5.3 The Chinese Remainder Theorem

In the previous section we saw how to decide if certain congruences have solutions, and how to solve them when solutions exist. In this section we shall consider a certain type of problem in which two congruences are involved. We begin with an example.

In general the problem will be to solve simultaneously the pair of congruences

The trial-and-error approach proved successful in the case above, but if the numbers were larger it would involve rather a lot of work. We shall now try to produce a better approach.

Let us consider the case where the moduli $m$ and $n$ are coprime, and take $r,s\in\mathbb{Z}$ such that $rm+sn=1$. If we multiply this identity by $a$, then we obtain $arm+asn=a$ and thus $asn\equiv a\bmod m$. On the other hand, multiplying $rm+sn=1$ by $b$, we get $brm+bsn=b$, so that $brm\equiv b\bmod n$. Hence $x=asn$ is a solution to the first congruence, while $x=brm$ solves the other. Adding up these two separate solutions, we obtain a number $c=asn+brm$ which satisfies

and

Thus $c$ solves the two congruences simultaneously.

In fact, we can build on this idea to obtain the following description of all simultaneous solutions to the pair of congruences (5.3.1) (still under the assumption that the moduli $m$ and $n$ are coprime); this result is known as the Chinese Remainder Theorem.

Solution. Since $\mathrm{hcf}(8,9)=1$, the Chinese Remainder Theorem applies. We have $a=2$, $b=5$, $m=8$ and $n=9$. We require integers $r$ and $s$ such that $8r+9s=1$; clearly we can take $r=-1$ and $s=1$ here. We now compute $mn=8\cdot 9=72$ and

so that the complete solution to the pair of congruences is $x\equiv 50\bmod 72$. (As a check, we observe that $50-2=48=6\cdot 8$ and $50-5=45=5\cdot 9$, so that $50\equiv 2\bmod 8$ and $50\equiv 5\bmod 9$.)

Proof. Set $c=asn+brm\in\mathbb{Z}$. We saw above that $c\equiv a\bmod m$ and $c\equiv b\bmod n$. Combining this with Lemmas 5.1.7 and 5.1.9, we see that $x\in\mathbb{Z}$ satisfies $x\equiv a\bmod m$ and $x\equiv b\bmod n$ if and only if $x\equiv c\bmod m$ and $x\equiv c\bmod n$. By definition, this means that $m|x-c$ and $n|x-c$, or in other words that $x-c$ is a common multiple of $m$ and $n$. Now Theorem 4.5.5 states that the common multiples of $m$ and $n$ are exactly the multiples of $\mathrm{lcm}(m,n),$ and $\mathrm{lcm}(m,n)=mn$ because $m$ and $n$ are coprime. Hence we conclude that $x\in\mathbb{Z}$ satisfies $x\equiv a\bmod m$ and $x\equiv b\bmod n$ if and only if $mn|x-c$, that is, if and only if $x\equiv c\bmod mn$. $\Box$

Solution. We use the Euclidean algorithm to find the highest common factor of $9$ and $11$ and express it as an integral linear combination of them:

Hence $9$ and $11$ are coprime, so the Chinese Remainder Theorem applies, and in the notation introduced therein, we have $a=7$, $b=3$, $m=9$, $n=11$, $r=5$ and $s=-4$. Thus the pair of congruences has the solution

Now $-173=(-2)99+25$, so this simplifies to $x\equiv 25\bmod 99$, and therefore $x=25$ is the smallest positive simultaneous solution to the two congruences.

As we have seen, the congruences (5.3.1) can be solved simultaneously whenever the moduli $m$ and $n$ are coprime. We shall now give a complete description of when simultaneous solutions exist.

Proof. Set $d=\mathrm{hcf}(m,n)$.

‘‘$\Rightarrow$’’. Suppose that the two congruences can be solved simultaneously, so that there exists $x\in\mathbb{Z}$ such that $x\equiv a\bmod m$ and $x\equiv b\bmod n$; write $x-a=pm$ and $x-b=qn$, where $p,q\in\mathbb{Z}$. Then $a=x-pm$ and $b=x-qn$, so that

Since $d$ is a common factor of $m$ and $n$, Lemma 4.2.13 implies that $d$ is also a factor of $qn-pm$, and hence of $a-b.$

‘‘$\Leftarrow$’’. Suppose that $d$ divides $a-b$, say $a-b=dq$ for some $q\in\mathbb{Z}$. By Bézout’s Theorem, we can write $d=rm+sn$, where $r,s\in\mathbb{Z}$. Define $c=a-qrm\in\mathbb{Z}$. Then clearly $c\equiv a\bmod m$ (because $c-a=-qrm$), and also $c\equiv b\bmod n$ because

so that $c$ solves the two congruences simultaneously. $\Box$