74 CHAPTER 7

numbers from 0 to 6, you will ﬁnd that x

2

− 5 ≡ 0(mod7)has

no solutions, and therefore

5

7

=−1. And, ﬁnally, if you try

all seven possibilities in the congruence x

2

− 10 ≡ 0(mod7),

again you will ﬁnd that there are no solutions, so

10

7

=−1.

And that checks (7.1): 1 ·−1 =−1.

We now return to our polynomial x

2

+ 1, which corresponds

to choosing a =−1. In terms of Legendre’s notation, we have

discovered that

−1

p

=

1ifp ≡ 1(mod4)

−1ifp ≡ 3(mod4).

Before we continue, remember that if a is not divisible by p,then

a

p

is not 0. In particular,

−1

p

is never 0.

When Is 2 a Square mod p?

The next number to consider is 2. We present you with the following

challenge if y ou like computer programming—otherwise, just read

our solution:

EXERCISE: List all of the odd primes under 100, and see for

which p you have

2

p

=−1, and for which p you have

2

p

= 1.

SOLUTION: It turns out that

2

p

= 1ifp = 7, 17, 23, 31, 41,

47, 71, 73, 79, 89, and 97. On the other hand,

2

p

=−1if

p = 3, 5, 11, 13, 19, 29, 37, 43, 53, 59, 61, 67, and 83.

Start Free Trial

No credit card required