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

QUADRATIC RECIPROCITY 69
we can restrict our attention to odd primes. For the remainder of
this chapter, assume that p is an odd prime.
When Is 1 a Square mod p?
We return to x
2
+ 1, and try various values of p. By trial-and-
error, we find that S(F
3
) = ,andS(F
5
) ={2, 3},andS(F
7
) = ,and
S(F
11
) = ,andS(F
13
) ={5, 8}. Here, is the standard symbol for
the empty set.Inotherwords,“S(F
11
) = means that there is no
element in F
11
whose square equals 1. Or, equivalently, whatever
integer b you take, you will never find that b
2
+ 1 is evenly divisible
by 11.
EXERCISE: Why does S(F
3
) = ,andS(F
5
) ={2, 3}?
SOLUTION: To compute S(F
3
), we substitute the three
elements of F
3
into the polynomial x
2
+ 1, and see if we ever
get 0 modulo 3:
0:0
2
+ 1 = 1 ≡ 0(mod3)
1:1
2
+ 1 = 2 ≡ 0(mod3)
2:2
2
+ 1 = 5 ≡ 0(mod3)
We have now tried out everything in F
3
, and nothing worked,
so S(F
3
) = .
What about S(F
5
)? We try the five elements of F
5
and see
what happens:
0:0
2
+ 1 = 1 ≡ 0(mod5)
1:1
2
+ 1 = 2 ≡ 0(mod5)
2:2
2
+ 1 = 5 0(mod5)
3:3
2
+ 1 = 10 0(mod5)
4:4
2
+ 1 = 17 ≡ 0(mod5)
So that is how to see that S(F
5
) ={2, 3}.
70 CHAPTER 7
We can observe that if S(F
p
) = , then the two elements in S(F
p
)
adduptop.
EXERCISE: Suppose that S(F
p
) ={n, m}. Show that
n + m = p.
SOLUTION: Suppose that we know that S(F
p
) contains the
number n. This means that n
2
+ 1 0(modp). Now, we plug
the number p n into the same polynomial x
2
+ 1. We get
(p n)
2
+ 1 (n)
2
+ 1 = n
2
+ 1 0(modp). This means
that p n is an element of S(F
p
). So the two numbers in S(F
p
)
are n and p n, and those two numbers add up to p.Because
p is odd, we know that n and p n must be unequal numbers
(one is odd and the other is even), so we really have two
different solutions.
One of the truly inspired notions in mathematics was to step
back, and not worry about the particular numbers contained in
S(F
p
). Instead, we can ask: For which primes p is S(F
p
) = ,and
for which is it not?
EXERCISE: List all of the primes under 100, and for each
odd prime on your list, decide if S(F
p
) = or not. Use
trial-and-error—and a computer, or at least a calculator, for
the larger primes.
SOLUTION: You will find that S(F
p
) = if p = 3, 7, 11, 19,
23, 31, 43, 47, 59, 67, 71, 79, and 83, and S(F
p
) = if p = 5,
13, 17, 29, 37, 41, 53, 61, 73, 89, and 97.
The amazing thing here is that there is a pattern in these two
lists! The first list consists of those primes p so that p 3(mod4),
and the second list is those primes p so that p 1 (mod 4). We will
not prove this observation in this book, but we will assume it from
now on. The proof is somewhat complicated. The theorem that we
are aiming at, called “quadratic reciprocity,” is much deeper, and its

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