Quadratic Residues

Notes

An integer q is a quadratic reside mod n if it is congruent to a perfect square mod n, that is if there exists an integer x such that . If q is not congruent to a perfect square mod n, then it is a quadratic non residue mod n. If n is an odd prime number, then there are (n+1)/2 quadratic residues and nonresidues.