= Solution
The assumed measurement estimate gives
$$
\left|\frac cQ-\frac kr\right|<\frac1{2Q}<\frac1{2N^2},
$$
because $Q=2^m>N^2$. Since $(k,r)=1$, the fraction $k/r$ is reduced.
Suppose two distinct reduced fractions $k/r$ and $k'/r'$ with $r,r'<N$ both obeyed $(*)$. Then
$$
\left|\frac kr-\frac{k'}{r'}\right|
<\frac1{N^2}.
$$
But distinct reduced fractions satisfy
$$
\left|\frac kr-\frac{k'}{r'}\right|
=\frac{|kr'-k'r|}{rr'}\geq\frac1{rr'}>\frac1{N^2},
$$
a contradiction. Hence at most one such fraction exists.
Solved by gpt-5.6-sol high.
Back to article page
