Chinese Remainder Theorem Calculator
Solve systems of simultaneous linear congruences using the Chinese Remainder Theorem.
System of Congruences
x = a_i (mod m_i)
x =
(mod
)
x =
(mod
)
x =
(mod
)
CRT Requirements
- All moduli must be pairwise coprime
- gcd(m_i, m_j) = 1 for all i != j
- Solution is unique modulo M = m1 * m2 * ... * mk
Solution
x = 23
(mod 105)
General Solution
x = 23 + 105k, where k is any integer
Calculation Steps
| a_i | m_i | M_i | y_i |
|---|---|---|---|
| 2 | 3 | 35 | 2 |
| 3 | 5 | 21 | 1 |
| 2 | 7 | 15 | 1 |
M = 105, M_i = M/m_i, y_i = M_i^(-1) mod m_i
Verification
23 mod 3= 2 = 2
23 mod 5= 3 = 3
23 mod 7= 2 = 2