# The Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) is very useful in cryptography and other
domains. According to Wikipedia, its origin and name
come from this riddle in a 3rd century book by a Chinese mathematician:

There are certain things whose number is unknown. If we count them by threes,
we have two left over; by fives, we have three left over; and by sevens, two
are left over. How many things are there?

Mathematically, this is a system of linear congruences. In this post we’ll go
through a simple proof of the existence of a solution. It also demonstrates
how to find such a solution.

We’ll start with a few prerequisite lemmas needed to prove the CRT. You may want
to skip them on first reading and refer back when going through the CRT proof.

See my follow-up post on Computing the Chinese Remainder Theorem
for a discussion of some computational approaches with full source code.

## Prerequisites

Lemma 1: if d|ab and (d,a)=1, then d|b.

Proof: Since (d,a)=1 we know from Bézout’s identity that
there exist integers x and y such that dx+ay=1. Multiplying both
sides by b, we get: bdx+bay=b. bdx is divisible by d, and so is
bay because d|ab. Therefore d|b ∎

Lemma 2: if acequiv bc pmod{m} and (c,m)=1, then
aequiv b pmod{m}.

Proof: Since acequiv bc pmod{m}, we know that
m|(ac-bc), or m|c(a-b). Since (m,c)=1 we can use
Lemma 1 to conclude that m|(a-b). In other words,
aequiv b pmod{m} ∎

### Modular multiplicative inverse

A modular multiplicative inverse of an integer a w.r.t. the modulus m is
the solution of the linear congruence:

[axequiv1 pmod{m}]

Lemma 3: if (a,m)=1 then a has a unique modular multiplicative
inverse modulo m.

Proof: Once again using Bézout’s identity, we know from (a,m)=1 that
there exist integers r and s such that ar+ms=1. Therefore
ar-1 is a multiple of m, or arequiv 1pmod{m}. So r is a
multiplicative inverse of a.

Now let’s see why this inverse is unique. Let’s assume there are two inverses,
r_1 and r_2, so ar_1equiv 1pmod{m} and also
ar_2equiv 1pmod{m}, which means that ar_1equiv ar_2pmod{m}.

Since (a,m)=1 we can apply Lemma 2 to conclude that
r_1equiv r_2pmod{m} ∎

### Factorization and multiplying moduli

Lemma 4: if a|n and b|n and (a,b)=1 then also
ab|n.

Proof: Consider the prime factorization of n. a|n so a is
a multiple of some subset of the these prime factors. The same
can be said about b. But (a,b)=1, so a and b don’t have any prime
factors in common. Therefore ab is also a subset of the prime factors
of n, and ab|n ∎

## The Chinese Remainder Theorem

Assume n_1,dots,n_k are positive integers, pairwise coprime; that is,
for any ineq j, (n_i,n_j)=1. Let a_1,dots,a_k be
arbitrary integers. The system of congruences with an unknown x:

[begin{align*}
x &equiv a_1 pmod{n_1} \
&vdots \
x &equiv a_k pmod{n_k}
end{align*}]

has a single solution modulo the product
N=n_1times n_2times cdots times n_k.

Proof: Let N_k=frac{N}{n_k}. Then (N_k,n_k)=1, so each
N_k has a unique multiplicative inverse modulo n_k per Lemma 3
above; let’s call this inverse N’_k. Now consider:

[x=a_1 N_1 N’_1+a_2 N_2 N’_2+cdots +a_k N_k N’_k]

N_k is a multiple of every n_i except for i=k. In other
words for ineq k we have N_iequiv 0pmod{n_i}. On the other
hand, for i=k we have, by construction, N_i N’_iequiv
1pmod{n_i}. So for each k we have:

[xequiv a_k N_k N’_k equiv a_k pmod{n_k}]

because all the other terms in the sum are zero. Hence x satisfies every
congruence in the system.

To prove that x is unique modulo N, let’s assume there are two solutions:
x and y. Both solutions to the CRT should satisfy
xequiv yequiv a_kpmod{n_k}. Therefore x-y is a multiple of
n_k for each k. Since these n_k are pairwise coprime, from
Lemma 4 we know that x-y is also a multiple of N, or
xequiv ypmod{N} ∎

### Corollary

If n_1,dots,n_k are pairwise coprime and
N=n_1times n_2times cdots times n_k, then for all integers x
and a, xequiv apmod{n_i} for i=1,2,dots,k if and only if
xequiv apmod{N}. 