This web page gives some elmentary definitions and results concerning quadratic residues. They are needed to help with the proof of Legendre's theorem about numbers that are the sum of 3 squares.
Let p be an odd prime. Then:
Definition: If a2≡q modulo m, q is a quadratic residue modulo m.
Definition: If q is not a quadratic residue modulo m, q is a quadratic nonresidue modulo m.
Definition: The Legendre symbol (a\m) is defined by:
| (a\m) = | 0 | if a≡0 modulo m |
| 1 | if a is a quadratic residue modulo m | |
| -1 | if a is a quadratic nonresidue modulo m |
Theorem (Euler's criterion): If p is an odd prime and a is coprime to p, (a\p)=1 iff a(p-1)/2≡1 modulo p.
(a\p)≡a(p−1)/2 modulo p.
| (−1\p)= | 1, if p≡1 modulo 4 |
| −1, if p≡3 modulo 4 |
| (q\p)= | (p\q), | if p≡1 or q≡1 modulo 4 |
| −(p\q), | if p≡3 and q≡3 modulo 4 |
Definition: The absolute least residue of a modulo n is that b where a≡b modulo n, and −n/2<b≤n/2.
Thus the absolute least residue of a modulo n is the nearest that maths gets to an actual modulo-operator. Note that the absolute value is minimised, and that the value is negative if necessary.