4-8-2019

Quadratic Residues
In this section, we’ll begin our discussion of quadratic congruences. The central result to come is called
Quadratic Reciprocity.
Gauss considered the proofs he gave of quadratic reciprocity one of his crowning achievements; in fact,
he gave 6 distinct proofs during his lifetime. Reciprocity is a deep result: Proofs eluded both Euler and
Legendre.
The reciprocity law is simple to state. For p and q odd primes, it relates solutions to the two congruences

x2 = p (mod q) and x2 = q (mod p) .

(Note how p and q switch places: This explains why it’s called a reciprocity law.) The law of quadratic
reciprocity says:

The congruences are either both solvable or both unsolvable, unless both primes are congruent to 3 mod
4. In that case, one is solvable while the other is not.

Gauss first gave a proof of this when he was 19!

Gauss’s masterwork, the Disquisitiones Arithmeticae, was published in 1801 when Gauss was 24. It
changed the course of number theory, collecting scattered results into a unified theory.
We’ll look at some important computational devices before we consider reciprocity.

Definition. Let (a, m) = 1, m > 0. a is a quadratic residue mod m if the following equation has a
solution:
x2 = a (mod m) .
Otherwise, a is a quadratic nonresidue mod m.

Example. (a) Is 8 a quadratic residue mod 17?

(b) Find all the quadratic residues mod 18.

(a) 8 is a quadratic residue mod 17, since 52 = 8 (mod 17).

(b) I list the elements in {1, 2, . . . 17} which are relatively prime to 18 and compute their squares mod 18:

x 1 5 7 11 13 17
2
x (mod 18) 1 7 13 13 7 1

The quadratic residues are the squares: that is, 1, 7, and 13.
Since x2 = (−x)2 , the second row of the table is symmetric left-to-right.

Lemma. Let p be an odd prime, and consider the congruence

x2 = a (mod p) .

(a) The only solution is x = 0 if a = 0.

(b) There are exactly 0 or 2 solutions if p 6 | a.

Proof. x = 0 solves x2 = 0 (mod p). Conversely, if x2 = 0 (mod p), then p | x2 , so p | x, and hence
x = 0 (mod p).
Suppose p 6 | a. To show there are 0 or 2 solutions, suppose there is at least one solution b. Then
b2 = a (mod p), so (−b)2 = a (mod p). I claim that b and −b are distinct.

1
 If not, then b = −b (mod p), so p | 2b. p is an odd prime, so p 6 | 2. Therefore, p | b, b = 0 (mod p),
b2 = 0 (mod p), and finally a = 0 (mod p) — contradicting p 6 | a. Hence, b 6= −b (mod p).
Now I have two distinct solutions; since a quadratic equation mod p has at most two solutions (Prove
it!), there are exactly two.

For example, x2 = 8 (mod 17) has 5 and 12 as solutions, and 5 = −12 (mod 17).
On the other hand, you can check that the quadratic residues mod 17 are {1, 2, 4, 8, 9, 13, 15, 16}. Thus,
x2 = 5 (mod 17) has no solutions.
Note that the result is false if p = 2, since x2 = 1 (mod 2) has exactly one solution: x = 1 (mod 2).
p−1 p−1
Corollary. Let p be an odd prime. There are quadratic residues and quadratic nonresidues
2 2
mod p in {1, . . . , p − 1}.

Proof. k and −k = p − k have the same square mod p. That is, 1 and p − 1 have the same square, 2 and
p−1 p−1
p − 2 have the same square, . . . , and and + 1 have the same square.
2 2
p−1
Thus, the number of different squares is — these squares are the quadratic residues, and the other
2
p−1
numbers in {1, 2, . . . , p − 1} are quadratic nonresidues.
2
a
 
Definition. Let p be an odd prime, and let (a, p) = 1. The Legendre symbol     is defined by
p
  
a 1 if a is a quadratic residue mod p

  =
p −1 if a is a quadratic nonresidue mod p

Note that a = 0 is disallowed (since (0, p) = p 6= 1) even though x2 = 0 (mod p) has a solution.
4 5
   
As an easy example,    = 1, since 4 = 22 (mod 11). On the other hand,     = −1, because as
11 17
2
I noted above x = 5 (mod 17) has no solutions.

You might wonder about the case where p = 2, or the case where the modulus is composite. For p = 2,
there are only two quadratic congruences:

x2 = 0 (mod 2) and x2 = 1 (mod 2) .

These have the solutions x = 0 (mod 2) and x = 1 (mod 2) — nothing much is going on.
If the modulus has prime factorization n = pr11 · · · prkk , then relative primality implies that it’s enough
to solve the congruences x2 = a (mod pri i ) for each i. It turns out that solving such a congruence reduces
to determining whether a is a quadratic residue mod pi . Therefore, there is little harm in concentrating on
the case of a single prime.

Example. Solve the congruence

x2 = 79 (mod 91) .
I’ll solve the congruences
x2 = 79 (mod 7) and x2 = 79 (mod 13) .
x2 = 79 (mod 7) reduces to x2 = 2 (mod 7). Making a table of squares mod 7, I find that the solutions
are x = 3 and x = 4 mod 7.
x2 = 79 (mod 13) reduces to x2 = 1 (mod 13). The solutions are x = 1 and x = −1 = 12 mod 13.
I’ll consider the 2 · 2 = 4 possibilities, solving using the Chinese Remainder Theorem. But note that
since m2 = (−m)2 , the solutions will come in pairs. So once I find a solution m, I know that −m is also a
solution.

2
 Consider
