Quadratic Residues Summary

Number Theory · Axiom Academy

Unit 6 Review: Key concepts in quadratic congruences and computational tools Definition: An integer a is a quadratic residue modulo p (odd prime) if there exists an x such that x 2 ≡ a (mod p ) Quadratic Nonresidue: If no such x exists, then a is a quadratic nonresidue modulo p Count: For an odd prime p , there are exactly ( p -1)/2 quadratic residues and ( p -1)/2 quadratic nonresidues among 1, 2, ..., p -1 Why It Matters: Determines which quadratic congruences have solutions, fundamental to cryptography and primality testing Notation: ( a / p ) where p is an odd prime Value +1: When a is a quadratic residue mod p Value -1: When a is a quadratic nonresidue mod p Multiplicative Property: ( ab / p ) = ( a / p )( b / p ) Example: Computing the Legendre Symbol (3/11) Apply Euler's Criterion: Compute 3 (11-1)/2 = 3 5 (mod 11) Calculate Power: 3 5 = 243 ≡ 1 (mod 11) since 243 = 22 × 11 + 1 Interpret Result: Since 3 5 ≡ 1 (mod 11), we have (3/11) = 1 Conclude: Therefore, 3 is a quadratic residue modulo 11, and the equation x 2 ≡ 3 (mod 11) has solutions Main Theorem: For distinct odd primes p and q : ( p / q )( q / p ) = (-1) ( p -1)( q -1)/4 Simplified Form: If either p ≡ 1 (mod 4) or q ≡ 1 (mod 4), then ( p / q ) = ( q / p ) Both ≡ 3 (mod 4): If both p ≡ 3 (mod 4) and q ≡ 3 (mod 4), then ( p / q ) = -( q / p ) Supplement for -1: (-1/ p ) = (-1) ( p -1)/2 , so -1 is a QR mod p if and only if p ≡ 1 (mod 4)

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