Original post

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, though check the Wikipedia link for a discussion

of different methods and their relative efficiency.

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.

## 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}.

**Proof**: we’ll start with the *if* direction. If xequiv apmod{N}

this means N|(x-a). But that immediately means that for each *i*,

n_i|(x-a) as well, or xequiv apmod{n_i}.

Now the *only if* direction. Given xequiv apmod{n_i} for

i=1,2,dots,k, we can invoke the CRT using *a* in all congruences.

The CRT tells us this system has a single solution modulo N. But we know

that *a* is a solution, so it has to be the only one ∎