# document.write (document.title)

 Math Help > Number Theory > Theorems > Legendre Symbol

### Legendre symbol

 If n is an integer and p is an odd prime, then ( n p ) is { 0 if n≡0 (mod p), 1 if n is a square (mod p), and -1 otherwise
 From Euler's Criterion, we can see that ( n p ) = n(p-1)/2.
 if n=1, or any square smaller than p, then ( n p ) = 1,

### Properties of the Legendre symbol

 ( ab p ) = ( a p )( b p ) for all integers a,b, because the Legendre symbol is "completely multiplicative".
 ( a p ) = ( b p ) whenever a≡b (mod p)
 ( 1 p ) = 1.  In fact, ( n p ) = 1 whenever n is a non-zero square (mod p)
 ( −1 p ) = (-1)(p-1)/2, or { 1 if p≡1 (mod 4), -1 if p≡-1 (mod 4),

These first four properties come directly from Euler's Criterion.  In general,

 ( a p ) = a(p-1)/2 (mod p)

 ( p q ) = ( q p ) (-1)[(p-1)/2][(q-1)/2], whenever p and q are both prime.  This can be simplified to
 ( p q ) = ( q p ) (-1)(p-1)(q-1)/4, whenever p and q are both prime.

Another way to express this is

 ( p q ) = ( q p ) , for primes p,q, and either p=4k+1 for some k, or q=4k+1 for some k.
 ( p q ) = (-1) ( q p ) , for primes p,q, and p=4k+3 for some k, and q=4k+3 for some k.

### Examples of Legendre Symbol

 ( 2 p ) = 2(p-1)/2 (mod p), or ( 2 p ) = (-1)(p^2-1)/2 (mod p), or { 1 if p≡±1 (mod 8), -1 if p≡�3 (mod 8),

which is proved using Gauss' Lemma.

 ( 3 p ) = 3(p-1)/2 (mod p), or { 1 if p≡±1 (mod 12), -1 if p≡�5 (mod 12),

which is proved using Quadratic Reciprocity.

 ( 3 p ) = ( p 3 ) if p≡1 (mod 4), and ( 3 p ) = (-1) ( p 3 ) if p≡-1 (mod 4).

Since 1 is the only quadratic residue (mod 3), and -1 is the only quadratic non-residue (mod 3), the result follows.  The next two examples are done the same way.  Note that the case of 5, 13, etc. are easier because, for example,

 ( 5 p ) = ( p 5 ) for all values of p, since 5≡1 (mod 4).
 ( 5 p ) = 5(p-1)/2 (mod p), or { 1 if p≡±1 (mod 5), -1 if p≡�2 (mod 5),
 ( 6 p ) = 6(p-1)/2 (mod p), or { 1 if p≡±1,5 (mod 24), -1 if p≡�7,11 (mod 24),
 ( 7 p ) = 7(p-1)/2 (mod p), or { 1 if p≡±1,3,9 (mod 28), -1 if p≡�5,11,13 (mod 28),
 ( -2 p ) = -2(p-1)/2 (mod p), or { 1 if p≡1,3 (mod 8), -1 if p≡-1,3 (mod 8),
 ( -3 p ) = -3(p-1)/2 (mod p), or { 1 if p≡1 (mod 6), -1 if p≡-1 (mod 6),
 ( -5 p ) = -5(p-1)/2 (mod p), or { 1 if p≡1,3,7,9 (mod 20), -1 if p≡-1,3,7,9 (mod 20),
 ( -6 p ) = -6(p-1)/2 (mod p), or { 1 if p≡1,5,7,11 (mod 24), -1 if p≡-1,5,7,11 (mod 24),
 ( -7 p ) = -7(p-1)/2 (mod p), or { 1 if p≡1,9,11,15,23,25 (mod 28), -1 if p≡-1,9,11,15,23,25 (mod 28),

### Related pages in this website

Euler's Criterion — a way to tell if a number is a quadratic residue, i.e. a square, (mod p): If p is an odd prime, and a is an integer coprime to p, then a is a quadratic residue (mod p) iff a(p-1)/2 ≡ 1 (mod p)

 Jacobi symbol — ( a n ) , where a is any integer, and n is a positive integer greater than 2, an extension of the Legendre symbol.
 Kronecker symbol — ( a n ) , where a and n are any integers, an extension of the Jacobi symbol.

Quadratic Residues - Modular Arithmetic and the Quadratic Equations ax^2+bx+c=0, a(p-1)/2 ≡�1 (mod P), a is a quadratic residue (mod p) iff a^((p-1)/2)≡1 (mod p), Legendre Symbol, Prime of form 4k+1 is a "Pythagorean Prime" because it can be expressed as the sum of two squares, Legendre (2/p) = (p^2-1)/8 (mod p) attributed to Gauss, quadratic reciprocity law, computing sqrt (mod p) using Tonelli-Shanks algorithm

The webmaster and author of this Math Help site is Graeme McRae.