Q:

Find all ordered pairs \((a, b)\) of positive integers such that

\[ \frac{1}{a} + \frac{1}{b} = \frac{3}{2018} \]

A:

I honestly threw the entire kitchen sink at this problem (to generally no avail) for a solid two weeks. I suppose this is less of a surprise and more of a running theme of this blog. My excuse this time is that I haven’t worked with divisibility relations in a long long time, and thus I had to learn/prove how to manipulate them from scratch. None of the things I discovered are crazy or hard; they’re just basic things I haven’t been used to thinking about. It’s funny because we always joke about how the mathematicians of ancient times got famous for grabbing all the low hanging mathematical fruit. Sometimes I wonder, though, how far I could have to taken the field of basic (i.e. middle school) algebra or number theory if I just started proving things from the ground up, fueled solely by my curiosity and resourcefulness. Sometimes I feel like I wouldn’t have gotten very far at all.

We will establish two (honestly trivial) lemmas, and that’ll be all we’ll need to solve this problem.

Lemma 1

For any integer \(k\), if \(a \mid b\) then \(a \mid bk\)

Proof Lemma 1

I generally try not to use the phrase “This is obvious” in my proofs, but this lemma should indeed be obvious.

Lemma 2

For any integer \(k\), if \(a \mid b\) then \(a \mid b + ak\)

Proof Lemma 2

This lemma should also be obvious, but for completion: \(a \mid b\) is equivalent to saying there exists an integer \(j\) such that \(b = aj\). Thus

\[ b + ak = aj + ak = a(j+k) \]

which implies that \(b + ak\) is divisible by \(a\).

Solving the Problem

Suppose \(a\) and \(b\) are positive integers such that

\[ \frac{1}{a} + \frac{1}{b} = \frac{3}{2018} \]

We can assume WLOG that \(a \leq b\), since the problem is symmetric in \(a\) and \(b\). Since \(a\) and \(b\) are positive integers, we can thus bound \(a\) as follows:

\[ \frac{1}{2} \cdot \frac{3}{2018} \leq \frac{1}{a} \leq \frac{3}{2018} \]

since \(a \leq b\) implies that \(\frac{1}{a} \geq \frac{1}{b}\) which implies that \(\frac{1}{a}\) should make up at least half of \(\frac{3}{2018}\). On the other hand, \(\frac{1}{a}\) can’t be more than \(\frac{3}{2018}\). Taking the reciprocals of the inequalities, we get

\[ 672\frac{2}{3} \leq a \leq 1345\frac{1}{3} \]

which means we can restrict our search space to

\[ 673 \leq a \leq 1345 \]

From our original sum equation, we can solve for \(b\):

\[ \frac{3}{2018} = \frac{1}{a} + \frac{1}{b} = \frac{a + b}{ab} \]

\[ \Rightarrow 3ab = 2018(a+b) \]

\[ \Rightarrow (3a - 2018)b = 2018a \]

\[ \Rightarrow b = \frac{2018a}{3a - 2018} \]

Since \(b\) is an integer, we must have that the RHS is also an integer, i.e.

\[ 3a - 2018 \mid 2018a \]

Using Lemma 2, we can multiply the RHS by \(3\):

\[ 3a - 2018 \mid 3 \cdot 2018a \]

Using Lemma 1, we can subtract \(2018(3a - 2018)\) from the RHS:

\[ 3a - 2018 \mid 3 \cdot 2018a - 2018(3a - 2018) = 3 \cdot 2018a - 2018 \cdot 3a + 2018^2 = 2018^2 \]

In other words, \(3a - 2018\) must be a factor of \(2018^2\).

The prime factorization of \(2018^2\) is \(2^2 \cdot 1009^2\), so the candidates for \(3a - 2018\) are: \(1, 2, 4, 1009, 2 \cdot 1009, 4 \cdot 1009, 1009^2, 2 \cdot 1009^2, 4 \cdot 1009^2\).

\(3a - 2018 = 1\) gives us the solution \(a = 673\).

\(3a - 2018 = 2\) has no integer solution.

\(3a - 2018 = 4\) gives us the solution \(a = 674\).

\(3a - 2018 = 1009\) gives us the solution \(a = 1009\).

\(3a - 2018 = 2 \cdot 1009\) has no integer solution.

\(3a - 2018 = 4 \cdot 1009\) gives us the solution \(a = 2018\).

Here we can actually stop, since, as we noted before, we can restrict our search space for \(a\) to \(a \leq 1345\). Thus our final set of solutions is simply

\[ (673, 673 \cdot 2018), (674, 337 \cdot 1009), (1009, 2018) \]

Of course, the flipped version of each of the pairs above works too.