Arithmetic and number theory

Chinese remainder theorem

A system of congruences with coprime moduli always has a unique solution modulo their product.

IntuitionCounting soldiers without counting past $7$

A general lines up his soldiers in rows of $3$ and sees $2$ left over; in rows of $5$ , $3$ are left over; in rows of $7$ , $2$ are left over. How many soldiers are there? Even though the general never counted past $7$ , those three tiny remainders $(2,3,2)$ pin down the exact count modulo $3\times5\times7=105$ : the answer is $23$ (plus any multiple of $105$ ). This is the Chinese remainder theorem (CRT): as long as the moduli share no common factor in pairs, knowing the remainders modulo each $m_i$ carries the exact same information as knowing the remainder modulo their product $m_1 m_2\cdots m_k$ . It lets us split one hard computation modulo a huge number into several easy, independent computations modulo its prime-power factors, and then reassemble the result.

Residues modulo

m = 15 = 3 \times 5

: each residue

x \bmod 15

is uniquely determined by its pair of remainders

(x \bmod 3,\ x \bmod 5)

SchoolStatement and explicit formula

Definition: A system of simultaneous congruences

Given moduli $m_1,\dots,m_k$ that are pairwise coprime — $\gcd(m_i,m_j)=1\quad(i\neq j)$ — and any integers $a_1,\dots,a_k$ , the system $x \equiv a_i \pmod{m_i}\quad(1\le i\le k)$ asks for an integer $x$ that simultaneously leaves remainder $a_i$ modulo $m_i$ for every $i$ . Setting $M = m_1 m_2 \cdots m_k,\quad M_i = M/m_i$ and letting $y_i$ be the inverse of $M_i$ modulo $m_i$ (so $M_i y_i \equiv 1 \pmod{m_i}$ , which exists since $\gcd(M_i,m_i)=1$ ), the solution is given explicitly by $x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M}$ .

x \equiv a_i \pmod{m_i}\quad(1\le i\le k),\qquad \gcd(m_i,m_j)=1\ (i\neq j)

Each term $a_i M_i y_i$ in the sum is engineered to be $\equiv a_i \pmod{m_i}$ (since $M_i y_i\equiv1\pmod{m_i}$ ) and $\equiv 0 \pmod{m_j}$ for every $j\neq i$ (since $m_j$ is a factor of $M_i = M/m_i$ ). So when we reduce the whole sum modulo a fixed $m_i$ , all terms except the $i$ -th vanish, leaving $a_i$ — exactly as required.

x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M},\qquad M = m_1\cdots m_k,\ M_i = M/m_i,\ M_i y_i \equiv 1 \pmod{m_i}

Two moduli vs. $k$ moduli
Case	Hypothesis	Unique modulo
$2$ moduli $m_1,m_2$	$\gcd(m_1,m_2)=1$	$m_1 m_2$
$k$ moduli $m_1,\dots,m_k$	$\gcd(m_i,m_j)=1$ for $i\neq j$	$M=m_1\cdots m_k$

UndergraduateTheorems

Theorem: Chinese remainder theorem (existence and uniqueness)

If $m_1,\dots,m_k$ are pairwise coprime ( $\gcd(m_i,m_j)=1\quad(i\neq j)$ ), then for any integers $a_1,\dots,a_k$ the system $x \equiv a_i \pmod{m_i}\quad(1\le i\le k)$ has a solution $x$ , and any two solutions are congruent modulo $M=m_1\cdots m_k$ .

Why is it true?

Because the moduli share no prime factors, the condition of leaving remainder $a_1$ modulo $m_1$ and the condition of leaving remainder $a_2$ modulo $m_2$ are completely independent constraints — like specifying an object's $x$ -coordinate and $y$ -coordinate separately. Bézout's identity gives us "basis vectors" that are $1$ modulo one modulus and $0$ modulo all the others, letting us build a solution directly as a linear combination.

Proof

We first prove the two-modulus case ( $k=2$ ) and then extend by induction. Since $\gcd(m_1,m_2)=1$ , Bézout's identity gives integers $u,v$ with $m_1 u + m_2 v = 1$ . Set $x_0 = a_1 m_2 v + a_2 m_1 u$ .

