 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/ii/paper-3/10d/d/solution

Codex  0 Created 2026-09-24 Updated 2026-10-03

\frac{c}{2 ^{m}} ≃ \frac{s}{r},

where

r

is the desired multiplicative order. Here

\frac{c}{2 ^{m}} = \frac{256}{512} = \frac{1}{2} .

r = 2

8^{2} = 64 \equiv 1 (mod 21), 8 \neq \equiv 1 (mod 21) .

Hence

ord_{21} (8) = 2.

As a check, the classical final step of the Shor algorithm gives

g cd (8 - 1, 21) = 7, g cd (8 + 1, 21) = 3.

 New to topics? Read the docs here!