Diophantine Reciprocals I

In the following equation $x$, $y$, and $n$ are positive integers.
$$\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{n}$$
For $n = 4$ there are exactly three distinct solutions:
$$\begin{align}
\dfrac{1}{5} + \dfrac{1}{20} &= \dfrac{1}{4}\\
\dfrac{1}{6} + \dfrac{1}{12} &= \dfrac{1}{4}\\
\dfrac{1}{8} + \dfrac{1}{8} &= \dfrac{1}{4}
\end{align}
$$

What is the least value of $n$ for which the number of distinct solutions exceeds one-thousand?
NOTE: This problem is an easier version of Problem 110; it is strongly advised that you solve this one first.

This is an algebra problem that involves diophantine equations.

The given equation is a particular case of the general diophantine equation known as the equation of friendly pairs:

$\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{n}$

If we rewrite it, we get:

$yx = n(x+y)$

And further simplified to:

$yx-nx = ny$

This is equivalent to:

$x(y-n) = ny$

Here the positive integer solutions (x, y) are dependent on the positive integer divisors of $n^2$. Note that x must be greater than n.

Let’s denote d as a divisor of $n^2$; then, x can be represented as:

$x = \dfrac{n^2}{d} + d$

Where d can take any value from n+1 to $\sqrt{n^2}$ (inclusive).

The number of solutions is hence equal to half the number of divisors of $n^2$.

Therefore, to find the least value of n, we need to find the least integer whose square has over 2000 divisors (since 2*1000=2000, and we need over 1000 solutions).

A number $n$ = $p_1^{k_1}*p_2^{k_2}*…*p_n^{k_n}$ (p’s are prime divisors) has $(k_1 + 1)*(k_2 + 1)*…*(k_n + 1)$ divisors. For square number n^2, the number of its divisors is $(2*k_1 + 1)*(2*k_2 + 1)*…*(2*k_n + 1)$.

From this, we want to find the smallest $n$ such that $(2*k_1 + 1)*(2*k_2 + 1)*…*(2*k_n + 1) > 2000$.

The product is maximized when $k_1 >= k_2 >= … >= k_n$.

Start with first few prime numbers (2, 3, 5, 7…) and assign them power starting from 1. So, The smallest such $n$ is $2^3 * 3^2 * 5^1 * 7^1 * 11^0 * 13^0 … = 2^3 * 3^2 * 5 * 7 = 2520$.

Therefore, the least value of $n$ for which the number of distinct solutions exceeds one-thousand is 2520.

More Answers: