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

  1. If c is congruent to a mod p then (c/p)=(a/p).
  2. (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. (1/p)=1
  2. (-1/p)=(-1)e(p)
  3. (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.

Log in or register to write something here or to contact authors.