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

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