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

) = ∅.

What about S(F

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

)

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

Start Free Trial

No credit card required