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

proof is correspondingly more complicated—we will not be giving
that proof either.
The Legendre Symbol
There is a clever bit of notation, going back to the French mathe-
matician Adrien-Marie Legendre (a contemporary of Gauss’s), that
lets us summarize what we just discovered. We will also see that
it does more than summarize; it has an important multiplicative
property (7.1) that will be interpreted in chapter 19. It is called
the Legendre symbol in his honor. Remember that we noticed that
after we select some integer a,thevarietyS(F
p
) corresponding to
the polynomial x
2
a can have 0, 1, or 2 elements. Here is how
Legendre chose to record this fact. He deﬁned the Legendre symbol
a
p
according to the following formula:
2
a
p
=
1 if the number of solutions to x
2
a 0(modp)is0.
0 if the number of solutions to x
2
a 0(modp)is1.
1 if the number of solutions to x
2
a 0(modp)is2.
Thus, what we were exploring in the previous section was
1
p
.
WARNING: The Legendre symbol
a
p
is not a divided by p.
Legendre used a fraction symbol but put in the parentheses to
remind you that it is not division but—the Legendre symbol!
3
2
See our previous footnote to see why S(F
p
) cannot have more than two elements. Also
note the following facts:
Because p is odd, b ≡ p b (mod p) unless b 0(modp).
p b ≡−b (mod p), i.e., p b =−b as elements of the ﬁeld F
p
.
So if a is a nonzero square in F
p
, then it has two unequal square roots b and b for some
b in F
p
.
3
If you leave out the horizontal bar, you get the symbol
a
p
, which is reserved for
something completely different called a binomial coefﬁcient.

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