Chinese Remainder Theorem Calculator
Solve a system of simultaneous congruences with pairwise coprime moduli via CRT.
About Chinese Remainder Theorem Calculator
The Chinese Remainder Theorem (CRT) states that if m₁, m₂, …, mₖ are pairwise coprime, then the system x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), …, x ≡ aₖ (mod mₖ) has a unique solution modulo M = m₁×m₂×…×mₖ. The solution is constructed by computing partial products Mᵢ = M/mᵢ, finding their modular inverses yᵢ (mod mᵢ), and summing x = Σ aᵢ×Mᵢ×yᵢ (mod M).
Formula
CRT solution
x = Σ(aᵢ × Mᵢ × yᵢ) mod M, where Mᵢ = M/mᵢ and yᵢ = Mᵢ⁻¹ mod mᵢ
- aᵢ
- Remainder for ith congruence
- mᵢ
- ith modulus
- M
- Product of all moduli
- yᵢ
- Modular inverse of Mᵢ mod mᵢ
Worked example
With the default values below, Chinese Remainder Theorem Calculator returns Smallest Positive Solution of 23. Change any input above and every figure here is recalculated in your browser.
Inputs used
- Remainders (comma-separated)
- 2, 3, 2
- Moduli (comma-separated)
- 3, 5, 7
Results
- Smallest Positive Solution
- 23
- Combined Modulus (M)
- 105
- General Solution
- x ≡ 23 (mod 105)
Step by step
- 1Product of moduli
- 2Term 1
- 3Term 2
- 4Term 3
- 5Sum mod M= 23
- 6General solution
Assumptions and limits
- The result is derived only from the 2 inputs listed above. Anything not among them is not part of the calculation.
- In particular, this calculator does not take inflation, tax, fees or charges or compounding frequency into account.
- Figures are rounded for display to whole numbers, so totals built from several rounded parts can differ slightly from the unrounded arithmetic.
How these calculators are built and tested is described on the Methodology page. If a figure looks wrong, please report it.
Frequently Asked Questions
What does 'pairwise coprime' mean?
Every pair of moduli must have gcd = 1. For example, {3, 5, 7} is pairwise coprime because gcd(3,5)=1, gcd(3,7)=1, and gcd(5,7)=1. But {4, 6, 5} fails because gcd(4,6)=2.
What if the moduli are not coprime?
The standard CRT does not apply. A generalized version exists that works when the system is consistent (each pair aᵢ ≡ aⱼ mod gcd(mᵢ, mⱼ)), but this calculator requires pairwise coprime moduli.