Legendre Symbol

    

Definition (Legendre Symbol) Let be an odd prime with The Legendre symbol is defined as follows:

Example (Legendre Symbol)  Since the quadratic residues of 13 are and the quadratic nonresidues of 13 are We find that

Proposition (Euler's Criterion) Let be an odd prime and Then



    Proof. The only values for are So it suffices to consider the cases and
    If then has a solution say Then by Fermat's Little theorem,  
    


since Conversely, if then has no solution. The key idea is that we can group together the integers into pairs each with product of . Then multiplying these pairs together, and using Wilson's theorem, we have:



To see why we can do this, note that means has exactly one solution say and this must happen precisely when         

Example (Euler's Criterion) Determine and
    Solution. Since we have, by Euler's criterion,
    


and so is a quadratic nonresidue of 23. Similarly,



and so is a quadratic residue of 53.

Proposition (Properties of the Legendre Symbol) Let be an odd prime with and Then

    (i) if then
    
    (ii)  
    
    (iii)  
    
    (iv)
    
    (v) if has prime factorization



and is a prime not dividing , then
    

    
    
    Proof. (i) The congruence has a solution if and only if does because
    (ii) By Euler's Criterion we know

, and

Therefore,



Because the only values are we have, as desired.
    (iii) Since , part (ii) yields as desired.
    (iv) By (ii) and (iii): as desired.
    (v) By (iv) we have,
    
    

By (iii), we see that

    

as desired.  

• print this page
• pages linking here
• related pages

Cite this as:
Legendre Symbol
Published by Library of Math -- Online math organized by subject into topics.
Written by Smith, David A.
http://www.libraryofmath.com/legendre-symbol.html