IMO Team Selection Test 1, June, 2020

We will first show that it is possible to choose $c$ and $d$ such that $\frac{a}{b} - \frac{c}{d} = \frac{1}{bd}$.

Because $\gcd(a, b) = 1$, there exists a multiplicative inverse $b^{-1}$ of $b$ modulo $a$. Now let $c$ with $1 \le c \le a$ be such that $c \equiv -b^{-1} \pmod a$. Then we have $bc \equiv -1 \pmod a$, hence $a \mid bc + 1$. Define $d = \frac{bc+1}{a}$, which is a positive integer. We have $d = \frac{bc+1}{a} \le \frac{ba+1}{a} = b + \frac{1}{a}$. Because $a \ge 2$ and $d$ is an integer, we get $d \le b$. All conditions are met. Hence, we have $\frac{a}{b} - \frac{c}{d} = \frac{ad-bc}{bd} = \frac{bc+1-bc}{bd} = \frac{1}{bd}$.

If this is the smallest possible outcome, then we are done, because $\frac{1}{r} = bd$ would be an integer. We will show that no smaller positive outcome is achievable. Let $c$ and $d$ be as above, and suppose there are positive integers $c' \le a$ and $d' \le b$ such that $0 < \frac{a}{b} - \frac{c'}{d'} < \frac{1}{bd}$. We will derive a contradiction.

Let $x = ad' - bc'$, then we have $\frac{a}{b} - \frac{c'}{d'} = \frac{x}{bd'}$, hence $xbd < bd'$, which yields $xd < d'$. We also know that $x > 0$. Hence, $0 < xd < d' \le b$, which means that $xd$ and $d'$ are two distinct numbers whose difference is less than $b$. Moreover, from $x = ad' - bc'$ we get that $x \equiv ad' \pmod b$. On the other hand, we know that $ad - bc = 1$, hence $ad \equiv 1 \pmod b$, hence $xad \equiv x \pmod b$. Combining this, we get $ad' \equiv xad \pmod b$. Because $\gcd(a, b) = 1$ we may divide by $a$, hence $d' \equiv xd \pmod b$. However, we already saw that $d'$ and $xd$ are distinct numbers whose difference is smaller than $b$, hence this is impossible.

We conclude that the $c$ and $d$ we found indeed give the smallest possible outcome, and hence $\frac{1}{r}$ is an integer. $\square$