]> Number Theory - The Chinese Remainder Theorem

## The Chinese Remainder Theorem

Suppose we are asked to solve

$x=2\left(mod5\right)$ $x=3\left(mod7\right)$

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\left(mod35\right)$.

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

$x=a\left(modp\right)$ $x=b\left(modq\right)$

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

The reverse direction is trivial: given $x\in {ℤ}_{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}\left(modq\right)$ and ${q}_{1}={q}^{-1}\left(modp\right)$. These must exist since $p,q$ are coprime. Then we claim that if $y$ is an integer such that

$y=aq{q}_{1}+bp{p}_{1}\left(modpq\right)$

then $y$ satisfies both equations:

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

It remains to show no other solutions exist modulo $pq$. If $z=a\left(modp\right)$ then $z-y$ is a multiple of $p$. If $z=b\left(modq\right)$ 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\left(modpq\right)$. $\blacksquare$

This theorem implies we can represent an element of ${ℤ}_{pq}$ by one element of ${ℤ}_{p}$ and one element of ${ℤ}_{q}$, and vice versa. In other words, we have a bijection between ${ℤ}_{pq}$ and ${ℤ}_{p}×{ℤ}_{q}$.

Examples: We can write $17\in {ℤ}_{35}$ as $\left(2,3\right)\in {ℤ}_{5}×{ℤ}_{7}$. We can write $1\in {ℤ}_{pq}$ as $\left(1,1\right)\in {ℤ}_{p}×{ℤ}_{q}$.

In fact, this correspondence goes further than a simple relabelling. Suppose $x,y\in {ℤ}_{pq}$ correspond to $\left(a,b\right),\left(c,d\right)\in {ℤ}_{p}×{ℤ}_{q}$ respectively. Then a little thought shows $x+y$ corresponds to $\left(a+c,b+d\right)$, and similarly $xy$ corresponds to $\left(ac,bd\right)$.

A practical application: if we have many computations to perform on $x\in {ℤ}_{pq}$ (e.g. RSA signing and decryption), we can convert $x$ to $\left(a,b\right)\in {ℤ}_{p}×{ℤ}_{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×17\left(mod35\right)$, we can compute $\left(2×2,3×3\right)=\left(4,2\right)$ in ${ℤ}_{5}×{ℤ}_{7}$, and then apply the Chinese Remainder Theorem to find that $\left(4,2\right)$ is $9\left(mod35\right)$.

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

## For Several Equations

Theorem: Let ${m}_{1},...,{m}_{n}$ be pairwise coprime (that is $\mathrm{gcd}\left({m}_{i},{m}_{j}\right)=1$ whenever $i\ne j$). Then the system of $n$ equations

$x={a}_{1}\left(mod{m}_{1}\right)$ $...$ $x={a}_{n}\left(mod{m}_{n}\right)$

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}\left(mod{m}_{i}\right)$. Then by a similar argument to before,

$x=\sum _{i=1}^{n}{a}_{i}{b}_{i}b{\prime }_{i}\left(modM\right)$

is the unique solution.$\blacksquare$

## Prime Powers First

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

${ℤ}_{n}={ℤ}_{{p}_{1}^{{k}_{1}}}×...×{ℤ}_{{p}_{m}^{{k}_{m}}}$

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