The Legendre symbol is very important in number theory. Let's define it.
Let p be an odd prime and let a be an integer that is not divisible by p. The Legendre symbol of a is denoted by (a/p). It is either 1 or -1.
To define which, consider b=a^{(p-1)/2}.
By Fermat's Little Theorem we know that b^{2} is congruent to 1
mod p. Or to put it another way, if we consider the class y of b
in Z_{p}, the integers mod p, then
we have y^{2}=1. Thus, y is a zero of the polynomial
x^{2}-1. This polynomial, being of degree two, has at most two
zeroes, so we see that y=1 or y=-1, and we define (a/p)=1 in the first case and (a/p)=-1 in the second.
It follows from the definition that we have:
Lemma 1
- If c is congruent to a mod p then
(c/p)=(a/p).
- (a/p)(b/p)=(ab/p)
The next lemma (which is easily proved) gives some useful ways to compute the Legendre symbols but first we need notation.
For an odd integer n we define
e(n)=0 if n is congruent to 1 mod 4 and e(n)=1
if n is congruent to 3 mod 4. We define w(n)=0 if
n is congruent to 1,7 mod 8 and w(n)=1 if n
is congruent to 3,5 mod 8.
Lemma 2
- (1/p)=1
- (-1/p)=(-1)^{e(p)}
- (2/p)=(-1)^{w(p)}
Gauss' quadratic reciprocity law gives an effective way to compute Legendre symbols.
Theorem: If p and q are distinct odd primes then (q/p)=(p/q)(-1)^{e(q)e(p)}.
Let's illustrate with an example.
(13/47)=(47/13) by reciprocity. Now by Lemma 1,
(47/13)=(8/13)=(2/13)^{3}. Finally, Lemma 2 tells us that (2/13)=-1. Putting it all together (13/47)=-1.