Check modulo $m_1$ : from $m_1 u + m_2 v = 1$ we have $m_2 v = 1 - m_1 u \equiv 1 \pmod{m_1}$ , while $m_1 u \equiv 0 \pmod{m_1}$ , so $x_0 \equiv a_1\cdot 1 + a_2\cdot 0 = a_1 \pmod{m_1}$ .

Symmetrically, modulo $m_2$ : $m_1 u = 1-m_2 v \equiv 1 \pmod{m_2}$ and $m_2 v \equiv 0 \pmod{m_2}$ , so $x_0 \equiv a_1\cdot 0 + a_2\cdot 1 = a_2 \pmod{m_2}$ . This proves existence for $k=2$ .

For uniqueness when $k=2$ : if $x$ and $x'$ both solve the system, then $x-x'\equiv0\pmod{m_1}$ and $x-x'\equiv0\pmod{m_2}$ , i.e. both $m_1$ and $m_2$ divide $d=x-x'$ . Multiply the Bézout equation $m_1 u+m_2 v=1$ by $d$ : $d = d m_1 u + d m_2 v$ . Since $m_2\mid d$ , the first term $d m_1 u$ is a multiple of $m_1 m_2$ ; since $m_1\mid d$ , the second term $d m_2 v$ is also a multiple of $m_1 m_2$ . Hence $m_1 m_2 \mid d$ , i.e. $x\equiv x'\pmod{m_1 m_2}$ .

For general $k>2$ , induction: the first two congruences are equivalent (by the $k=2$ case) to a single congruence modulo $m_1 m_2$ ; since $m_3$ is coprime to both $m_1$ and $m_2$ , it is coprime to their product $m_1 m_2$ , so we can combine again, and so on up to $k$ . Notice also that the explicit sum $x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M}$ works directly for any $k$ by the exact same reasoning: $M_i = M/m_i$ is coprime to $m_i$ so its inverse $y_i$ exists, and every term $j\neq i$ contains $m_i$ as a factor of $M_j$ . $\blacksquare$

Theorem: CRT as a ring isomorphism and the multiplicativity of

\varphi

When $\gcd(m_1,m_2)=1$ , the map $\psi(x \bmod m_1 m_2) = (x\bmod m_1,\ x\bmod m_2)$ is a ring isomorphism $\mathbb{Z}/(m_1 m_2)\mathbb{Z} \cong (\mathbb{Z}/m_1\mathbb{Z})\times(\mathbb{Z}/m_2\mathbb{Z})$ , and restricting $\psi$ to invertible elements proves $\varphi(m_1 m_2) = \varphi(m_1)\,\varphi(m_2)$ .

Why is it true?

This is the structural meaning of CRT: arithmetic modulo $m_1 m_2$ literally is two independent copies of modular arithmetic (one mod $m_1$ , one mod $m_2$ ) running side by side. That is both why Euler's totient $\varphi$ factors cleanly across coprime numbers, and why computers can speed up big-integer and cryptographic calculations by doing them in each small component separately.

Proof

First, $\psi$ is well-defined: if $x\equiv x'\pmod{m_1 m_2}$ then $m_1 m_2\mid(x-x')$ , so both $m_1$ and $m_2$ divide $x-x'$ , meaning $x\equiv x'\pmod{m_1}$ and $x\equiv x'\pmod{m_2}$ .

Second, $\psi$ respects addition and multiplication in each coordinate because reduction modulo $m_i$ does (proved in the first topic on congruences), so $\psi$ is a ring homomorphism.

Third, Theorem 1 above says precisely that for every pair $(a_1,a_2)$ there is an $x$ mapped to it (so $\psi$ is surjective) and that $x$ is unique modulo $m_1 m_2$ (so $\psi$ is injective). Hence $\psi$ is a bijection and therefore a ring isomorphism.

