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
    Since you mentioned *programming*, is there an upper bound on $x, y$? i.e. a limit on how large $x$ and $y$ could be?2012-07-14
  • 0
    @ J.D. No sir no upper bounds2012-07-14
  • 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
    could you explain it with a simple example2012-07-14
  • 0
    Sure. Say $N=6$. Then $36=1\cdot 36=2\cdot 18=3\cdot 12$ and so on. Take for example $3\cdot 12$. Set $x-6=3$, $y-6=12$. That gives us the solution $x=9$, $y=18$. For another example, $36=9\cdot 4$. So set $x-6=9$, $y-6=4$, we get the solution $x=15$, $y=10$.2012-07-14
  • 0
    sir could you explain it with an example2012-07-14
  • 0
    no sir the reason why it is difficult for large values2012-07-14
  • 0
    @cdummy http://en.wikipedia.org/wiki/Integer_factorization2012-07-14
  • 0
    @André Nicolas k thanks.2012-07-14
  • 0
    By large I meant huge. There is no known fast algorithm for factoring. Of course factoring is easy by hand for numbers under a few hundred. And we need only factor $N$, because from that we can pick up all factorizations of $N^2$.2012-07-14
  • 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