Chinese Remainder Theorem Calculator

Enter Calculation

Remainder 1 (a₁)

Modulus 1 (m₁)

Remainder 2 (a₂)

Modulus 2 (m₂)

Remainder 3 (a₃) — optional

Modulus 3 (m₃) — leave blank if unused

Results

Smallest non-negative solution

8

x (mod 15)

Unique solution exists	Yes (mod 15)
Congruences used	2
General solution	x = 8 + 15k

What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem (CRT) is a classic result in number theory. It states that if you have a system of congruences \(x \equiv a_1 \pmod{m_1}\), \(x \equiv a_2 \pmod{m_2}\), … where the moduli are pairwise coprime (share no common factor), then there is a single unique solution x modulo \(M = m_1 \cdot m_2 \cdot \dots\). This calculator finds that smallest non-negative solution.

The CRT finds a unique value mod M that satisfies all congruences at once.

How to use this calculator

Enter each remainder \(a_i\) together with its modulus \(m_i\). You can solve a system of two or three congruences — leave the third modulus blank if you only need two. The tool checks that your moduli are pairwise coprime, then returns x and the combined modulus M. Every value of the form \(x + Mk\) (for any integer k) is also a solution.

The formula explained

Let \(M = \prod m_i\). For each congruence define \(M_i = M / m_i\) and \(y_i = M_i^{-1} \bmod m_i\) (the modular inverse computed with the extended Euclidean algorithm). The solution is the weighted sum $$x \equiv \sum_{i} a_i\,M_i\,y_i \pmod{M}$$ Because \(M_i\) is divisible by every modulus except \(m_i\), each term contributes the correct remainder only to its own congruence.

Each congruence contributes a term a_i M_i y_i, summed and reduced mod M.

Worked example

Solve \(x \equiv 2 \pmod{3}\) and \(x \equiv 1 \pmod{4}\). Here \(M = 3 \cdot 4 = 12\). \(M_1 = 4\), and \(4 \equiv 1 \pmod{3}\) so \(y_1 = 1\); \(M_2 = 3\), and \(3 \equiv 3 \pmod{4}\) so \(y_2 = 3\) (since \(3 \cdot 3 = 9 \equiv 1\)). Then $$x = 2 \cdot 4 \cdot 1 + 1 \cdot 3 \cdot 3 = 8 + 9 = 17 \equiv 5 \pmod{12}$$ Check: \(5 \bmod 3 = 2\) ✓ and \(5 \bmod 4 = 1\) ✓.

FAQ

Why must the moduli be coprime? If two moduli share a factor, the system may have no solution or many solutions modulo their lcm, so the standard CRT formula no longer applies.

What does "smallest non-negative solution" mean? All solutions differ by multiples of M; the calculator reports the one in the range 0 to M−1.

Can I use negative remainders? Yes. They are reduced modulo each \(m_i\) into the range 0 to \(m_i-1\) before solving.