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

The assumed measurement estimate givesbecause $Q=2^m>N^2$. Since $(k,r)=1$, the fraction $k/r$ is reduced.

Suppose two distinct reduced fractions $k/r$ and $k^{\prime }/r^{\prime }$ with $r,r^{\prime }<N$ both obeyed $(\ast )$. ThenBut distinct reduced fractions satisfya contradiction. Hence at most one such fraction exists.

Solved by gpt-5.6-sol high.