Suppose we are asked to solve

for $x$. Notice if we have a solution $y$, then $y+35$ is also a solution, and in fact so is $y$ plus any mulitple of $35$. So we only need to look for solutions modulo $35$. By brute force, we find the only solution is $x=17(mod35)$.

For any system of equations like this, the Chinese Remainder Theorem not only tells us that there is a solution, but also that it is unique. Additonally, the theorem describes how to find the solution efficiently.

Theorem: Let $p,q$ be coprime. Then the system of equations

has a unique solution for $x$ modulo $pq$.

The reverse direction is trivial: given $x\in {\mathbb{Z}}_{pq}$, we can reduce $x$ modulo $p$ and $x$ modulo $q$ to obtain two equations of the above form.

Proof: Let $p_1=p^{-1}(modq)$ and $q_1=q^{-1}(modp)$. These must exist since $p,q$ are coprime. Then we claim that if $y$ is an integer such that

then $y$ satisfies both equations:

Modulo $p$, we have $y=aq{q}_1=a(modp)$ since $q{q}_1=1(modp)$. Similarly $y=b(modq)$. Thus $y$ is a solution for $x$.

It remains to show no other solutions exist modulo $pq$. If $z=a(modp)$ then $z-y$ is a multiple of $p$. If $z=b(modq)$ as well, then $z-y$ is also a multiple of $q$. Since $p$ and $q$ are coprime, this implies $z-y$ is a multiple of $pq$, hence $z=y(modpq)$. $\blacksquare$

This theorem implies we can represent an element of ${\mathbb{Z}}_{pq}$ by one element of ${\mathbb{Z}}_p$ and one element of ${\mathbb{Z}}_q$, and vice versa. In other words, we have a bijection between ${\mathbb{Z}}_{pq}$ and ${\mathbb{Z}}_p\times {\mathbb{Z}}_q$.

Examples: We can write $17\in {\mathbb{Z}}_{35}$ as $(\mathrm{2,3})\in {\mathbb{Z}}_5\times {\mathbb{Z}}_7$. We can write $1\in {\mathbb{Z}}_{pq}$ as $(\mathrm{1,1})\in {\mathbb{Z}}_p\times {\mathbb{Z}}_q$.

In fact, this correspondence goes further than a simple relabelling. Suppose $x,y\in {\mathbb{Z}}_{pq}$ correspond to $(a,b),(c,d)\in {\mathbb{Z}}_p\times {\mathbb{Z}}_q$ respectively. Then a little thought shows $x+y$ corresponds to $(a+c,b+d)$, and similarly $xy$ corresponds to $(ac,bd)$.

A practical application: if we have many computations to perform on $x\in {\mathbb{Z}}_{pq}$ (e.g. RSA signing and decryption), we can convert $x$ to $(a,b)\in {\mathbb{Z}}_p\times {\mathbb{Z}}_q$ and do all the computations on $a$ and $b$ instead before converting back. This is often cheaper because for many algorithms, doubling the size of the input more than doubles the running time.

Example: To compute $17\times 17(mod35)$, we can compute $(2\times \mathrm{2,3}\times 3)=(\mathrm{4,2})$ in ${\mathbb{Z}}_5\times {\mathbb{Z}}_7$, and then apply the Chinese Remainder Theorem to find that $(\mathrm{4,2})$ is $9(mod35)$.

Let us restate the Chinese Remainder Theorem in the form it is usually presented.

Theorem: Let $m_1,...,m_n$ be pairwise coprime (that is $\gcd (m_i,m_j)=1$ whenever $i\ne j$). Then the system of $n$ equations

has a unique solution for $x$ modulo $M$ where $M=m_1...m_n$.

Proof: This is an easy induction from the previous form of the theorem, or we can write down the solution directly.

Define $b_i=M/m_i$ (the product of all the moduli except for $m_i$) and $b{\prime }_i=b_i^{-1}(mod{m}_i)$. Then by a similar argument to before,

is the unique solution.$\blacksquare$

An important consequence of the theorem is that when studying modular arithmetic in general, we can first study modular arithmetic a prime power and then appeal to the Chinese Remainder Theorem to generalize any results. For any integer $n$, we factorize $n$ into primes $n=p_1^{k_1}...p_m^{k_m}$ and then use the Chinese Remainder Theorem to get

To prove statements in ${\mathbb{Z}}_{p^k}$, one starts from ${\mathbb{Z}}_p$, and inductively works up to ${\mathbb{Z}}_{p^k}$. Thus the most important case to study is ${\mathbb{Z}}_p$.