 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/ii/paper-4/11i/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 square, a is a nonsquare .

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

The Gauss lemma says that, for

p ∤ a

, if

m

of the least positive residues of

a, 2 a, \dots, \frac{p - 1}{2} a

lie in

(p /2, p)

, then

(\frac{a}{p}) = (- 1)^{m} .

To prove it, replace every residue above

p /2

by its negative. The resulting absolute residues are distinct up to sign and therefore form a permutation of

1, 2, \dots, \frac{p - 1}{2} .

Multiplying the congruences gives

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

Cancel the nonzero factorial and apply Euler's criterion.

For

a = 2

, the residues are

2, 4, \dots, p - 1

. The number above

p /2

m = \frac{p - 1}{2} - ⌊ \frac{p}{4} ⌋,

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

Consequently, for odd primes,

x^{2} \equiv 2 (mod p) ⟺ p \equiv 1 or 7 (mod 8) .

The congruence is also soluble for

p = 2

 New to topics? Read the docs here!