Q: Solve 6x ≡ 9 (mod 15). gcd(6,15) = 3, and 3|9: solvable! Divide by 3: 2x ≡ 3 (mod 5). Inverse of 2 mod 5 is 3 (2×3 = 6 ≡ 1). x ≡ 3×3 = 9 ≡ 4 (mod 5). Solutions mod 15: x = 4, 9, 14 (add 15/3 = 5!). Three solutions!