Quadratic Congruence Examples

Number Theory · Axiom Academy

EXAMPLE Quadratic Congruence Examples Learn to solve x² ≡ a (mod p) by checking quadratic residues and finding square roots Excellent work! You've completed this quadratic congruence example. Here's what we learned: Legendre Symbol Check: Before solving x² ≡ a (mod p), always verify that a is a quadratic residue using Euler's criterion: a^((p-1)/2) ≡ 1 (mod p). If it equals -1, there are no solutions. Special Case Formula: When p ≡ 3 (mod 4), finding square roots is straightforward using the formula x ≡ ±a^((p+1)/4) (mod p). This works because of the special structure of these primes. Two Solutions: Quadratic congruences modulo a prime always have either 0 or 2 solutions. If x is a solution, then -x ≡ (p - x) is also a solution. Verification: Always verify your answer by squaring it and checking that x² ≡ a (mod p). This catches computational errors and confirms your solution. For primes p ≡ 1 (mod 4), the Tonelli-Shanks algorithm is needed, which is more complex. Practice these p ≡ 3 (mod 4) cases first to build your intuition!

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