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₂.