Squares Modulo n

Number Theory · Axiom Academy

Not every number can be a perfect square mod n. Let's discover which ones can! Let's start simple. Pick a number and see what happens when you square it modulo 8. Step 2: Find All Possible Squares Now let's systematically check all possible remainders. Which remainders mod 8 can be perfect squares? Does every modulus have the same pattern? Let's explore different values of n and see what happens. Step 4: The Prime Number Secret Prime numbers have a special property. For a prime p, exactly half of the non-zero remainders are quadratic residues! Let's synthesize what we've discovered about quadratic residues modulo n. A number a is a quadratic residue modulo n if there exists some integer x such that x² ≡ a (mod n). In other words, a can be "written as a perfect square" when working modulo n. 1. Not every remainder modulo n is a quadratic residue 2. 0 and 1 are always quadratic residues 3. For prime p, exactly (p+1)/2 remainders are quadratic residues 4. The pattern depends on the factorization of n Quadratic residues are fundamental to: • Cryptography (RSA, Rabin cryptosystem) • Primality testing and factorization • Solving quadratic equations modulo n • The law of quadratic reciprocity

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