Linear Congruences

Number Theory · Axiom Academy

Solving equations of the form ax ≡ b (mod n) through existence theorems and solution methods 1. The Linear Congruence Equation This equation asks: "What values of x make ax congruent to b modulo n?" In other words, for which x does n divide (ax - b)? Key Insight: Unlike linear equations in ordinary arithmetic, linear congruences may have no solutions, exactly one solution class, or multiple solution classes modulo n. This theorem tells us two crucial facts: Existence: Solutions exist precisely when gcd(a, n) divides b Number of Solutions: When solutions exist, there are exactly d = gcd(a, n) distinct solutions modulo n When d = gcd(a, n) divides b, we can simplify the congruence by dividing through by d: After simplification, we have a congruence where the coefficient and modulus are coprime. This is the key to finding a unique solution class. Once we have a simplified congruence ax ≡ b (mod n) with gcd(a, n) = 1, we have two main methods to find the solution: Since gcd(a, n) = 1, the element a has a multiplicative inverse modulo n. We find a⁻¹ such that: Then multiply both sides of ax ≡ b (mod n) by a⁻¹: Use the Extended Euclidean Algorithm to find integers s and t such that: Multiply by b: abs = gcd(a,n) = 1, so abs ≡ 1 (mod n), meaning sb ≡ a⁻¹b (mod n) Then x ≡ sb (mod n) is the solution. When the original congruence ax ≡ b (mod n) has d = gcd(a, n) > 1 and d | b, we found one solution x₀ to the simplified equation. The complete solution set consists of d solutions:

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