Quadratic Residue

    (1) Explain why it suffices to know when is solvable when trying to solve quadratic congruences.

    (2) Define quadratic residues, the Legendre symbol, and determine all quadratic residues of 13 and 17.
    
    (3) Use the quadratic residues for 13 and 17 to state and use Euler's Criterion.

    (4) Quadratic characters of and 2.

    (5) Law of Quadratic Reciprocity with examples.

Solving Quadratic Congruences

    Consider the congruence



where is an odd prime and Inspired by completing the square, we have











Let and then we have a simplified version of the original namely;



Here is an example which illustrates how to take advantage of this.

Quadratic Residue

Definition (Quadratic Residue) Let   be a positive integer with     
    
    (i) If has a solution then is a quadratic residue of
    
    (ii) If does not have solution then is a quadratic non-residue of
        

Example (Quadratic Residue) Determine the quadratic residues of

    Solution. We compute the squares of the positive integers less than 13 namely: and Therefore, the quadratic residues of 13 are and the quadratic non-residues of 13 are

Example (Quadratic Residue) Determine the quadratic residues of

    Solution. We compute the squares of the positive integers less than 13 namely: and Therefore, the quadratic residues of 17 are and the quadratic non-residues of 17 are

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 non-residues of 13 are We find that





Since the quadratic residues of 17 are and the quadratic non-residues of 17 are We find that

Euler's Criterion

Notice the relationship the quadratic residues and quadratic non-residues of 13 satisfies:





So for each of these we have

And again for





So for each of these we have   

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

Quadratic Characters

Example (Quadratic Character of -1) If is an odd prime, then

Law of Quadratic Reciprocity

Proposition (Quadratic Reciprocity - Gauss's Form) Let and be distinct odd primes, then

Proposition (Quadratic Reciprocity - Legendre's Form) Let and be distinct odd primes, then

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
    

Example (Quadratic Reciprocity) Evaluate the following Legendre symbols

(a)

    Solution. Since we have Since and we have




(b)

    Solution. To evaluate we note that So we have and since we see that



Finally since and we have




(c)

    Solution.  Since we have



So we break these down into cases as follows

  since

  since

  since

  since

  since

  since

  since

since
and

since

since

















Therefore,

• print this page
• pages linking here
• related pages