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

With the positive-exponent convention,The opposite sign convention is equivalent after conjugating all Fourier phases.

Put $Q=2^m$. Applying the transform term by term giveswhereThus, when $e^{2\pi iru/Q}\ne 1$,If the denominator vanishes, the continuous limiting value isThe magnitude is a Dirichlet-kernel peak near integers $u$ for which $ru/Q$ is close to an integer.

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.

Here $N^2=441$, so the least power of two exceeding it is $Q=2^9=512$. The continued fraction iswhose convergents beginThe only nontrivial convergent with denominator below $N=21$ is $5/6$, and indeedThe uniqueness result therefore givesAs a check, $10^6\equiv 1(\mathrm{mod}21)$, while $10^2\not\equiv 1$ and $10^3\not\equiv 1$, so the order is exactly six.