Quadratic Residues

Definition

Letbe an odd prime andIf the congruence has a solution then is said to be a quadratic residue ofotherwise it is a quadratic non – residue of

Theorem

For any odd primethere are exactlyquadratic residues ofand exactly quadratic non – residues ofThe quadratic non – residues are congruentto

Proof: The quadratic residues ofare the integerswhich result from the evaluation ofSincetheseintegers fall intopairs

Hence each quadratic residue ofis congruentto one of

None of this set are congruentsince ifwith then dividesdividesordividesbut sincewe havesodoes not dividethendividesbut soHence there arequadratic residues andquadratic non – residues.

0 is excluded as a quadratic residues despite the fact that 0 is a square. This enables many theorems to be expressed simply. The value 0 can be treated as a special case.

Example: Solve

Multiply both sides by 8 to obtainand complete the square to obtainTake 4 from both sides to give

Thenor