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

Solving Two-Congruence Systems

Work through detailed examples of solving systems of two congruences with coprime moduli.

Solving Two-Congruence Systems

What you'll learn: You'll master the step-by-step process of finding solutions to systems of exactly two congruences when their moduli are coprime.

The Core Idea

When you have two congruences like:

  • x ≡ a₁ (mod m₁)
  • x ≡ a₂ (mod m₂)

where gcd(m₁, m₂) = 1, the Chinese Remainder Theorem guarantees a unique solution modulo M = m₁·m₂. While the full CRT construction works for any number of congruences, the two-congruence case is simpler and teaches the essential technique.

Working Through an Example

Let's solve:

  • x ≡ 3 (mod 5)
  • x ≡ 7 (mod 8)

Step 1: Verify coprimality. Since gcd(5, 8) = 1, we can proceed.

Step 2: Express the first congruence explicitly: x = 3 + 5t for some integer t.

Step 3: Substitute into the second congruence:

  • 3 + 5t ≡ 7 (mod 8)
  • 5t ≡ 4 (mod 8)

Step 4: Solve for t. We need the modular inverse of 5 modulo 8. Using the extended Euclidean algorithm or inspection: 5·5 = 25 ≡ 1 (mod 8), so the inverse is 5.

Step 5: Multiply both sides by 5:

  • t ≡ 5·4 ≡ 20 ≡ 4 (mod 8)

Step 6: Back-substitute: x = 3 + 5(4) = 23.

Verification: 23 ≡ 3 (mod 5) ✓ and 23 ≡ 7 (mod 8) ✓

The general solution is x ≡ 23 (mod 40), since M = 5·8 = 40.

Key Takeaway: For two coprime moduli, substitute the first congruence into the second, solve the resulting linear congruence using modular inverses, then back-substitute to find the unique solution modulo m₁·m₂.