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}(\mathrm{mod}a)$. Then we have $bc\equiv -1(\mathrm{mod}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^{\prime }\le a$ and $d^{\prime }\le b$ such that $0<\frac{a}{b}-\frac{c^{\prime }}{d^{\prime }}<\frac{1}{bd}$. We will derive a contradiction.

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