TAOCP 4.5.1 Exercise 9
Suppose $1 \le u' < 2^k$ and $1 \le v' < 2^k$.
Exercise 9. [**] [$M23$] If $1 \le u'$, $u' < 2^k$, show that $\lfloor 2^{2k} u/u' \rfloor = \lfloor 2^{2k} u/u' \rfloor$ implies $u/u' = v/v'$.
Verified: yes
Solve time: 3m18s
Suppose $1 \le u' < 2^k$ and $1 \le v' < 2^k$. If
$\lfloor 2^{2k} u/u' \rfloor = \lfloor 2^{2k} v/v' \rfloor,$
then the difference $|2^{2k} (u/u' - v/v')|$ is strictly less than $1$, because the floor of a number differs from the number by less than $1$. Hence
$|u/u' - v/v'| < 2^{-2k}.$
But the smallest positive difference between two distinct fractions with denominators less than $2^k$ is
$\frac{1}{u'v'} > \frac{1}{(2^k-1)^2} > 2^{-2k},$
so the only way the inequality $|u/u' - v/v'| < 2^{-2k}$ can hold is if $u/u' = v/v'$. This completes the proof.
∎