4.

Quadratic Residues

We study quadratic residues and non-residues. In this part we are mainly interested in
deciding whether a given integer a is a quadratic residue modulo an odd prime p. We will
introduce quadratic reciprocity, whose proof will be given in next part.

4.1. Quadratic residues and the Legendre symbol. First we recall the definition of
quadratic residues and non-residues.

Definition 4.1. For integers a and m, m  0, hcf pa, mq  1, a is called a quadratic

residue modulo m if the congruence x2  a pmod mq has a solution. Otherwise a is
called a quadratic non-residue modulo m.

Given any fixed positive integer m, it is possible to determine the quadratic residues
by simply listing the positive integers less than and coprime to m, squaring them, and
reducing modulo m. But we prefer to have a more convenient way to determine whether
a given integer a coprime to m is a quadratic residue modulo m. At the moment we are
mostly interested in the case that m is an odd prime p. An example of a composite m
will be given in Exercise 5.3.

The Legendre symbol is a very simple yet powerful tool in studying this problem. Roughly
speaking, it is the indication function for quadratic residues. We recall its definition:

a
Definition 4.2. Let p be an odd prime. The Legendre symbol takes value 1 if a is
p
a quadratic residue modulo p, or
1 if a is a quadratic non-residue modulo p, or 0 if p
divides a.

Therefore the problem reduces to the computation of the Legendre symbol. There are a
series of rules which help with the computation. We introduce them in four groups.

The first group of properties are simple consequences of the definition.

Proposition 4.3. Let p be an odd prime.

a
b
(1) If a  b pmod pq, then  .
p p

a2
(2) If p  a, then  1.
p

Proof. Both statements are clear by definition. 

Next group of properties are more interesting. The proof essentially use the existence of
primitive roots.
39
Proposition 4.4. Let p be an odd prime.

a
(1) (Euler’s criterion).
p
 a
pmod pq.
p 1
2

ab
a
b
(2)
p
 p p
.

Proof. For (1), both sides are congruent to 0 if p  a. Now we assume p  a. Notice
p
1 p
1
that ap
1  1 pmod pq by Corollary 2.11. Hence pa 2 1qpa 2
1q  0 pmod pq, so
p
1
a 2  1 or
1 pmod pq.


If a is a quadratic residue modulo p, assume a  x2 pmod pq. Then p  x, and a 2 
p 1

xp
1  1 pmod pq by Corollary 2.11 again. If a is a quadratic non-residue modulo p, it

p
1
suffices to show a 2  1 pmod pq. Let g be a primitive root modulo p, then a  g r
pmod pq for some r P Z. We observe that r must be odd, otherwise a  pg r2 q2 pmod pq
is a quadratic residue. Hence we can write r  2k 1 for some k P Z. Then we have
p
1 p
1 p
1 p
1
a 2  g p2k 1q 2  g pp
1qk  g 2  g 2  1 pmod pq because the order of g modulo p is
p
1.




For (2), by (1) we can get p ab q  pabq 2  a 2 b 2  p ap qp pb q pmod pq. Since both sides
p 1 p 1 p 1

p
can only take values in t
1, 0, 1u, they must be equal. 

We characterise those primes for which
1 or 2 is a quadratic residue by the follow

proposition. We remind the reader that if n is an odd integer, then n
1 is always a
multiple of 2 and n2
1 is always a multiple of 8 (we have seen this fact in the proof of
Proposition 3.6).

Proposition 4.5. Let p be an odd prime.

#


1  p
1q
 p 1 1 if p  1 pmod 4q
(1)

1 if p 
1 pmod 4q.
2
p
#

2
p  1 pmod 8q
(2)  p
1q p2 1
 1 if

1 p  3 pmod 8q.
8
p if

Proof. Part (1) follows immediately from of Proposition 4.4 (1). There are different ways
of proving part (2). We provide an elementary proof here. Consider the following p
2 1
40
congruences
p
1  1  p
1q1 pmod pq
2  2  p
1q2 pmod pq
p
3  3  p
1q3 pmod pq
..
.
p
1 p
1
2
or p

2
 p
2 1  p
1q
pmod pq.
p 1
2

The pattern on the left-hand side: for every i  1, 2,    , p
2 1 , we put i if i is even, or
p
i if i is odd. So the left-hand side of the above congruences has exhausted all even
numbers between 1 and p. We multiply all of the congruences together to get

p
1  p
2 1
2  4  6    pp
3q  pp
1q  !  p
1q1 2
pmod pq.
2
Therefore we have
 

p
1 p
1 p2
1
2
p 1
2  2
!
2
!  p
1q 8 pmod pq.
Since p does not divide
!, we can cancel it on both sides to get
p 1
2



2
p 1
2  p
1q p2 1
8 pmod pq.
By Proposition 4.4 (1) we get

2

p
 p
1q p2 1
8

since they both take values 1 or
1.

Finally, if p  1 pmod 8q, then we can write p  8k  1 for some k P Z. Hence
p 2
1
8
 8k2  2k is an2 even number. If p  3 pmod 8q, then we can write p  8k  3 for
some k P Z. Hence p 8
1  8k 2  6k 1 is an odd number. This proves
#

if p  1 pmod 8q
p
1q p2 1
 1

1 p  3 pmod 8q,
8

if
as desired. 

Finally, we state the law of quadratic reciprocity. This is a deep result which has great
influence in the modern number theory. The proof will be postponed to next part.

Theorem 4.6 (Law of Quadratic Reciprocity). Let p and q be distinct odd primes. Then

p
q p
1 q
1
 p
1q 2  2 .
q p
41
Remark 4.7. We can state the quadratic reciprocity in a slightly different way: for odd
primes p and q, we have p pq q  p pq q. We take the positive sign if either p or q is congruent
to 1 modulo 4, or the negative sign if both p and q are congruent to
1 modulo 4.

The law of quadratic reciprocity can be used in conjunction with the previous propositions
to compute the Legendre symbol. Very roughly speaking, given a Legendre symbol p ap q,
after replacing a by the remainder of a modulo p if possible, we use the prime factorisation
of a to write p ap q as the product of several Legendre symbols, some of which can be
immediately evaluated. Then we use the quadratic reciprocity for the other factors and
repeat this process. We give an example:

Example 4.8. We calculate p 101 79

q. Since 101  1 pmod 4q we have p 101 79
q  p 101
79
q  p 2279 q.
Then we factor as p 22
79
q  p 792 qp 1179 q. Now 79  7 pmod 8q, thus p 792 q  1. Since both
11 and 79 are congruent to 3 modulo 4 we have p 79 11
q 
p 7911 q 
p 112 q. Finally 11  3
pmod 8q implies that p 112 q 
1. Therefore p 101 79
q  1; i.e. 79 is a quadratic residue modulo
101. Indeed, we can check 33  79 pmod 101q.
2

42