Tags Math

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 ac\equiv bc \pmod{m} and (c,m)=1, then a\equiv b \pmod{m}.

Proof: Since ac\equiv 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, a\equiv 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:

\[ax\equiv1 \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 ar\equiv 1\pmod{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_1\equiv 1\pmod{m} and also ar_2\equiv 1\pmod{m}, which means that ar_1\equiv ar_2\pmod{m}.

Since (a,m)=1 we can apply Lemma 2 to conclude that r_1\equiv r_2\pmod{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 i\neq 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_1\times n_2\times \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 i\neq k we have N_i\equiv 0\pmod{n_i}. On the other hand, for i=k we have, by construction, N_i N'_i\equiv 1\pmod{n_i}. So for each k we have:

\[x\equiv 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 x\equiv y\equiv a_k\pmod{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 x\equiv y\pmod{N}

Corollary

If n_1,\dots,n_k are pairwise coprime and N=n_1\times n_2\times \cdots \times n_k, then for all integers x and a, x\equiv a\pmod{n_i} for i=1,2,\dots,k if and only if x\equiv a\pmod{N}.

Proof: we'll start with the if direction. If x\equiv a\pmod{N} this means N|(x-a). But that immediately means that for each i, n_i|(x-a) as well, or x\equiv a\pmod{n_i}.

Now the only if direction. Given x\equiv a\pmod{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 ∎