Chinese Remainder Theorem Calculator
Given three congruences x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), x ≡ a₃ (mod n₃) with pairwise coprime moduli, the Chinese Remainder Theorem guarantees a unique solution modulo N = n₁·n₂·n₃. Enter the remainders and moduli to find it with full step-by-step working.
x ≡ 23 (mod 105) — unique solution modulo N = 105
Compute N = n₁ × n₂ × n₃
Compute partial products Nᵢ = N / nᵢ
Find modular inverses Mᵢ = Nᵢ⁻¹ (mod nᵢ)
Compute x = Σ aᵢ · Nᵢ · Mᵢ (mod N)
Smallest non-negative solution
- 1
Product of moduli N = n₁ × n₂ × n₃
3 × 5 × 7 = 105 - 2
Weighted sum Σ aᵢ · Nᵢ · Mᵢ
2·35·2 + 3·21·1 + 2·15·1 = 233Nᵢ = N/nᵢ; Mᵢ is the modular inverse of Nᵢ (mod nᵢ) found via the extended Euclidean algorithm. - 3
Smallest non-negative solution x = sum mod N
233 mod 105 = 23
How does this calculator work?
Given x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), x ≡ a₃ (mod n₃) with pairwise coprime n₁, n₂, n₃: compute N=n₁n₂n₃, partial products Nᵢ=N/nᵢ, inverses Mᵢ=Nᵢ⁻¹ mod nᵢ (via extended Euclidean), then x = (Σ aᵢNᵢMᵢ) mod N. Unique solution modulo N.
Formula
How this is calculated
The Chinese Remainder Theorem (CRT) states that if the moduli n₁, n₂, …, nₖ are pairwise coprime (every pair shares no common factor other than 1), then the system of congruences x ≡ aᵢ (mod nᵢ) has a unique solution modulo N = n₁·n₂·…·nₖ.
The constructive proof gives the algorithm directly. First compute N = n₁·n₂·n₃ and the partial products Nᵢ = N/nᵢ. Each Nᵢ is then invertible modulo nᵢ (because gcd(Nᵢ, nᵢ) = 1 by coprimality) — the modular inverse Mᵢ = Nᵢ⁻¹ mod nᵢ is found using the extended Euclidean algorithm. The solution is x = (Σ aᵢ·Nᵢ·Mᵢ) mod N. Any integer of the form x + k·N (k ∈ ℤ) is also a solution.
If the moduli are not pairwise coprime, a solution may or may not exist, and this version of the algorithm does not apply — the calculator will flag the error. The extended Euclidean algorithm runs in O(log min(a,b)) and handles all values up to JavaScript's safe integer limit (2⁵³−1).
Frequently asked questions
Two numbers are coprime if their greatest common divisor (GCD) is 1. "Pairwise coprime" means every pair of moduli must be coprime: gcd(n₁, n₂) = 1, gcd(n₁, n₃) = 1, and gcd(n₂, n₃) = 1. For example, 3, 5, 7 are pairwise coprime; 4, 6, 5 are not (gcd(4,6) = 2).
CRT appears in cryptography (RSA key generation and fast modular exponentiation), computer architecture (residue number systems for parallel arithmetic), competitive programming, and pure number theory. Historically it was used in China to count troops in units.
Yes — the calculator automatically normalises each remainder aᵢ to the range [0, nᵢ − 1] using aᵢ mod nᵢ before solving. Negative inputs are handled correctly.
Also known as
TG we-Calculate Editorial Team. (2026). Chinese Remainder Theorem Calculator [Online calculator]. TG we-Calculate. https://we-calculate.com/calculator/chinese-remainder-calculator
TG we-Calculate Editorial Team. "Chinese Remainder Theorem Calculator." TG we-Calculate. 2026. https://we-calculate.com/calculator/chinese-remainder-calculator.
TG we-Calculate Editorial Team, "Chinese Remainder Theorem Calculator," TG we-Calculate, 2026. [Online]. Available: https://we-calculate.com/calculator/chinese-remainder-calculator
@misc{wecalculate_chinese_remainder_calculator, title = {Chinese Remainder Theorem Calculator}, author = {{TG we-Calculate Editorial Team}}, howpublished = {\url{https://we-calculate.com/calculator/chinese-remainder-calculator}}, year = {2026}, note = {TG we-Calculate} }
Did this calculator help you?