Quadratic Residues and Non-Residues

Number Theory · Axiom Academy

LESSON Quadratic Residues and Non-Residues Understanding which numbers are perfect squares modulo n Let n be a positive integer, and let a be an integer with gcd(a, n) = 1. In other words, a is a QR mod n if a appears in the list of squares: 1², 2², 3², ..., (n-1)² when reduced modulo n. 2. Examples: QRs and NRs Modulo 7 Let's find all quadratic residues modulo 7 by computing the squares of integers from 1 to 6: Notice that the quadratic residues are 1, 2, 4 , while the non-residues are 3, 5, 6 . 3. Counting QRs Modulo a Prime For a prime p , how many quadratic residues are there modulo p ? Why? Consider the squares 1², 2², 3², ..., ((p-1)/2)². Each produces a distinct quadratic residue modulo p . Furthermore, due to symmetry (since (p-x)² ≡ x² mod p), the squares of numbers from ((p-1)/2 + 1) to (p-1) repeat the same residues.

This is the written version of the interactive lesson above. See the full Number Theory course.