Solving Linear Congruences
You'll learn how to solve equations of the form ax ≡ b (mod n) by applying the gcd condition and modular inverses.
What Are Linear Congruences?
A linear congruence is an equation like ax ≡ b (mod n), where you're looking for all values of x that satisfy the relationship. Think of it as solving ax = b, but in the world of modular arithmetic—where numbers "wrap around" at n.
The Key Question: Does a Solution Exist?
Not every linear congruence has a solution. The solvability condition is:
A solution exists if and only if gcd(a, n) divides b.
If gcd(a, n) = d and d divides b, then there are exactly d solutions modulo n.
How to Solve
Case 1: gcd(a, n) = 1
When a and n are relatively prime, the congruence has a unique solution modulo n. Simply find the modular inverse of a (call it a⁻¹) and multiply both sides:
x ≡ a⁻¹b (mod n)
Example: Solve 7x ≡ 3 (mod 10)
Since gcd(7, 10) = 1, we find 7⁻¹ ≡ 3 (mod 10) using the extended Euclidean algorithm. Then x ≡ 3 · 3 ≡ 9 (mod 10).
Case 2: gcd(a, n) = d > 1
If d divides b, divide the entire congruence by d:
(a/d)x ≡ (b/d) (mod n/d)
Now gcd(a/d, n/d) = 1, so solve as in Case 1. The solution will give you one value, and you'll have d distinct solutions modulo n.
Example: Solve 6x ≡ 9 (mod 15)
gcd(6, 15) = 3, and 3 divides 9 ✓. Simplify: 2x ≡ 3 (mod 5). Find 2⁻¹ ≡ 3 (mod 5), so x ≡ 9 ≡ 4 (mod 5). The three solutions mod 15 are: 4, 9, 14.
Key Takeaway: Linear congruences ax ≡ b (mod n) are solvable when gcd(a, n) divides b; use modular inverses to find solutions.