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 and , then .

**Proof**: Since we know from Bézout's identity that
there exist integers *x* and *y* such that . Multiplying both
sides by *b*, we get: . *bdx* is divisible by *d*, and so is
*bay* because . Therefore ∎

**Lemma 2**: if and , then
.

**Proof**: Since , we know that
, or . Since we can use
Lemma 1 to conclude that . In other words,
∎

### Modular multiplicative inverse

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

**Lemma 3**: if then *a* has a unique modular multiplicative
inverse modulo *m*.

**Proof**: Once again using Bézout's identity, we know from that
there exist integers *r* and *s* such that . Therefore
is a multiple of *m*, or . So *r* is a
multiplicative inverse of *a*.

Now let's see why this inverse is unique. Let's assume there are two inverses, and , so and also , which means that .

Since we can apply Lemma 2 to conclude that ∎

### Factorization and multiplying moduli

**Lemma 4**: if and and then also
.

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

## The Chinese Remainder Theorem

Assume are positive integers, pairwise coprime; that is,
for any , . Let be
arbitrary integers. The system of congruences with an unknown *x*:

has a single solution modulo the product .

**Proof**: Let . Then , so each
has a unique multiplicative inverse modulo per Lemma 3
above; let's call this inverse . Now consider:

is a multiple of every except for . In other
words for we have . On the other
hand, for we have, by construction, . So for each *k* we have:

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
. Therefore is a multiple of
for each *k*. Since these are pairwise coprime, from
Lemma 4 we know that is also a multiple of N, or
∎

### Corollary

If are pairwise coprime and
, then for all integers *x*
and *a*, for if and only if
.

**Proof**: we'll start with the *if* direction. If
this means . But that immediately means that for each *i*,
as well, or .

Now the *only if* direction. Given for
, we can invoke the CRT using *a* in all congruences.
The CRT tells us this system has a single solution modulo . But we know
that *a* is a solution, so it has to be the only one ∎