Solving Linear Congruences

Number Theory · Axiom Academy

LESSON Solving Linear Congruences Master complete methods for solving ax ≡ b (mod n) using systematic techniques Before attempting to solve ax ≡ b (mod n) , we must first determine if solutions exist. If d ∤ b (d does not divide b), there are no solutions If d | b (d divides b), there are exactly d solutions modulo n 2. The Extended Euclidean Algorithm The key tool for solving linear congruences is the Extended Euclidean Algorithm, which finds integers x and y such that: Initialize: r₀ = a, r₁ = n; x₀ = 1, x₁ = 0; y₀ = 0, y₁ = 1 Iterate: While rᵢ ≠ 0: qᵢ = ⌊rᵢ₋₁ / rᵢ⌋ Result: When rᵢ = 0, then gcd(a, n) = rᵢ₋₁ with a·xᵢ₋₁ + n·yᵢ₋₁ = gcd(a, n) 3. Finding the Principal Solution Once we've confirmed solvability and computed the Extended Euclidean Algorithm, we can find the solution. Compute gcd: Use Extended Euclidean Algorithm to find d = gcd(a, n) and x₀ such that a·x₀ ≡ d (mod n) Check divisibility: If d ∤ b, report "No solution" Simplify the congruence: Divide by d to get (a/d)·x ≡ (b/d) (mod n/d) Find particular solution: x = (b/d)·x₀ (mod n/d) Normalize: Reduce x to the range [0, n/d) The principal solution is the unique solution in the range [0, n/d) . When gcd(a, n) = d > 1, there are exactly d distinct solutions modulo n. These d solutions form a complete residue system modulo n. gcd(6, 15) = 3, and 3 | 9 ✓ (solvable) Since 2·3 = 6 ≡ 1 (mod 5), we have 2⁻¹ ≡ 3 (mod 5) Principal solution: x₀ = 3·3 = 9 ≡ 4 (mod 5) All solutions: x ∈ 4, 9, 14 (mod 15)

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