The classic puzzle – “a number leaves remainder 2 when divided by 3, 3 when divided by 5 and 2 when divided by 7” – was posed by Sunzi in the 3rd century. Today the theorem speeds up RSA decryption and underlies many algorithms in computer arithmetic.
How to use the Chinese Remainder Theorem Calculator
- Number of congruences
- x ≡ a₁
- (mod n₁)
- x ≡ a₂
- (mod n₂)
- x ≡ a₃
- (mod n₃)
- x ≡ a₄
- (mod n₄)
- x ≡ a₅
- (mod n₅)
- x ≡ a₆
- (mod n₆)
Everything is calculated in your browser, so results appear instantly and nothing you type is sent to a server.
How it works
For each congruence the calculator computes Mᵢ = N/nᵢ and its inverse modulo nᵢ with the extended Euclidean algorithm, then combines the terms. The moduli must be pairwise coprime.
Formula
x ≡ Σ aᵢ · Mᵢ · (Mᵢ⁻¹ mod nᵢ) (mod N), Mᵢ = N / nᵢ
Worked example
Inputs — Number of congruences: 3; x ≡ a₁: 2; (mod n₁): 3; x ≡ a₂: 3; (mod n₂): 5; x ≡ a₃: 2; (mod n₃): 7.
Results — Solution = x ≡ 23 (mod 105); Smallest non-negative x = 23; N = product of the moduli = 105; Steps = x ≡ 2 (mod 3): Mᵢ = 35, inverse of Mᵢ mod 3 = 2, term = 140
x ≡ 3 (mod 5): Mᵢ = 21, inverse of Mᵢ mod 5 = 1, term = 63
x ≡ 2 (mod 7): Mᵢ = 15, inverse of Mᵢ mod 7 = 1, term = 30
Sum mod 105 = 23.
Key terms
- Congruence
- a ≡ b (mod n) means n divides a − b.
- Pairwise coprime
- Every pair of numbers has gcd 1.
Frequently asked questions
What does the theorem say?
If the moduli are pairwise coprime, the system has exactly one solution modulo their product.
What if the moduli share a factor?
A solution may or may not exist; the calculator asks for pairwise coprime moduli.
What is the classic example?
x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) gives x = 23.
Where is it used?
In RSA (CRT decryption), calendars, error-correcting codes and fast big-number arithmetic.