## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

78 CHAPTER 7
You do not need to do the work, but here is the corresponding table
for a = 7:
6
7
p
=
1ifp 1 (mod 28)
1ifp 3 (mod 28)
1ifp 5 (mod 28)
1ifp 9 (mod 28)
1ifp 11 (mod 28)
1ifp 13 (mod 28)
1ifp 15 (mod 28)
1ifp 17 (mod 28)
1ifp 19 (mod 28)
1ifp 23 (mod 28)
1ifp 25 (mod 28)
1ifp 27 (mod 28).
It can be difﬁcult to see the forest for the trees here. One pattern
that remains the same from chart to chart is that when we are
computing
a
p
, the modulus in the chart is 4a. Moreover, the
charts are all symmetric. This can be expressed as follows:
THEOREM 7.2: Let a be a positive integer.
1. If p and q aretwooddprimessothatp q (mod 4a), then
a
p
=
a
q
.
2. If p and q aretwooddprimessothatp + q 0(mod4a),
then
a
p
=
a
q
.
Theorem 7.2 is a surprisingly difﬁcult statement to prove (even
if we just pick a = 3). Like most such statements, it has amazing
6
Can you explain why there is no need to try a = 6?
consequences. With it, we can ﬁnally get around to explaining the
title of this chapter, the Law of Quadratic Reciprocity:
THEOREM 7.3 (Quadratic Reciprocity): Suppose that p and
q are odd primes.
1.
1
p
=
1ifp 1(mod4)
1ifp 3(mod4).
(7.4)
2.
2
p
=
1ifp 1or7(mod8)
1ifp 3or5(mod8).
(7.5)
3. If p q 3(mod4),then
p
q
=−
q
p
. (7.6)
4. If p or q or both are 1(mod4),then
p
q
=
q
p
. (7.7)
The format of equations (7.6) and (7.7) is why the theorem is
called a reciprocity law. The numbers p and q play reciprocal roles
with respect to each other in these two equations. Although we will
not prove Theorem 7.2 in this book, the proof of (7.6) and (7.7)—
assuming the truth of Theorem 7.2—is just a complicated bit of
algebraic manipulation. Feel free to skip it if you like. Here it is:
PROOF: First, we suppose that p q 3 (mod 4). Assume
that p > q,andwritep = q + 4n.Then
p
q
=
q + 4n
q
=
4n
q
. Next, we use (7.1) from page 73 to rewrite
4n
q
as
4
q

n
q
, and because
4
q
= 1, we have now proved that
p
q
=
n
q
.

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required