x = 3 (mod 7)
x = 1 (mod 13)

m 7 13
p 13 7
s=p −1
(mod m) 6 2
a 3 1

x = 13 · 6 · 3 + 7 · 2 · 1 = 248 = 66 (mod 91) .

Then x = −66 = 25 (mod 91) is another solution.
Consider
x = 3 (mod 7)
x = 12 (mod 13)

m 7 13
p 13 7
s = p−1 (mod m) 6 2
a 3 12

x = 13 · 6 · 3 + 7 · 2 · 12 = 402 = 38 (mod 91) .

Then x = −38 = 53 (mod 91) is another solution.
It’s possible that the second computation might have given me 25, the solution I got earlier. In that
case, I’d have to move on to one of the other two cases. I got lucky and had to only do two cases, instead
of three.

Here are some tools for computing Legendre symbols.

Theorem. (Euler) Let p be an odd prime, a > 0, (a, p) = 1. Then

a
 

   = a(p−1)/2 (mod p) .
p

a
 
Proof. There are two cases. Suppose that     = 1. Then there is a number b such that b2 = a (mod p).
p
So
(b2 )(p−1)/2 = a(p−1)/2 (mod p)
bp−1 = a(p−1)/2 (mod p)
If p | b, then p | b2 = a, a contradiction. So p 6 | b, and Fermat’s theorem implies that bp−1 = 1 (mod p).
So
a
 
a(p−1)/2 = 1 (mod p) , and    = a(p−1)/2 (mod p) .
p
a
 
The other possibility is     = −1. In this case, consider the set {1, 2, . . . , p − 1}. I claim that these
p
integers occur in pairs s, t, such that st = a.
First, if s ∈ {1, 2, . . . , p − 1}, then s is invertible mod p. So I can write s(s−1 a) = a, and the pair s,
s a, multiplies to a.
−1
a
 
2
Moreover, s and s a are distinct. If not, s = s a, or s = a, which contradicts 
−1 −1    = −1.
p

3
 p−1
Since the integers {1, 2, . . . , p − 1} divide up into pairs, each multiplying to a, and since there are
2
pairs, I have
1 · 2 · · · (p − 1) = a(p−1)/2 (mod p) .
By Wilson’s theorem,
−1 = a(p−1)/2 (mod p)
a
 
 
  = a(p−1)/2 (mod p)
p

10
 
Example. Use Euler’s formula to compute 
  .
13

a(p−1)/2 = 106 = 1 (mod 13) .

10
 
Hence, 
   = 1, and x2 = 10 (mod 13) should have a solution. Indeed,
13

72 = 49 = 10 (mod 13) .

Euler’s formula gives an expression for the Legendre symbol, but it becomes tedious to compute with
it if the numbers are large. We’ll see that you can use the properties of the Legendre symbol given below
together with Quadratic Reciprocity to simplify computations.
a b
   
Proposition. If a = b (mod p), then    =   .
p p
Proof. If a = b (mod p), then x2 = a (mod p) if and only if x2 = b (mod p). Thus, one  ofthese
 equations
a b

is solvable or not solvable if and only if the same is true for the other — which means 
 
 = 
 .
p p
a
 
Note that I can use this result to apply Euler’s formula to     for a < 0 by simply replacing a with
p
b > 0 such that a = b (mod p).

Proposition. Let p be an odd prime, a, b > 0, (a, p) = (b, p) = 1. Then

a  b   ab 
    
 
   =  .
p p p

Proof. By Euler’s formula,

a b ab
    

     = a(p−1)/2 b(p−1)/2 (mod p) , and 
   = (ab)(p−1)/2 (mod p) .
p p p

Therefore,
a  b   ab 
    

     =   (mod p) .
p p p
The two sides of this equation are ±1. Since p is an odd prime, the two sides can’t differ by 2. Hence,
they must be equal as integers:
a  b   ab 
    
 
   =  .
p p p

4
Corollary. Let p be an odd prime, a > 0, (a, p) = 1. Then
 2
a 
 = 1.


 
p

Proof.  2        2
a  a a a

 
  =    = 
   = (±1)2 = 1.
p p p p

a
 
You can use the results above to compute 
   for specific values of a and arbitrary p.
p
Proposition. Let p be an odd prime. Then
 
−1 
= 1 if p = 4k + 1

 .
−1 if p = 4 k + 3

p

Proof. By Euler’s formula,

−1   p − 1 
   

 =  = (p − 1)(p−1)/2 = (−1)(p−1)/2 =
p p
 
(−1)2k if p = 4k + 1 1 if p = 4k + 1
= .
(−1)2k+1 if p = 4 k + 3 −1 if p = 4 k + 3

−1 
 
As examples, 
  = 1, because 13 = 4 · 3 + 1. Thus, x2 = −1 (mod 13) has solutions. And in fact,
13

52 = 25 = 12 = −1 (mod 13) .

−1 
 
Likewise, 
  = −1, because 23 = 4 · 5 + 3. Hence, x2 = −1 (mod 23) has no solutions.
23
Using Gauss’s lemma, which I’ll prove shortly, you can also show that

2
 
2
 
  = (−1)(p −1)/8 .
p

p2 − 1
Note that is actually an integer: Since p = 2k + 1, I have p2 − 1 = 4k(k + 1). And 4k(k + 1) is
8
divisible by 8, because one of k, k + 1, must be even.
So, for example,
2
 
2
 
  = (−1)(7 −1)/8 = 1.
7
Therefore, x2 = 2 (mod 7) has solutions. x = 3 works, for instance.

c 2019 by Bruce Ikenaga 5