QUADRATIC RECIPROCITY 75

You could stare at this list for a long time before discovering the

pattern, even when you know there is a pattern. If you did not know

there was something going on, you would have an even harder time

seeing the pattern. The answer is:

2

p

=

⎧

⎪

⎪

⎪

⎪

⎨

⎪

⎪

⎪

⎪

⎩

1ifp ≡ 1(mod8)

−1ifp ≡ 3(mod8)

−1ifp ≡ 5(mod8)

1ifp ≡ 7(mod8).

What this equation means is that if you have an odd prime p,

and you want to know whether or not 2 has two square roots in

F

p

, then you see what p is congruent to modulo 8, and look at the

corresponding line on the right-hand side of the equation to get

the value o f the Legendre symbol

2

p

.Inotherwords,

2

p

= 1

if p ≡ 1 or 7 (mod 8) and

2

p

=−1ifp ≡ 3 or 5 (mod 8). For

example, 47 ≡ 7 (mod 8), and sure enough, 7

2

≡ 2 (mod 47) and

40

2

≡ 2 (mod 47).

When Is 3 a Square mod p?

We now move on even further to a = 3, and try again:

EXERCISE: Use the list of odd primes under 100 and decide

for which of those primes the equation

3

p

= 1 holds, and for

which you have

3

p

=−1.

SOLUTION: This time, our computer tells us that

3

p

= 1

when p = 11, 13, 23, 37, 47, 59, 61, 71, 73, 83, and 97, and

3

p

=−1whenp = 5, 7, 17, 19, 29, 31, 41, 43, 53, 67, 79,

and 89.

Start Free Trial

No credit card required