Quadratic Residues – Part III | Mathematics and Such

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 $(\frac a p)$ is given by:

$(\frac a p) = \begin{cases} +1, \quad &\mbox{if } a \mbox{ is a square mod p},\\ -1,\quad &\mbox{if } a \mbox{ is not a square mod p}.\end{cases}$

For completeness, one also defines $(\frac a p) = 0$ if a is a multiple of p, but we won’t need this for now. From our previous post, we know the following:

$(\frac a p) \equiv a^{(p-1)/2} \pmod p$ ;
hence from property 1, $(\frac a p) (\frac b p) = ( \frac {ab} p )$ ;
for special values of a, we have $(\frac {-1} p) = (-1)^{(p-1)/2}$ and $(\frac 2 p) = (-1)^{(p^2-1)/8}$ .

From the multiplicative property (2), it thus suffices to consider $(\frac q p)$ 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

$(\frac p q) (\frac q p) = (-1)^{(p-1)(q-1)/4}$ .

In other words, $(\frac p q)$ and $(\frac q p)$ 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:

$(\frac{31}{73}) (\frac{73}{31}) = +1$ since 73 is 1 mod 4, so $(\frac{31}{73}) = (\frac{73}{31}) = (\frac{11}{31})$ ;
$(\frac{11}{31}) (\frac{31}{11}) = -1$ since 31 ≡ 11 ≡ 3 (mod 4), so $(\frac{11}{31}) = -(\frac{31}{11}) = -(\frac {9}{11}) = -1$ 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: $(\frac 3 p) (\frac p 3) = (-1)^{(p-1)/2}$ . Since the RHS depends on p modulo 4, we need to consider p modulo 12. Thus, 3 is a square modulo p iff $(\frac p 3) = (-1)^{(p-1)/2}$ .

If $(\frac p 3) = (-1)^{(p-1)/2} = +1$ , then $p \equiv 1 \pmod 3$ and $p \equiv 1 \pmod 4$ , i.e. $p \equiv 1 \pmod {12}$ .
If $(\frac p 3) = (-1)^{(p-1)/2} = -1$ , then $p \equiv 2 \pmod 3$ and $p \equiv 3 \pmod 4$ , i.e. $p \equiv 11 \pmod {12}$ .

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 $(\frac 3 p) = (\frac p 3) (-1)^{(p-1)/2}$ . Thus,

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

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 $\frac {p-1} d$ is even.

To see why, just let g be a primitive root modulo p. And write $a \equiv g^r \pmod p$ . Now d is the smallest positive integer for which $a^d \equiv g^{rd} \equiv 1 \pmod p$ . 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.

Quadratic Residues – Part III

Leave a Reply Cancel reply

Recent Posts

Archives

Categories

Meta

Pages