O'Reilly logo

Fearless Symmetry by Robert Gross, Avner Ash

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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, finally, 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 definition 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 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
specified (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

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

Start Free Trial

No credit card required