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 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 ∎