 Solution

ID: past-exam-of-the-short-options-course-of-the-university-of-oxford/2015/1/a/ii/solution

p

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

where the Legendre symbol is zero if

p ∣ a

, one if

a

is a nonzero quadratic residue, and minus one otherwise. Including the zero case makes this formulation valid for every integer

a

a

b

, and

ab

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

p

divides either factor, both sides are zero. Otherwise both sides belong to

{- 1, 1}

; these two values are distinct modulo the odd prime number

p

. The congruence is therefore an equality of integers, proving multiplicativity of the Legendre symbol:

(\frac{ab}{p}) = (\frac{a}{p}) (\frac{b}{p}) .

 New to topics? Read the docs here!