Course contentsShow
← Mathematics
Lesson 2759 of 3,12154. Number TheoryFree lesson

When Moduli Are Not Coprime

Investigate what happens when moduli share common factors and how to determine solvability conditions.

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.