Quadratic Patterns

Number Theory · Axiom Academy

Discover which numbers are perfect squares modulo primes and uncover a beautiful pattern. Let's explore what happens when we square numbers and reduce modulo a prime. Choose a prime and watch which residues appear. Let's color-code all residues modulo p. Blue for quadratic residues (squares), gray for non-quadratic residues (non-squares). How many quadratic residues are there? Let's count them for different primes and look for a pattern. Let's investigate why exactly half are quadratic residues. The key is that squaring "pairs up" numbers. A number a is a quadratic residue modulo p if there exists an x such that x² ≡ a (mod p). These are the numbers that "can be squared" in modular arithmetic. For any odd prime p, exactly (p-1)/2 of the non-zero residues are quadratic residues, and (p-1)/2 are non-quadratic residues. The pairing a² ≡ (p-a)² shows that each quadratic residue arises from exactly two squares. Since there are p-1 non-zero elements and each square produces the same result twice, we get (p-1)/2 distinct quadratic residues.

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