2
3
15
1
1
8
15
2
3
2
3
15
1
1
8
15
2
3
The Chinese Remainder Theorem (CRT) Calculator solves systems of simultaneous linear congruences. Given two congruences $$x \equiv a_1 \pmod{m_1}$$ and $$x \equiv a_2 \pmod{m_2}$$ where $$\gcd(m_1, m_2) = 1$$, the CRT guarantees a unique solution modulo $$M = m_1 \cdot m_2$$.
The Chinese Remainder Theorem is one of the oldest results in number theory, appearing in the 3rd-century Chinese mathematical text Sunzi Suanjing (孙子算经). The original problem asks: "Find a number that leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7." The theorem was later generalized by mathematicians including Euler and Gauss, who incorporated it into his systematic treatment of congruences in Disquisitiones Arithmeticae (1801).
The formal statement is elegant: if $$m_1, m_2, \ldots, m_k$$ are pairwise coprime positive integers and $$a_1, a_2, \ldots, a_k$$ are any integers, then the system $$x \equiv a_i \pmod{m_i}$$ for $$i = 1, \ldots, k$$ has a unique solution modulo $$M = m_1 m_2 \cdots m_k$$. The coprimality condition is essential — without it, solutions may not exist.
The constructive proof provides an explicit formula. Define $$M_i = M / m_i$$ and find $$s_i$$ such that $$M_i s_i \equiv 1 \pmod{m_i}$$ (the modular inverse of $$M_i$$ modulo $$m_i$$). Then $$x = \sum_{i=1}^{k} a_i M_i s_i \pmod{M}$$.
Modern applications of the CRT are ubiquitous. In RSA cryptography, CRT-based decryption computes $$m^d \bmod n$$ by splitting the computation into two smaller modular exponentiations modulo $$p$$ and $$q$$ separately, achieving roughly 4× speedup. In computer arithmetic, residue number systems represent large integers as tuples of small residues for parallel computation. Secret sharing schemes like Asmuth-Bloom use CRT to split secrets into shares that can only be reconstructed when enough shares are combined.
This calculator handles systems of two congruences, finding the smallest non-negative solution and presenting the general solution family. Enter your remainders and moduli to find the simultaneous solution.
The calculator uses the constructive CRT algorithm for two congruences.
Step 1: Verify coprimality. Check that $$\gcd(m_1, m_2) = 1$$. The CRT only guarantees a solution when the moduli are coprime.
Step 2: Compute combined modulus. $$M = m_1 \times m_2$$
Step 3: Compute partial products. $$M_1 = M / m_1 = m_2$$ and $$M_2 = M / m_2 = m_1$$.
Step 4: Find modular inverses. Find $$s_1$$ such that $$M_1 \cdot s_1 \equiv 1 \pmod{m_1}$$ and $$s_2$$ such that $$M_2 \cdot s_2 \equiv 1 \pmod{m_2}$$. The calculator searches for these inverses by trial.
Step 5: Construct the solution.
$$x = (a_1 \cdot M_1 \cdot s_1 + a_2 \cdot M_2 \cdot s_2) \bmod M$$
Step 6: Verify. Confirm $$x \bmod m_1 = a_1$$ and $$x \bmod m_2 = a_2$$.
The general solution is $$x + kM$$ for any integer $$k$$, giving infinitely many solutions spaced $$M$$ apart.
Are m₁ and m₂ coprime? confirms whether the CRT hypothesis is satisfied. If the moduli share a common factor greater than 1, the standard CRT construction may fail and the system might have no solution.
Combined Modulus M is the product $$m_1 \times m_2$$. The solution is unique modulo this value — all solutions differ by multiples of $$M$$.
Smallest Non-Negative Solution x is the unique value in $$[0, M-1]$$ satisfying both congruences simultaneously.
General Solution shows the full family of solutions: $$x_0 + kM$$ for all integers $$k$$.
Verification values confirm that the computed $$x$$ indeed satisfies both original congruences.
Inputs
Results
M₁ = 5, and 5 × 2 = 10 ≡ 1 (mod 3), so s₁ = 2. M₂ = 3, and 3 × 2 = 6 ≡ 1 (mod 5), so s₂ = 2. Then x = (2×5×2 + 3×3×2) mod 15 = (20 + 18) mod 15 = 38 mod 15 = 8. Verify: 8 mod 3 = 2 ✓, 8 mod 5 = 3 ✓.
Inputs
Results
M₁ = 11, and 11 × 2 = 22 ≡ 1 (mod 7), so s₁ = 2. M₂ = 7, and 7 × 8 = 56 ≡ 1 (mod 11), so s₂ = 8. Then x = (5×11×2 + 3×7×8) mod 77 = (110 + 168) mod 77 = 278 mod 77 = 47. Verify: 47 mod 7 = 5 ✓, 47 mod 11 = 3 ✓.
If $$\gcd(m_1, m_2) > 1$$, the standard CRT does not apply. The system $$x \equiv a_1 \pmod{m_1}$$, $$x \equiv a_2 \pmod{m_2}$$ has a solution if and only if $$a_1 \equiv a_2 \pmod{\gcd(m_1, m_2)}$$. When solutions exist, they are unique modulo $$\text{lcm}(m_1, m_2)$$ rather than $$m_1 m_2$$.
Yes. For $$k$$ pairwise coprime moduli, the CRT generalizes directly. You can also apply it iteratively: solve the first two congruences to get a single congruence modulo $$m_1 m_2$$, then combine that with the third congruence, and so on. Each step reduces the system by one equation.
In RSA, the private key operation computes $$c^d \bmod n$$ where $$n = pq$$. Using CRT, this splits into $$c^{d \bmod (p-1)} \bmod p$$ and $$c^{d \bmod (q-1)} \bmod q$$, then combines the results. Since modular exponentiation cost grows with the cube of the modulus bit-length, two half-size exponentiations are roughly 4 times faster.
The modular inverse of $$a$$ modulo $$m$$ is the integer $$s$$ such that $$as \equiv 1 \pmod{m}$$. It exists if and only if $$\gcd(a, m) = 1$$. The extended Euclidean algorithm efficiently computes it. For small moduli, trial multiplication (testing $$s = 1, 2, \ldots$$ until $$as \bmod m = 1$$) also works.
A residue number system (RNS) represents an integer $$x$$ by its residues $$(x \bmod m_1, x \bmod m_2, \ldots, x \bmod m_k)$$ for pairwise coprime moduli. Addition and multiplication become parallel, component-wise operations on small numbers. CRT reconstructs the original number when needed. RNS is used in specialized DSP hardware for high-throughput arithmetic.
The calculator uses a brute-force search, testing multipliers $$s = 1, 2, \ldots, 20$$ until $$M_i \cdot s \equiv 1 \pmod{m_i}$$. This works reliably for moduli up to 20. For larger moduli, the extended Euclidean algorithm would be more efficient, but the search approach is transparent and easy to verify.
Roboculator Team
The Roboculator Team explains calculations, planning tools, and practical formulas in clear language for real-life situations.
How helpful was this calculator?
Be the first to rate!
