3.4 The Chinese Remainder Theorem – Introduction to Cryptography with Coding Theory, 3rd Edition

3.4 The Chinese Remainder Theorem

In many situations, it is useful to break a congruence mod n into a system of congruences mod factors of n. Consider the following example. Suppose we know that a number x satisfies x25(mod42). This means that we can write x=25+42k for some integer k. Rewriting 42 as 76,  we obtain x=25+7(6k),  which implies that x254(mod7). Similarly, since x=25+6(7k),  we have x251(mod6). Therefore,

x25(mod42){ x4(mod7)x1(mod6).

The Chinese remainder theorem shows that this process can be reversed; namely, a system of congruences can be replaced by a single congruence under certain conditions.

Chinese Remainder Theorem

Suppose gcd(m, n)=1. Given integers a and b,  there exists exactly one solution x(modmn) to the simultaneous congruences

xa(modm), xb(modn).

Proof. There exist integers s, t such that ms+nt=1. Then ms1(modn) and nt1(modm). Let x=bms+ant. Then xanta(modm),  and xbmsb(modn),  so a solution x exists. Suppose x1 is another solution. Then xx1(modm) and xx1(modn),  so xx1 is a multiple of both m and n.

Lemma

Let m, n be integers with gcd(m, n)=1. If an integer c is a multiple of both m and n,  then c is a multiple of mn.

Proof. Let c=mk=n. Write ms+nt=1 with integers s, t. Multiply by c to obtain c=cms+cnt=mns+mnkt=mn(s+kt).

To finish the proof of the theorem, let c=xx1 in the lemma to find that xx1 is a multiple of mn. Therefore, xx1(modmn). This means that any two solutions x to the system of congruences are congruent mod mn,  as claimed.

Example

Solve x3(mod7), x5(mod15).

SOLUTION

x80(mod105) (note: 105=715). Since 803(mod7) and 805(mod15),  80 is a solution. The theorem guarantees that such a solution exists, and says that it is uniquely determined mod the product mn,  which is 105 in the present example.

How does one find the solution? One way, which works with small numbers m and n,  is to list the numbers congruent to b(modn) until you find one that is congruent to a(modm). For example, the numbers congruent to 5(mod15) are

5, 20, 35, 50, 65, 80, 95, .

Mod 7, these are 5, 6, 0, 1, 2, 3, 4, . Since we want 3(mod7),  we choose 80.

For slightly larger numbers m and n,  making a list would be inefficient. However, the proof of the theorem gives a fast method for finding x:

  1. Use the Extended Euclidean algorithm to find s and t with ms+nt=1.

  2. Let xbms+ant(modmn).

Example

Solve x7(mod12345), x3(mod11111).

SOLUTION

First, we know from our calculations in Section 3.2 that

12345(2224)+111112471=1, 

so s=2224 and t=2471. Therefore, x312345(2224)+7111112471109821127(mod(1111112345)).

How do you use the Chinese remainder theorem? The main idea is that if you start with a congruence mod a composite number n,  you can break it into simultaneous congruences mod each prime power factor of n,  then recombine the resulting information to obtain an answer mod n. The advantage is that often it is easier to analyze congruences mod primes or mod prime powers than to work mod composite numbers.

Suppose you want to solve x21(mod35). Note that 35=57. We have

x21(mod35){ x21(mod7)x21(mod5).

Now, x21(mod5) has two solutions: x±1(mod5). Also, x21(mod7) has two solutions: x±1(mod7). We can put these together in four ways:

x1(mod5), x1(mod7)x1(mod35), x1(mod5), x1(mod7)x6(mod35), x1(mod5), x1(mod7)x29(mod35), x1(mod5), x1(mod7)x34(mod35).

So the solutions of x21(mod35) are x1, 6, 29, 34(mod35).

In general, if n=p1p2pr is the product of r distinct odd primes, then x21(modn) has 2r solutions. This is a consequence of the following.

Chinese Remainder Theorem (General Form)

Let m1, , mk be integers with gcd(mi, mj)=1 whenever ij. Given integers a1, ,  ak,  there exists exactly one solution x(modm1mk) to the simultaneous congruences

xa1(modm1), xa2(modm2), , xak(modmk).

For example, the theorem guarantees there is a solution to the simultaneous congruences

x1(mod11), x1(mod13), x1(mod17).

In fact, x1871(mod111317) is the answer.

Exercise 57 gives a method for computing the number x in the theorem.