When Moduli Are Not Coprime
You'll learn: How to determine whether a system of congruences has a solution when the moduli share common factors, and what extra conditions are required.
The Problem with Shared Factors
The Chinese Remainder Theorem (CRT) guarantees a unique solution to systems of congruences only when the moduli are pairwise coprime. But what if two moduli share a common factor?
Consider this system:
x ≡ 2 (mod 6)
x ≡ 5 (mod 9)
Since gcd(6, 9) = 3 ≠ 1, the standard CRT doesn't apply. We need to investigate whether this system even has a solution.
The Solvability Condition
For a system with non-coprime moduli to have a solution, the congruences must be compatible on their overlap. Specifically:
If you have:
x ≡ a (mod m)
x ≡ b (mod n)
where d = gcd(m, n), then a solution exists if and only if:
a ≡ b (mod d)
Think of it this way: Both congruences restrict x within their moduli. If those restrictions contradict each other on the "shared part" (the gcd), no number can satisfy both.
Example Check
For our system above:
- a = 2, b = 5, d = gcd(6, 9) = 3
- Check: Is 2 ≡ 5 (mod 3)?
- 2 mod 3 = 2, but 5 mod 3 = 2 ✓
Since 2 ≡ 5 (mod 3), the system is solvable. If we'd had b = 4 instead, then 2 ≢ 4 (mod 3), and no solution would exist.
When solvable, you can often combine the congruences into a single one modulo lcm(m, n) and proceed from there.
Key Takeaway: When moduli share factors, check that the remainders are congruent modulo their gcd—this compatibility condition determines whether any solution exists at all.