6
$\begingroup$

I have a question about the following problem from a Putnam review:

Let $n\in \mathbb{N}$. Find how many pairs of natural numbers $(x, y)\in \mathbb{N}\times \mathbb{N}$ solve $$ \frac{xy}{x+y}=n. $$

I have found some solutions for all $n$, such as $(2n, 2n)$ and $(n+1, n(n+1))$, but I feel as though this is the wrong approach, as the question is only asking for the number of solutions to the equation.

I don't really want a complete solution, but any hints would be greatly appreciated.

$\endgroup$
14
$\begingroup$

HINT:

Utilize $$(x-n)(y-n)=n^2$$

$\endgroup$
2
  • $\begingroup$ Sorry if this is stupid, but how does one come up with this? I thought about some kind of an intelligent factorisation for a long time but was unable to come up with this. $\endgroup$ – eem Aug 15 '19 at 21:39
  • 1
    $\begingroup$ @AdityaDutt It's a special case of completing a product, a generalization of completing a square. $\endgroup$ – Bill Dubuque Dec 18 '19 at 5:59
5
$\begingroup$

This can be rewritten as

$$\frac 1x+\frac 1y=\frac 1n$$

$$\frac 1y=\frac 1n-\frac 1x$$ $$y=\frac{nx}{x-n}$$

Changing variables to $k=x-n$:

$$y=\frac{n(n+k)}{k}$$

$$y=\frac{n^2}k+n$$

The left side is an integer. What does that tell you about the allowed values of $k$, and the corresponding number of valid $x$ values?

$\endgroup$
1
$\begingroup$

Let $d=\gcd (x,y)$ and $x=dp, y=dq$ and $\gcd (p,q)=1$. Then we have $$\frac{dpq}{p+q}=n$$ Now $\gcd(pq,p+q)=1$ implies $(p+q)|d$. So $d=k(p+q)$ where $k\in\mathbb{N}$. Hence all the solutions are given by, $$x=kp(p+q), y=kq(p+q)$$ where $k,p,q\in\mathbb{N}$, $\gcd(p,q)=1$ and $n=kpq$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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