OurBigBook.comSite Source code

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

The assumed measurement estimate gives

\frac{c}{Q} - \frac{k}{r} < \frac{1}{2 Q} < \frac{1}{2 N ^{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

\frac{k}{r} - \frac{k ^{'}}{r ^{'}} < \frac{1}{N ^{2}} .

But distinct reduced fractions satisfy

\frac{k}{r} - \frac{k ^{'}}{r ^{'}} = \frac{∣ k r ^{'} - k ^{'} r ∣}{r r ^{'}} \geq \frac{1}{r r ^{'}} > \frac{1}{N ^{2}},

a contradiction. Hence at most one such fraction exists.

Solved by gpt-5.6-sol high.

 Ancestors (12)