Finally, in a product ring $R_1\times R_2$ , an element $(u_1,u_2)$ has a multiplicative inverse $(v_1,v_2)$ iff $u_1 v_1=1$ in $R_1$ and $u_2 v_2=1$ in $R_2$ — that is, iff both coordinates are invertible. Since a ring isomorphism preserves invertibility, the invertible elements of $\mathbb{Z}/(m_1 m_2)\mathbb{Z}$ (of which there are $\varphi(m_1 m_2)$ ) correspond bijectively to pairs of invertible elements in $(\mathbb{Z}/m_1\mathbb{Z})\times(\mathbb{Z}/m_2\mathbb{Z})$ (of which there are $\varphi(m_1)\,\varphi(m_2)$ ). Counting both sides gives $\varphi(m_1 m_2)=\varphi(m_1)\,\varphi(m_2)$ . Combined with $\varphi(p^r)=p^r-p^{r-1}$ for a prime power (where the non-coprime numbers are just the $p^{r-1}$ multiples of $p$ ), this immediately yields the general product formula for $\varphi(n)$ used in the previous topic. $\blacksquare$

AdvancedReal-World Applications and Worked Examples

Beyond classical puzzles, the Chinese remainder theorem is a workhorse of modern computation. Every production RSA implementation (OpenSSL, BoringSSL, hardware security modules) uses CRT-RSA (Quisquater–Couvreur, 1982) to compute $c^d \bmod pq$ by computing modulo $p$ and modulo $q$ separately and recombining via CRT — roughly a $4$ -times speedup because modular exponentiation costs $O((\log m)^3)$ and halving the bit-length of the modulus cuts the work per exponentiation by $2^3=8$ (done twice, so $8/2=4$ times faster overall). The same idea underlies Residue Number Systems (RNS) in fast big-integer libraries and homomorphic encryption, as well as astronomical and calendar cycle calculations.

Example: Solving Sunzi's original soldier puzzle

Find all integers $x$ satisfying $x\equiv2\pmod3$ , $x\equiv3\pmod5$ , and $x\equiv2\pmod7$ .

Solution

The moduli $m_1=3,m_2=5,m_3=7$ are pairwise coprime with product $M = 3\times5\times7 = 105$ , so the explicit CRT formula applies with $M_1 = 105/3 = 35$ , $M_2 = 105/5 = 21$ , $M_3 = 105/7 = 15$ .

Find each inverse $y_i$ of $M_i$ modulo $m_i$ : (1) $35 \equiv 2 \pmod 3$ , and $2\times2=4\equiv1\pmod3$ , so $y_1=2$ ; (2) $21 \equiv 1 \pmod 5$ , so $y_2=1$ ; (3) $15 \equiv 1 \pmod 7$ , so $y_3=1$ .

Substitute into $x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M}$ with $(a_1,a_2,a_3)=(2,3,2)$ : $x \equiv 2\cdot35\cdot2 + 3\cdot21\cdot1 + 2\cdot15\cdot1 = 140 + 63 + 30 = 233 \pmod{105}$ .

Since $233 = 2\times105 + 23$ , reducing modulo $105$ gives $x \equiv 23 \pmod{105}$ . Quick check: $23 = 3\times7+2\equiv2\pmod3$ , $23=5\times4+3\equiv3\pmod5$ , $23=7\times3+2\equiv2\pmod7$ . All three hold, and the smallest positive solution is ** $23$ **.

Example: Fast RSA decryption via CRT (CRT-RSA)

In the RSA example from the previous topic ( $p=5,q=11,n=55,d=27$ , ciphertext $c=8$ ), compute $m = 8^{27} \bmod 55$ by splitting it into two tiny calculations modulo $5$ and modulo $11$ instead of working modulo $55$ .

Solution

Modulo $p=5$ : reduce the base $8\equiv3\pmod5$ , and reduce the exponent $d=27$ modulo $p-1=4$ using Fermat's little theorem ( $27 = 4\times6+3$ , so $d_p = 3$ ). Then $m_p = 3^3 = 27 \equiv 2 \pmod 5$ — a single tiny cube!

