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.

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 2 / 15C / d / iii / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ii/paper-2/15c/d/iii/solution