Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath 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)   

 

Quadratic Reciprocity

    ( 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),

 

Internet references

Mathworld: Legendre Symbol, Quadratic Residue 

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.