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 b2 is congruent to 1
mod p. Or to put it another way, if we consider the class y of b
in Zp, the integers mod p, then
we have y2=1. Thus, y is a zero of the polynomial
x2-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.