78 CHAPTER 7

The Law of Quadratic Reciprocity

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?

QUADRATIC RECIPROCITY 79

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

.

Start Free Trial

No credit card required