Find all ordered pairs $(a,b)$ of positive integers for which $\frac{1}{a} + \frac{1}{b} = \frac{3}{2018}$

Question

This question comes from the 2018 Putnam and can be found in the following link:

https://kskedlaya.org/putnam-archive/

So far, I got the following two equations using simple algebra:

(1) $2018a = b(3a - 2018)$

(2) $2018b = a(3b - 2018)$

Then, I divide (1) by $b$ and I divide (2) by $a$ to get

(3) $\frac{2018a}{b} = (3a - 2018)$

(4) $\frac{2018b}{a} = (3b - 2018)$

Multiplying (3) and (4) together, I get $(2018)^2 = (3a - 2018)(3b-2018)$

So $(2018\mod3)$ is congruent to $(2\mod3)$ and $(2\mod3)^2$ is congruent to $(1 \mod3)$. In the answer provided, I'm told that each of the factors is congruent to $(1\mod3)$. Do we not consider the case when both factors are congruent to $(2\mod3)$ because only $2$ satisfies this requirement, and

$2$ x $2 = 4$ is definitely not equal to $2018$?

Answer 1

You want to look at factorizations of $2018^2$ where each term $\equiv -2018 \equiv 1 \mod 3$. Since $2018 = 2 \times 1009$ with $1009$ prime, there are not too many solutions.

Answer 2

Do we not consider the case when both factors are congruent to (2mod3) ...?

There is no such case since both factors in $(3a-2018)(3b-2018)$ are congruent to $1$ (mod $3$) whatever integers you take for $a$ and $b$: $$ 3n-2018=-2018=1\pmod{3},\quad \forall n\in{\mathbb{Z}}. $$

That's why the solution says so:

Answer 3

Take $d=gcd(a,b)$, with $a=da_2$, $b=db_2$. Then $\frac 1 a + \frac 1 b = \frac 1 {da_2} + \frac 1 {db_2}$. $a_2$ and $b_2$ are by definition coprime, so $\frac {b_2+a_2}{da_2b_2}$ is a fraction in simplest form that is equal to $\frac 3 {2018}$. Since $da_2b_2=2018$, and $1009$ is a prime factor of $2018$, it follows that of $d$, $a_2$, and $b_2$, one of them must be $1009$, and clearly that would be $d$ (otherwise the numerator $b_2+a_2$ would contain a $1009$, which is more than $3$). It then follows that of $a_2$ and $b_2$, one of them is $2$, and then it follows that the other is $1$.

Answer 4

More generally, if $\dfrac1{a}+\dfrac1{b} =\dfrac{u}{v}$, then $v(a+b) =abu $ or

$\begin{array}\\ 0 &=abu^2-uv(a+b)\\ &=abu^2-uv(a+b)+v^2-v^2\\ &=(au-v)(bu-v)-v^2\\ \end{array} $

so $(au-v)(bu-v)=v^2 $.

In particular, either $au\gt v, bu \gt v$ or $au\lt v, bu \lt v$.

We can assume that $a \ge b$.

If $a=b$ then $(au-v)^2=v^2 $ so $au-v = \pm v$ so that $a = \frac{2v}{u}$ (which gives $\frac1{a}=\frac{u}{2v}$) or $a=0$ , which not be. For there to be a solution here, we must have $u | 2v$.

So we can assume from now on that $a > b$.

For each factorization $v^2 = rs$ with $r \le s$, for a solution we must have either $au-v=r, bu-v = s $, $au-v=s, bu-v = r $, $au-v=-r, bu-v = -s $, or $au-v=-s, bu-v = -r$.

Since $a > b$ and $r \le s$, the first and third cases can not hold, so either $a = \frac{v+s}{u}, b = \frac{v+r}{u} $ or $a = \frac{v-r}{u}, b = \frac{v-s}{u} $.

For these to be integers, we must have either $u | (v+s), u | (v+r)$ or $u | (v-r), u | (v-s)$. In either case, we must have $u | (s-r)$.

By looking at $v \bmod u$ we can quickly decide which $r$ and $s$ will work.