76 CHAPTER 7

Now you really need to be told there is a pattern before you will

spot it. The answer is:

3

p

=

⎧

⎪

⎪

⎪

⎪

⎨

⎪

⎪

⎪

⎪

⎩

1ifp ≡ 1 (mod 12)

−1ifp ≡ 5 (mod 12)

−1ifp ≡ 7 (mod 12)

1ifp ≡ 11 (mod 12).

We would like to go a bit further along. There is no point in

computing

4

p

,becausex

2

− 4 ≡ 0 always has two solutions.

EXERCISE: What are the two solutions of x

2

− 4 ≡ 0(modp)?

SOLUTION: One part is easy: x ≡ 2(modp)isasolution.The

other solution may be more difﬁcult to spot. You need to recall

our observation from earlier that the two elements of S(F

p

)

will add up to p. Sure enough, you can try plugging p − 2into

x

2

− 4, and (p − 2)

2

− 4 ≡ (−2)

2

− 4 ≡ 0(modp). Or, in terms

of F

p

, we can just say that the two solutions are 2 and −2.

Remember that when we count solutions, we are counting them

as elements of F

p

, so that all possibilities that are congruent modulo

p count as just one solution. For instance, if p = 7, then 2

2

≡ 9

2

≡

16

2

≡−5

2

≡−12

2

... (mod 7), but that is just a single solution to

the equation x

2

− 4 = 0inF

7

.

When Is 5 a Square mod p? (Will This Go On Forever?)

Now we try a = 5:

EXERCISE: Compute

5

p

for all odd primes under 100.

QUADRATIC RECIPROCITY 77

SOLUTION: Now we work out that

5

p

= 1whenp = 11, 19,

29, 31, 41, 59, 61, 71, 79, and 89, and

5

p

=−1whenp = 3,

7, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, and 97.

Perhaps you are starting to spot the pattern. This would be much

easier if we used all primes up to 1,000. The difﬁculty of spotting

the pattern is eased slightly because p = 5, so you can look at the

last digit of each prime on each list, and use that to guide your

guess. One pattern is that

5

p

=

⎧

⎪

⎪

⎪

⎪

⎨

⎪

⎪

⎪

⎪

⎩

1ifp ≡ 1(mod5)

−1ifp ≡ 2(mod5)

−1ifp ≡ 3(mod5)

1ifp ≡ 4(mod5).

That answer is misleading. The form of the answer that we will ﬁnd

most helpful

5

is that

5

p

=

⎧

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎨

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎩

1ifp ≡ 1 (mod 20)

−1ifp ≡ 3 (mod 20)

−1ifp ≡ 7 (mod 20)

1ifp ≡ 9 (mod 20)

1ifp ≡ 11 (mod 20)

−1ifp ≡ 13 (mod 20)

−1ifp ≡ 17 (mod 20)

1ifp ≡ 19 (mod 20).

5

We will see later in this chapter th at we want the modulus in these patterns always to

be a multiple of 4.

Get *Fearless Symmetry* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.