Ok, here’s the third installation. Getting a little tired of repeatedly saying “a is/isn’t a square mod p“, we introduce a new notation.
Definition. Let p be an odd prime and a be an integer coprime to p. The Legendre symbol is given by:
For completeness, one also defines if a is a multiple of p, but we won’t need this for now. From our previous post, we know the following:
- hence from property 1, ;
- for special values of a, we have and .
From the multiplicative property (2), it thus suffices to consider for odd prime q ≠ p. This is where we’ll pull the next rabbit out of the hat (i.e. quote a result without proof).
Quadratic Reciprocity Theorem. If p, q are distinct odd primes, then
In other words, and are identical unless both p and q are congruent to 3 mod 4.
Example 1. Determine whether 31 is a square modulo 73.
Solution. We will repeatedly use the quadratic reciprocity rule:
- since 73 is 1 mod 4, so ;
- since 31 ≡ 11 ≡ 3 (mod 4), so since 9 is clearly a square mod 11.
Thus, 31 is not a square modulo 73. ♦
Example 2. Classify all odd primes p ≠ 3 such that 3 is a square modulo p.
Solution. Use the quadratic reciprocity: . Since the RHS depends on p modulo 4, we need to consider p modulo 12. Thus, 3 is a square modulo p iff .
- If , then and , i.e. .
- If , then and , i.e. .
Thus 3 is a square mod p iff p ≡ ±1 (mod 12). ♦
Example 3. Classify all odd primes p ≠ 3 such that -3 is a square modulo p.
Solution. From example 1, we have . Thus,
And -3 is a square mod p iff p ≡ 1 (mod 3). ♦
Coming up next: applying quadratic residues in conjunction with order of an element modulo n to solve IMO-type problems. The gist of the idea is this: suppose p is a prime and a be not divisible by p; let the (multiplicative) order of a modulo p be denoted d. We already know that d | (p-1). It turns out that a is a square modulo p if and only if is even.
To see why, just let g be a primitive root modulo p. And write . Now d is the smallest positive integer for which . Thus d is the smallest positive integer such that rd is a multiple of (p-1). A moment of thought will tell you that thus d = (p-1)/gcd(r, p-1) (prove it! just write g = gcd(r, p-1) and r = gu, (p-1) = gv where (u, v) = 1 … ).
Thus, our desired result follows from the fact that a is a square modulo p if and only if r is even. If you’re not sure why the fact is true, refer to part II of the notes. If you’re still confused, fret not, we will include some concrete examples in the next installation.