## 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 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
.
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 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,
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 asfrom0to30andseewhethera
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
.
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 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.