3
$\begingroup$

I want to write a code which boils down to equation $(x y) = (x + y) N$.

My task is to find all the possible integer (natural number) solutions for $x$ and $y$. For example, say $N=6$. As $x$ and $y$ are natural numbers, $x+y$ is also a natural number, starting from $1,2,\ldots$ That is, the product $xy$ should meet the multiples of $6$.

Is there any easy way to find all the combinations of $x$ and $y$?

  • 0
    @ J.D. but they are natural numbers2012-07-14

1 Answers 1

5

The equation can be rewritten as $(x-N)(y-N)=N^2$. So all positive solutions come from the factorizations of $N^2$ as a product $uv$, and all such factorizations come from a solution. Just put $x=N+u$, $y=N+v$.

Thus the problem of finding the solutions of your equation is essentially equivalent to the problem of finding all factors of $N^2$, which is easily solved if we know all the factors of $N$.

However, for very large $N$, finding all the factors of $M$ can be computationally challenging.

Remarks: Let $N$ have prime power factorization $N=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$. Then the number of ordered pairs $(u,v)$ of positive integers such that $uv=N^2$ is equal to $(2a_1+1)(2a_2+1)\cdots (2a_k+1)$. This is also the number of solutions of your equation. Thus you can manufacture examples where the number of solutions is large.

  • 0
    Because of the symmetry, you can assume $v \ge u$. Then if you want both solutions, you can switch them. In André Nicolas' example, the factorization $3 \cdot 12=36$ gives $u=3=x-6, v=12=y-6$, giving (as he says) $x=9, y=18$. You then also know there is a solution $x=18, y=9$2012-07-14