Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2026/ii/paper-1/1g/solution

A primitive root modulo is a unit of order ; a nonzero quadratic residue modulo an odd prime is a square.
If a primitive root modulo were , then its order would divide , the order of the subgroup of squares, contradicting .
Modulo , has order , so the primitive roots are for :
Finally , so the lifting criterion makes primitive modulo . It is plainly the smallest possible positive primitive root.

New to topics? Read the docs here!