We have taken some pains to note that $\Z_n$ is not a subset of $\Z$, and in particular that $\Z_n=\{[0],[1],\ldots,[n-1]\}$ is not the same as $\{0,1,\ldots,n-1\}$. The two sets certainly are closely related, however; $[a]=[b]$ if and only if $a$ and $b$ have the same remainder when divided by $n$, and the numbers in $\{0,1,\ldots,n-1\}$ are precisely all possible remainders—that's exactly why we chose them to be the "standard'' representatives when we write $\Z_n$. This is all by way of pointing out that anything involving $\Z_n$ can be thought of as being "about'' remainders. The principal result in this section, the Chinese Remainder Theorem, is an interesting fact about the relationship between $\Z_n$ for different values of $n$.

NB (That's Latin for "Pay attention!''): In the next two sections $( , )$ denotes an ordered pair, not a gcd.

Example 3.7.1 Both $\Z_{12}$ and $\Z_3\times \Z_4$ have 12 elements. In fact, there is a natural way to associate the elements of $\Z_{12}$ and $\Z_3\times \Z_4$ given by the following: $$ \begin{array}{ll} [0] &\leftrightarrow&([0],[0])&& [6]&\leftrightarrow&([6],[6])=([0],[2])\\ [1] &\leftrightarrow&([1],[1])&& [7]&\leftrightarrow&([7],[7])=([1],[3])\\ [2] &\leftrightarrow&([2],[2])&& [8]&\leftrightarrow&([8],[8])=([2],[0])\\ [3] &\leftrightarrow&([3],[3])=([0],[3])&& [9]&\leftrightarrow&([9],[9])=([0],[1])\\ [4]&\leftrightarrow&([4],[4])=([1],[0])&& [10]&\leftrightarrow&([10],[10])=([1],[2])\\ [5]&\leftrightarrow&([5],[5])=([2],[1])&& [11]&\leftrightarrow&([11],[11])=([2],[3])\\ \end{array} $$ The relationship used here, $[x]\leftrightarrow([x],[x])$, is about the simplest one could imagine, and this is one of those happy circumstances in which the simple, obvious choice is the one that works. Be sure you understand that the whole point of this example is to notice that every pair in $\Z_3\times \Z_4$ appears exactly once. When two sets are paired up in this way, so that every element of each set appears in exactly one pair, we say that there is a one-to-one correspondence between the sets. Note also that in the expression $[x]\leftrightarrow([x],[x])$, the symbol $[x]$ means three different things in the three places it appears, namely, $[x]\in\Z_{12}$, $[x]\in\Z_{3}$, and $[x]\in\Z_{4}$, respectively. This is an example of a general phenomenon. $\square$

Theorem 3.7.2 (Chinese Remainder Theorem) Suppose $n=ab$, with $a$ and $b$ relatively prime. For $x=0,1,…, n-1$, associate $[x]\in \Z_{n}$ with $([x], [x])\in \Z_a\times \Z_b$ (note that the symbol $[x]$ means different things in $\Z_n$, $\Z_a$ and $\Z_b$). This gives a one-to-one correspondence between $\Z_n$ and $\Z_a\times \Z_b$.

Proof. Observe that the two sets have the same number of elements. If we can show that associating $[x]$ with $([x], [x])$ does not associate any two distinct elements of $\Z_n$ with the same ordered pair in $\Z_a\times \Z_b$, then every element of $\Z_n$ will have to be associated with exactly one element of $\Z_a\times \Z_b$, and vice versa.

Suppose that $[x_1]$ and $[x_2]$ are assigned to the same pair in $\Z_a\times \Z_b$. We wish to show that $[x_1]=[x_2]$. We have $$ {{x_1}}\equiv x_2 \pmod a \quad and \quad {{x_1}}\equiv x_2 \pmod b, $$ in other words, both $a$ and $b$ must divide ${{x_1}}-x_2$. Since $a$ and $b$ are relatively prime, their product, $n$, also divides ${{x_1}}-x_2$. (See exercise 3.) That is, ${{x_1}}\equiv x_2\pmod n$ so $[x_1]=[x_2]$.$\qed$

Example 3.7.3 The theorem produces a correspondence between $\Z_{168}$ and $\Z_8\times \Z_{21}$. This correspondence, for example, takes $[97]$ to $([97], [97])=([1], [13])$. $\square$

Given an element of $\Z_n$, it is easy to find the corresponding element of $\Z_a\times \Z_b$: simply reduce modulo $a$ and $b$. Is there a way to reverse this? In other words, given $([y], [z])\in \Z_a\times \Z_b$ can we find the element of $\Z_n$ to which it corresponds? In fact, using the ubiquitous Extended Euclidean Algorithm it is easy.

Example 3.7.4 Which element of $\Z_{168}$ corresponds to the pair $([7],[5])\in \Z_8\times \Z_{21}$? If we apply the Extended Euclidean Algorithm to 8 and 21, we get $1=8\cdot 8 + (-3)\cdot 21$. Note that $8\cdot 8=64$ is congruent to 0 mod 8 and 1 mod 21, and $(-3)\cdot 21=-63$ is congruent to 1 mod 8 and 0 mod 21. Therefore $$ \eqalign{ 5\cdot 64+ 7\cdot (-63)\equiv 5\cdot 0 +7\cdot 1& =7 \pmod 8,\cr 5\cdot 64+ 7\cdot (-63)\equiv 5\cdot 1 +7\cdot 0& =5 \pmod {21},\cr} $$ so $$5\cdot 64+ 7\cdot (-63)=-121\equiv 47\pmod {168}$$ works, that is, $[47]\leftrightarrow ([7],[5])$. $\square$

This last example can be phrased in a somewhat different way. Given $7$ and $5$, we are asking whether the two simultaneous congruences $x\equiv 7\pmod 8$ and $x\equiv 5\pmod {21}$ can be solved, that is, is there an integer $x$ that has remainder $7$ when divided by $8$ and remainder $5$ when divided by $21$. This makes the name "Chinese Remainder Theorem'' seem a little more appropriate.

The Chinese Remainder Theorem is a useful tool in number theory (we'll use it in section 3.8), and also has proved useful in the study and development of modern cryptographic systems.

Exercises 3.7

Ex 3.7.1 Construct the correspondences between the indicated sets.

Ex 3.7.2 Given the following values of $a$, $b$, and the element $([y], [z])$ of $\Z_a\times \Z_b$, use the Extended Euclidean Algorithm to find the corresponding element of $\Z_{ab}$. In other words, solve the simultaneous congruences $x\equiv y\pmod a$ and $x\equiv z\pmod {b}$, as in Example 3.7.4.

Ex 3.7.3 The following fact was used in the proof of the Chinese Remainder Theorem: If $a$ and $b$ both divide $c$, and $a$ and $b$ are relatively prime, then $ab$ divides $c$. Prove the statement.

Ex 3.7.4 Suppose in the correspondence between $\Z_{150}$ and $\Z_{25}\times \Z_6$ that $[x]$ corresponds to $([10], [5])$ and $[y]$ corresponds to $([21], [4])$. What does $[x+y]$ correspond to? What does $[xy]$ correspond to?

Ex 3.7.5 Suppose $n=ab$ where $a$ and $b$ are not relatively prime. We can still associate $[x]\in \Z_n$ with $([x],[x])\in \Z_a\times \Z_b$. Show that this fails to be a one-to-one correspondence. (Hint: Let $L$ be the least common multiple of $a$ and $b$. Compare $[0]$ and $[L]$.)

Ex 3.7.6 Observe that there are one-to-one correspondences between $\Z_{60}$ and $\Z_4\times \Z_{15}$ and between $\Z_4\times \Z_{15}$ and $\Z_4\times \Z_3\times \Z_{5}$.

Ex 3.7.7 Show that $\U_n=\{[x]\in \Z_n: [x]\ne [0]\}$ if and only if $n$ is a prime.

Ex 3.7.8 Using example 3.7.4 as a guide, give an alternate proof of Theorem 3.7.2, by showing that for every $([x],[y])\in\Z_a\times\Z_b$ there is a $[z]\in\Z_n$ such that $([z],[z])=([x],[y])$.