The Chinese Remainder Theorem

In this section we prove the Chinese Remainder Theorem, which gives conditions under which a system of linear equations is guaranteed to have a solution. In the 4th century a Chinese mathematician asked the following:

Question 2.2   There is a quantity whose number is unknown. Repeatedly divided by 3, the remainder is 2; by 5 the remainder is 3; and by 7 the remainder is 2. What is the quantity?

In modern notation, Question 2.2.1 asks us to find a positive integer solution to the following system of three equations:

$$x \equiv 2 \pmod{3}$$

$$x \equiv 3 \pmod{5}$$

$$x \equiv 2 \pmod{7}$$

The Chinese Remainder Theorem asserts that a solution exists, and the proof gives a method to find one. (See Section 2.3 for the necessary algorithms.)

Theorem 2.2 (Chinese Remainder Theorem)   Let $a, b\in \mathbb {Z}$ and $n,m\in\mathbb{N}$ such that $\gcd(n,m)=1$ . Then there exists $x\in\mathbb{Z}$ such that

$$x \equiv a\pmod{m},$$

$$x \equiv b\pmod{n}.$$

Moreover $x$ is unique modulo $mn$ .

Proof. If we can solve for $t$ in the equation

$$a+tm \equiv b \pmod{n},$$

then $x=a+tm$ will satisfy both congruences. To see that we can solve, subtract $a$ from both sides and use Proposition 2.1.12 together with our assumption that $\gcd(n,m)=1$ to see that there is a solution.

For uniqueness, suppose that $x$ and $y$ solve both congruences. Then $z=x-y$ satisfies $z\equiv 0\pmod{m}$ and $z\equiv 0\pmod{n}$ , so $m\mid z$ and $n\mid z$ . Since $\gcd(n,m)=1$ , it follows that $nm\mid z$ , so $x\equiv y\pmod{nm}$ . $\qedsymbol$

Algorithm 2.2 (Chinese Remainder Theorem)   Given coprime integers $m$ and $n$ and integers $a$ and $b$ , this algorithm find an integer $x$ such that $x\equiv a\pmod{m}$ and $x\equiv b\pmod{n}$ .

1. [Extended GCD] Use Algorithm 2.3.7 below to find integers $c,d$ such that $cm+dn=1$ .
2. [Answer] Output $x =a + (b-a)cm$ and terminate.

Proof. Since $c\in \mathbb {Z}$ , we have $x\equiv a\pmod{m}$ , and using that $cm+dn=1$ , we have $a + (b-a)cm \equiv a + (b-a) \equiv b\pmod{n}$ . $\qedsymbol$

Now we can answer Question 2.2.1. First, we use Theorem 2.2.2 to find a solution to the pair of equations

$$x \equiv 2 \pmod{3},$$

$$x \equiv 3 \pmod{5}.$$

Set $a=2$ , $b=3$ , $m=3$ , $n=5$ . Step 1 is to find a solution to $t\cdot 3 \equiv 3-2\pmod{5}$ . A solution is $t=2$ . Then $x=a+tm=2+2\cdot 3 = 8$ . Since any $x'$ with $x'\equiv x\pmod{15}$ is also a solution to those two equations, we can solve all three equations by finding a solution to the pair of equations

$$x \equiv 8 \pmod{15}$$

$$x \equiv 2 \pmod{7}.$$

Again, we find a solution to $t\cdot 15 \equiv 2-8\pmod{7}$ . A solution is $t = 1$ , so

$$x=a+tm=8+15=23.$$

Note that there are other solutions. Any $x'\equiv x\pmod{3\cdot 5\cdot 7}$ is also a solution; e.g., $23+3\cdot 5\cdot 7 = 128$ .

SAGE Example 2.2   The SAGE command CRT(a,b,m,n) computes an integer $x$ such that $x\equiv a\pmod{m}$ and $x\equiv b\pmod{n}$ . For example,

sage: CRT(2,3, 3, 5)
8

The CRT_list command computes a number that reduces to several numbers modulo coprime modulo. We use it to answer Question 2.2.1:

sage: CRT_list([2,3,2], [3,5,7])
23