Chinese Remainder Calculator
Solve systems of simultaneous linear congruences using the Chinese Remainder Theorem.
System of Congruences
x ≡ aᵢ (mod mᵢ)
x ≡
(mod
)
x ≡
(mod
)
x ≡
(mod
)
Algorithm
1. Compute M = m₁ × m₂ × ... × mₖ
2. For each i: Mᵢ = M / mᵢ
3. Find yᵢ such that Mᵢyᵢ ≡ 1 (mod mᵢ)
4. Solution: x = Σ aᵢMᵢyᵢ (mod M)
Solution
x ≡ 23
(mod 105)
General Solution
x = 23 + 105k
where k is any integer
Calculation Steps
| aᵢ | mᵢ | Mᵢ | yᵢ |
|---|---|---|---|
| 2 | 3 | 35 | 2 |
| 3 | 5 | 21 | 1 |
| 2 | 7 | 15 | 1 |
Verification
23 mod 3= 2 = 2
23 mod 5= 3 = 3
23 mod 7= 2 = 2