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

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