Integers $x$ such that $\frac{nx}{x-n}$ is an integer

I'm trying to find all solutions of $\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$ with $ n < x \leq y \ $ and with a given $n$.

I started manipulating the expression and got $y = \frac{nx}{x-n}$.

For now I'm iterating $x$ from $n+1$ to $2n \ $ (obtained by manipulating $ n < x \leq y $).

So, my question is: How can I generate $x$ such that $\frac{nx}{x-n}$ yields a positive integer, without checking all integers from $n+1$ to $2n$?

(This comes from project Euler problem 108 that my method manage to solve, but pretty slowly) I'm pretty new to computer science and all that stuff and don't know yet the tricks of divisibility, so I'm a bit stuck.

Thanks in advance!

Solution 1:

Let $n$ be a positive integer, and let $x$ and $y$ be integers with $y\geq x>n$ such that $$\frac1x+\frac1y=\frac1n.$$ Clearing denominators shows that this is equivalent to $$n(x+y)=xy.$$ Let $d:=\gcd(x,y)$ so that $x=dX$ and $y=dY$ for coprime integers $X$ and $Y$, and $$n(X+Y)=dXY.$$ Then $X+Y$ is coprime to $X$ and $Y$, so $X+Y$ divides $d$, say $d=c(X+Y)$, and so $$x=c(X+Y)X,\qquad y=c(X+Y)Y,\qquad n=cXY.$$

Conversely, let $n=cXY$ for any three positive integers $c$, $X$ and $Y$ with $X\leq Y$. Then for $x:=c(X+Y)X$ and $y:=c(X+Y)Y$ you have $n<x\leq y$ and $$\frac1x+\frac1y=\frac1n.$$ So your problem boils down to factoring $n$.