Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
    
Since you mentioned programming, is there an upper bound on $x, y$? i.e. a limit on how large $x$ and $y$ could be? –  user2468 Jul 14 '12 at 20:29
    
@ J.D. No sir no upper bounds –  cdummy Jul 14 '12 at 20:30
    
@ J.D. but they are natural numbers –  cdummy Jul 14 '12 at 20:30

1 Answer 1

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.

share|improve this answer
    
could you explain it with a simple example –  cdummy Jul 14 '12 at 20:27
    
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$. –  André Nicolas Jul 14 '12 at 20:31
    
sir could you explain it with an example –  cdummy Jul 14 '12 at 20:31
    
no sir the reason why it is difficult for large values –  cdummy Jul 14 '12 at 20:32
    
@cdummy en.wikipedia.org/wiki/Integer_factorization –  user2468 Jul 14 '12 at 20:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.