Free Chinese Remainder Theorem Calculator

Understanding the Chinese Remainder Theorem

The Chinese remainder theorem (CRT) is a fundamental result in number theory that allows you to solve a system of congruences—equations that specify the remainder when an unknown integer is divided by several given moduli. When the moduli are pairwise coprime, the theorem guarantees a unique solution modulo the product of those moduli. This CRT calculator provides a fast, reliable way to solve such systems online, making modular arithmetic accessible whether you are studying number theory, preparing for competitive exams, or working on cryptographic algorithms.

Modular Arithmetic and Congruences

Before diving into the theorem itself, it helps to recall the concept of a remainder. When an integer $a$ is divided by a positive integer $b$, the remainder $r$ is the integer between $0$ and $b-1$ that satisfies:

$$a = k \cdot b + r$$

for some integer $k$. For example, dividing 17 by 5 gives $17 = 3 \cdot 5 + 2$, so the remainder is 2.

The modulo operation builds on this idea. We say that two numbers $a$ and $b$ are congruent modulo $n$ (written $a \equiv b \pmod{n}$) if they have the same remainder when divided by $n$. Such expressions are called congruences. They behave much like ordinary equations: you can add, subtract, or multiply both sides by any integer (though division requires care). This simple property makes congruences a powerful tool for working with integers.

The Euclidean Algorithm for GCD

The Euclidean algorithm is an efficient method for finding the greatest common divisor (gcd) of two integers. Given two numbers $x$ and $y$ with $x > y$, the algorithm proceeds as follows:

1. Set $a_1 = x$, $b_1 = y$, and let $n = 1$.
2. Determine the integer $k_n$ as the largest multiple of $b_n$ that does not exceed $a_n$ (i.e., the floor of $a_n / b_n$).
3. Compute the remainder $r_n = a_n - k_n \cdot b_n$.
4. If $r_n = 0$, the algorithm stops and $b_n = \gcd(x,y)$. Otherwise, set $a_{n+1} = b_n$, $b_{n+1} = r_n$, increase $n$ by 1, and repeat from step 2.

At each step we have $a_n = k_n \cdot b_n + r_n$. For example, to find $\gcd(1785, 546)$:

$n$	$a_n$	$k_n$	$b_n$	$r_n$
1	1785	3	546	147
2	546	3	147	105
3	147	1	105	42
4	105	2	42	21
5	42	2	21	0

Because $r_5 = 0$, $\gcd(1785, 546) = b_5 = 21$.

Bézout’s Identity

Bézout’s identity (or Bézout’s lemma) states that for any non‑zero integers $a$ and $b$, there exist integers $k$ and $l$ such that:

$$k \cdot a + l \cdot b = \gcd(a,b).$$

These coefficients can be found by reversing the steps of the Euclidean algorithm. Continuing with $a = 1785$ and $b = 546$ (gcd 21), we back‑substitute through the equations:

$$\begin{aligned} 21 &= 105 - 2 \cdot 42 \\ 42 &= 147 - 1 \cdot 105 \\ 105 &= 546 - 3 \cdot 147 \\ 147 &= 1785 - 3 \cdot 546 \end{aligned}$$

Replacing step by step gives:

$$21 = -11 \cdot 1785 + 36 \cdot 546,$$

so one valid pair is $k = -11$ and $l = 36$. Notice that the coefficients need not be positive; they are simply integers that satisfy the identity.

The Chinese Remainder Theorem: Statement and Algorithm

The Chinese remainder theorem brings together congruences, the Euclidean algorithm, and Bézout’s identity. Its formal statement is:

Let $n_1, n_2, \dots, n_k$ be pairwise coprime positive integers (i.e., $\gcd(n_i, n_j) = 1$ for $i \neq j$). Then for any integers $a_1, a_2, \dots, a_k$, the system of congruences

$$\begin{cases} x \equiv a_1 \pmod{n_1} \\ x \equiv a_2 \pmod{n_2} \\ \quad \vdots \\ x \equiv a_k \pmod{n_k} \end{cases}$$

has a unique solution modulo $N = n_1 n_2 \cdots n_k$.

In plain language: if you know the remainders of an unknown number when divided by several coprime moduli, you can determine that number uniquely (up to adding a multiple of the product of the moduli).

To solve such a system, follow these steps:

1. Compute the product $N = n_1 n_2 \cdots n_k$.
2. For each modulus $n_i$, let $m_i = N / n_i$.
3. Use Bézout’s identity to find integers $v_i$ and $u_i$ such that $u_i n_i + v_i m_i = 1$. The number $v_i$ is the multiplicative inverse of $m_i$ modulo $n_i$.
4. Define $e_i = v_i m_i$. Notice that $e_i \equiv 1 \pmod{n_i}$ and $e_i \equiv 0 \pmod{n_j}$ for $j \neq i$.
5. A particular solution is $x_0 = a_1 e_1 + a_2 e_2 + \cdots + a_k e_k$. The general solution is $x \equiv x_0 \pmod{N}$.

While the algorithm is straightforward, the manual calculation of the inverses can be tedious. This is where an online CRT solver becomes invaluable.

Worked Example with the Calculator

Consider a classic candy‑distribution problem. A mother has a handful of sweets. When she divides them equally among her three children, one sweet remains. If she also gives one to the neighbor girl (four children total), two sweets remain. Inviting the girl’s brother (five children total) leaves three sweets. How many sweets did she buy?

Let $x$ be the number of sweets. The conditions translate into the system:

$$\begin{aligned} x &\equiv 1 \pmod{3} \\ x &\equiv 2 \pmod{4} \\ x &\equiv 3 \pmod{5} \end{aligned}$$

The moduli 3, 4, 5 are pairwise coprime, so the CRT applies. Using the algorithm:

• $N = 3 \cdot 4 \cdot 5 = 60$
• $m_1 = 60/3 = 20$, $m_2 = 60/4 = 15$, $m_3 = 60/5 = 12$
• Find inverses via the Euclidean algorithm:
  • For (3,20): $20 \equiv 2 \pmod{3}$, inverse of 20 mod 3 is $v_1 = -1$ because $(-1)\cdot 20 \equiv 1 \pmod{3}$ → $e_1 = (-1)\cdot 20 = -20$
  • For (4,15): inverse of 15 mod 4 is $-1$ → $e_2 = -15$
  • For (5,12): inverse of 12 mod 5 is $-2$ → $e_3 = -24$
• Then $x_0 = 1\cdot(-20) + 2\cdot(-15) + 3\cdot(-24) = -122$
• The simplest non‑negative solution is $x \equiv -122 \equiv 58 \pmod{60}$.

So the mother bought 58 sweets. This result can be obtained instantly using the Chinese remainder theorem calculator—simply enter the three congruences and the tool returns the smallest positive solution.

Why Use This CRT Solver?

• Speed: Avoid manual back‑substitution and inverse calculations.
• Accuracy: Eliminates arithmetic mistakes when handling larger moduli.
• Flexibility: Works for any number of congruences (as long as the moduli are coprime).
• Educational: The step‑by‑step algorithm is clearly explained, making it a valuable learning aid for modular arithmetic, system of congruences, and number theory.

Whether you are a student or a professional working with cryptographic protocols that rely on the CRT, this tool streamlines the solving process and lets you focus on applying the results.