## 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

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?
2
+ 1, and try various values of p. By trial-and-
error, we ﬁnd 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 ﬁnd 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
) = .
5
)? We try the ﬁve 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
)
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
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 ﬁnd 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 ﬁrst 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.

No credit card required