Modulo $q=11$ : the base is $8$ , and reduce the exponent $27$ modulo $q-1=10$ using Fermat ( $27 = 10\times2+7$ , so $d_q = 7$ ). Compute $8^7 \bmod 11$ : since $8\equiv-3\pmod{11}$ , we have $8^2\equiv9\equiv-2$ , $8^4\equiv4$ , $8^7 = 8^4\cdot8^2\cdot8\equiv 4\cdot(-2)\cdot(-3)=24\equiv2\pmod{11}$ .

Now recombine $m\equiv2\pmod5$ and $m\equiv2\pmod{11}$ by CRT: since both remainders happen to be $2$ , the unique solution modulo $55$ is immediately $m\equiv2\pmod{55}$ (in general, with different $m_p,m_q$ , one applies the two-modulus CRT formula once). Notice we never squared a number larger than $11$ and never used an exponent larger than $7$ — for $2048$ -bit RSA primes this same split cuts decryption time to roughly a quarter.

Common mistake. Pairwise coprimality is not optional: if

\gcd(m_1,m_2)=g>1

, 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 g

, and when a solution exists it is unique modulo

\operatorname{lcm}(m_1,m_2)

, not

m_1 m_2

. For instance,

x\equiv1\pmod4

and

x\equiv0\pmod6

has no solution at all: the first forces

x

to be odd, the second forces

x

to be even, because

a_1=1\not\equiv0=a_2\pmod{\gcd(4,6)}

. A second frequent slip in the explicit formula

x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M}

is computing

y_i

as the inverse of

M_i

modulo

M

(which does not exist!) instead of modulo

m_i

ResearchCRT at the research frontier: fast arithmetic, fault attacks, and lattice cryptography

Research frontier as of 2026

Where the subject stands (as of 2026).

1. Fast integer and polynomial multiplication. In 2021 David Harvey and Joris van der Hoeven proved the long-conjectured bound that two $n$ -bit integers can be multiplied in $O(n\log n)$ bit operations. Multi-modular CRT / RNS techniques — splitting a huge integer or polynomial coefficient across several machine-word-sized coprime moduli, multiplying in each component via fast transforms, and reconstructing with CRT — remain a core building block of practical computer-algebra systems (FLINT, GMP, NTL) and continue to be optimized for modern SIMD and GPU architectures.

2. Bellcore fault attacks on CRT-RSA and countermeasures. Although CRT-RSA (Quisquater–Couvreur, 1982) gives a $4$ -times decryption speedup, Boneh, DeMillo, and Lipton (1997) discovered a devastating side-channel weakness: if a single hardware fault corrupts $m_p$ while leaving $m_q$ intact, the attacker receives a faulty signature $\tilde s$ satisfying $\tilde s^e \equiv m \pmod q$ but $\tilde s^e \not\equiv m \pmod p$ , and one GCD computation $\gcd(\tilde s^e - m, n) = q$ factors the RSA modulus instantly! Designing low-overhead fault-attack countermeasures for CRT-based implementations (and analogous fault protections for post-quantum schemes that use CRT-like Number-Theoretic Transforms) remains an active topic in cryptographic hardware research.

3. CRT in lattice-based and homomorphic cryptography. In ring-based post-quantum and fully homomorphic schemes, the polynomial ring $\mathbb{Z}_q[x]/(x^N+1)$ splits via the polynomial version of CRT into $N$ independent slots whenever $q\equiv1\pmod{2N}$ — the exact mechanism behind SIMD batching in homomorphic encryption, which packs thousands of plaintexts into one ciphertext and operates on all of them in parallel.

Find the smallest non-negative integer $x$ satisfying $x\equiv1\pmod3$ and $x\equiv2\pmod5$ .

If $m_1=4,m_2=9,m_3=25$ , the solution to a CRT system with these moduli is unique modulo:

What can you say about the system $x\equiv1\pmod4$ and $x\equiv0\pmod6$ ?

Why does CRT speed up RSA decryption $c^d\bmod pq$ by roughly $4$ times?

References

Jean-Jacques Quisquater, Christophe Couvreur (1982). Fast decipherment algorithm for RSA public-key cryptosystem · DOI:10.1049/el:19820617
David Harvey, Joris van der Hoeven (2021). Integer multiplication in time O(n log n) · DOI:10.4007/annals.2021.193.2.4