Solving Quadratic Congruences

Number Theory · Axiom Academy

LESSON Solving Quadratic Congruences Methods for solving x² ≡ a (mod p) when a is a quadratic residue 1. Special Case: p ≡ 3 (mod 4) When the prime p satisfies p ≡ 3 (mod 4), there's a beautiful closed-form solution. This case occurs for primes like 3, 7, 11, 19, 23, 31, and so on. Why it works: Since p ≡ 3 (mod 4), we can write p = 4k + 3 for some integer k. Then (p+1)/2 = 2k + 2, which is an integer. Let's verify that x = ±a^((p+1)/4) is indeed a solution. Since 7 ≡ 3 (mod 4), we use x = ±2^((7+1)/4) = ±2² = ±4 ≡ ±4 (mod 7). Check: 4² = 16 ≡ 2 (mod 7) ✓ and 3² = 9 ≡ 2 (mod 7) ✓ 2. Tonelli-Shanks Algorithm: General Case For primes where p ≡ 1 (mod 4), we need the more sophisticated Tonelli-Shanks algorithm. This works for any odd prime p and any quadratic residue a. The algorithm uses a quadratic non-residue to systematically adjust a candidate solution until we obtain the correct square root. We write p - 1 = 2^s · q where q is odd, then iteratively reduce the "order" of our candidate. The algorithm maintains an invariant: at each step, we have a value whose square equals a times a power of our non-residue. We halve the exponent of the non-residue at each iteration. 3. Tonelli-Shanks: Detailed Steps Let's break down the complete algorithm for solving x² ≡ a (mod p): Factorize p - 1: Write p - 1 = 2^s · q where q is odd Find non-residue n: Choose n such that (n|p) = -1 Initialize: Set M = s, c = n^q, t = a^q, R = a^((q+1)/2)

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