Find all positive integers $n$ such that the equation $\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$ has exactly $2011$ positive integer solutions $(x,y)$ where $x \leq y$.
Problem
Source: 2011 China Girls Mathematical Olympiad P1
Tags: number theory, Diophantine equation, prime factorization, number theory unsolved
07.08.2011 07:41
$(x-n)(y-n)=n^2$ must have exactly $2011$ solutions with $x\leq y$, hence $n$ must have exactly $2011$ divisors. But as $2011$ is prime, this can be achieved only for $n=p^{2010}$ where $p$ is prime.
08.08.2011 11:43
Farenhajt wrote: But as $2011$ is prime, this can be achieved only for $n=p^{2010}$ where $p$ is prime. I don't think that $2011$ being prime is enough to conclude the special form of $n$. If you do the same problem with $5$ instead of $2011$ (which is also prime), you get solutions of the form $n = p^4$, but also solutions of the form $n=pq$ with $p \neq q$ prime. (You can easily check the case $n=6$.) I think what you should use instead is that $4021$ is prime.
08.08.2011 12:34
Well spotted. The conclusion remains the same, but the reasoning is correct: $n^2$ must have $4021$ divisors, thus $n=p^{2010}$.
08.08.2011 13:02
Farenhajt wrote: $(x-n)(y-n)=n^2$ must have exactly $2011$ solutions with $x\leq y$, hence $n$ must have exactly $2011$ divisors. But as $2011$ is prime, this can be achieved only for $n=p^{2010}$ where $p$ is prime. Well, I think the wrong lies with this "solution", and solyaris is practically right. From $(x-n)(y-n)=n^2$ having to have exactly $2011$ solutions with $x\leq y$ follows that $n^2$ must have either $4022$ or $4021$ positive divisors. The case $4022=2\cdot 2011$ is realized by either $n^2 = p^{2010}q$ or $n^2 = p^{4021}$, both impossible. The case $4021$ is realized by $n^2 = p^{4020}$, thus $n = p^{2010}$. When solyaris proposed $n=6$ as a solution when we replace $2011$ by $5$, he is right, since $n^2 = 2^2\cdot 3^2$ has $9$ positive divisors, hence there are $5$ solutions. The above discussion for $5$ requires that $n^2$ must have either $10$ or $9$ positive divisors. The case $10=2\cdot 5$ is realized by either $n^2 = p^{4}q$ or $n^2 = p^{9}$, both impossible. The case $9=3\cdot 3$ is realized by either $n^2 = p^{2}q^2$, thus $n = pq$ (solyaris' counterexample), or $n^2 = p^8$, thus $n=p^4$. So what actually matters when we want exactly $q$ solutions, with $q$ an odd prime, is the factorization of $2q-1$.
08.08.2011 13:46
The Diophantine equation $(*) \; (x-n)(y-n) = n^2$ where $0 < x \leq y$ has exactly $\frac{1 + \tau(n^2)}{2}$ solutions. Proof: According to $(*)$ $x = n + d, y = n + \frac{n^2}{d}$ where $d$ is a divisor of $n^2$. Now $x=n + d > 0$ and $y = n(1 + \frac{n}{d}) > 0$ iff $(1) \; d > -n$ and $(2) \; \frac{n}{d} > -1$. If $d<0$, then $d < -n$ by (2), which contradicts (1). Hence $d>0$. Moreover $x \leq y$ gives $d \leq n$. Summa summarum the number of solutions of $(*)$ is the number $N$ of divisors of $n^2$ in the intervall $[1,n]$. The positive divisors (except $d$) of $n^2$ can be ordered in pairs $(d,n^2/d)$, where $0 < d < n$, implying $d<n^2/d$. Hence $(3) \; N = \frac{1 + \tau(n^2)}{2}. \;$ q.e.d. Let $\prod_{k=1}^m p_i^{r_i}$ be the prime factorization of $n$. Then $\tau(n^2) = \tau(\prod_{k=1}^m p_i^{2r_i}) = \prod_{k=1}^m (2r_i + 1),$ so by (3) $(4) \; \prod_{k=1}^m (2r_i + 1) = 2N - 1.$ If $N=2011$, then $\prod_{k=1}^m (2r_i + 1) = 4021$ hence $m=1$ and $r_1 = 2010$ since 4021 is a prime. Thus $N=2011$ iff $n = p^{2010}$ where $p$ is a prime. As mavropnevma writes, the number $N$ of solutions of $(*)$ is determined by the prime factorization of $2N-1$.
08.08.2011 16:00
Always good to see a poster retelling a poster's retelling of a post. Should this grow into a marathon?