80 CHAPTER 7

Now we use Theorem 7.2. Because p = q + 4n,wehave

p ≡ q (mod 4n), and so

n

q

=

n

p

.Becausep ≡ 3(mod4),

we have −

−1

p

= 1. Multiplying by this disguised form of

the number 1, we get

n

p

=−

−1

p

n

p

=−

−n

p

.Next,

we multiply by 1 again, this time disguised as

4

p

,toget

n

p

=−

−n

p

4

p

=−

−4n

p

. And now, ﬁnally, we’re

done: −

−4n

p

=−

p − 4n

p

=−

q

p

.

If p ≡ q ≡ 1 (mod 4), the same proof works, except that the

disguised form of the number 1 is now

−1

p

.

Finally, suppose that p ≡ 1(mod4)andq ≡ 3(mod4).

Then p + q is a multiple of 4, and now we write p + q = 4n.

We start as before:

p

q

=

4n − q

q

=

4n

q

=

4

q

n

q

=

n

q

. In exactly the same way,

q

p

=

n

p

.Now,weusethe

second piece of Theorem 7.2. Because p + q ≡ 0(mod4n), we

have

n

q

=

n

p

. Combine the pieces, and we have

p

q

=

q

p

.

Examples of Quadratic Reciprocity

Now that we have gone to such great lengths to prove Theorem 7.3,

we should show you an example or two of its use.

EXERCISE: Compute

24

31

.

SOLUTION: We mentioned above a fact that is critical in

using quadratic reciprocity to speed the computation of

QUADRATIC RECIPROCITY 81

Legendre symbols. Expressed symbolically, it is the statement

that if a ≡ b (mod p), then

a

p

=

b

p

. If you think back to

the deﬁnition of the Legendre symbol, you will see why this is

true. The symbol

a

p

tells you something about solving the

congruence x

2

≡ a (mod p). If a ≡ b (mod p), then solving

x

2

≡ a (mod p) is exactly the same as solving the congruence

x

2

≡ b (mod p).

We can start our computation of

24

31

by factoring

24 = 4 · 6. By property (7.1), we can write

24

31

=

4

31

6

31

.

We know right away that

4

31

= 1, because 4 is a perfect

square.Sowecanconcludethat

24

31

=

6

31

.

Now, factor 6 = 2 · 3, and we get

24

31

=

6

31

=

2

31

3

31

.

We use (7.5): Because 31 ≡ 7 (mod 8), we know that

2

31

= 1. So now we know that

24

31

=

3

31

.

Next, we use (7.6), because 31 ≡ 3(mod4)and3≡ 3

(mod 4), so

3

31

=−

31

3

.

Because 31 ≡ 1(mod3),weknowthat

31

3

=

1

3

,which

we know must be 1 (because 1 is a perfect square). Put all of

this together, and we have worked out that

24

31

=−1,

without solving any quadratic equations.

We now know that there is no integer a whose square leaves a

remainder of 24 when divided by 31. Of course, it would not be

82 CHAPTER 7

hard simply to check all a’sfrom0to30andseewhethera

2

≡ 24

(mod 31). But when the modulus is very big, it is much faster to

use quadratic reciprocity. If the modulus is very very big, or is not

speciﬁed (it might just be “any p” appearing in the proof of some

theorem), then we might have to use quadratic reciprocity.

Here is a medium-sized numerical example:

EXERCISE: Using the Law of Quadratic Reciprocity, compute

3,411

3,457

.

SOLUTION: Again, we start with a factorization:

3,411 = 3

2

· 379. So we have

3,411

3,457

=

9

3,457

379

3,457

=

379

3,457

.

Now, 379 ≡ 3 (mod 4) and 3457 ≡ 1 (mod 4), so we use (7.7)

and get

379

3,457

=

3,457

379

.

We continue by noticing that 3,457 ≡ 46 (mod 379), and so

3,457

379

=

46

379

=

2

379

23

379

.

We use (7.5) to compute

2

379

=−1, because 379 ≡ 3

(mod 8). So now we have the equation

3,411

3,457

=−

23

379

.

Next, we see that 23 ≡ 3 (mod 4) and 379 ≡ 3 (mod 4), and

so by (7.6) we get

−

23

379

=

379

23

.

Because 379 ≡ 11 (mod 23) we get

379

23

=

11

23

QUADRATIC RECIPROCITY 83

and then we use (7.6) again to see that

11

23

=−

23

11

=−

1

11

=−1.

So in the end, we have computed

3,411

3,457

=−1, again

without having to solve any quadratic equations.

We will return to this subject later, after we have explained

more about representations, and we will explain why the Law of

Quadratic Reciprocity can be viewed as an example in representa-

tion theory. We will also present some other examples of reciprocity

laws and explain why they are indeed reciprocity laws. Finally, we

will give some instances of how reciprocity laws can be used to

study solution sets of more complicated Diophantine equations.

This page intentionally left blank

Start Free Trial

No credit card required