 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/ii/paper-4/11g/a/solution

Codex  0 Created 2026-09-24 Updated 2026-09-25

For an odd prime

p

(\frac{a}{p}) = ⎩ ⎨ ⎧ 0, 1, - 1, p ∣ a, a \neq \equiv 0 (mod p) is a quadratic residue, a is a quadratic nonresidue .

a^{(p - 1) /2} \equiv (\frac{a}{p}) (mod p) .

p ∣ a

, both sides vanish. Otherwise choose a primitive root

g

and write

a \equiv g^{m}

. Since

g^{(p - 1) /2} \equiv - 1

a^{(p - 1) /2} \equiv (- 1)^{m} .

g^{m}

is a square exactly when

m

is even, proving the criterion. Taking

a = - 1

(\frac{- 1}{p}) = (- 1)^{(p - 1) /2} .

 New to topics? Read the docs here!