Proving Chinese Remainder Theorem

In this post, we consider systems of linear congruence equations with respect to pairwise relatively prime moduli. The theorem we prove here is known as the Chinese remainder theorem (see Theorem 1 below). It is useful in many contexts. For an example, see the blog post Introducing Carmichael numbers (used in proving the Korselt’s Criterion). Theorem 2 below is a useful corollary of the Chinese remainder theorem. For examples of applications, see Primitive roots of twice the powers of odd primes and The primitive root theorem (used in proving the primitive root theorem).

Theorem 1 (Chinese Remainder Theorem)

$n_1,n_2,\cdots,n_k$

$a_1,a_2,\cdots,a_k$

$x \equiv a_1 \ (\text{mod} \ n_1)$

$x \equiv a_2 \ (\text{mod} \ n_2)$

$x \equiv a_3 \ (\text{mod} \ n_3)$

$\cdots$
$\cdots$
$\cdots$

$x \equiv a_k \ (\text{mod} \ n_k)$

has a solution $x=b$ .

Furthermore, $x=b_0$ is another solution to the above system of equations if and only if $b_0 \equiv b \ (\text{mod} \ n_1 n_2 \cdots n_k)$ .

Proof of Theorem 1
Let $n=n_1 n_2 \cdots n_k$ . For each $i=1,\cdots,k$ , let $\displaystyle t_i=\frac{n}{n_i}$ . Note that $t_i$ is the product of all $n_j$ where $j \ne i$ . So $t_i$ and $n_i$ are relatively prime. Thus for each $i$ , $t_i$ has a multiplicative inverse modulo $n_i$ . Let $(t_i)^{-1}$ be the inverse of $t_i$ . Now define $g_i=t_i \cdot (t_i)^{-1}$ for each $i$ .

It is clear that for each $i$ , $g_i \equiv 1 \ (\text{mod} \ n_i)$ for each $i$ and $g_i \equiv 0 \ (\text{mod} \ n_j)$ for all $j \ne i$ . Now define $b$ as the following:

$b=g_1 \cdot a_1+g_2 \cdot a_2+\cdots+g_k \cdot a_k$

It follows that $b \equiv a_i \ (\text{mod} \ n_i)$ for each $i=1,\cdots,k$ . Thus $x=b$ is a solution that we are looking for.

It remains to show that solutions to the above system of equations are unique modulo $n$ . Suppose that $b_0 \equiv b \ (\text{mod} \ n)$ . This means that $b_0=b+n_1 n_2 \cdots n_k \cdot y$ for some integer $y$ . It follows from this equation that $b_0 \equiv b \ (\text{mod} \ n_i)$ for each $i$ . Thus $b_0 \equiv a_i \ (\text{mod} \ n_i)$ for each $i$ .

On the other hand, suppose that $x=b_0$ is another solution to the above system of equations. Then $b_0 \equiv b \ (\text{mod} \ n_i)$ for each $i$ . So $n_i \ \lvert \ (b_0-b)$ for each $i$ . We have the following equations

$b_0-b=n_1 \cdot c_1$

$b_0-b=n_2 \cdot c_2$

$b_0-b=n_3 \cdot c_3$

$\cdots$

$b_0-b=n_k \cdot c_k$

for some integers $c_1, c_2, \cdots, c_k$ . From these equations, it follows that $b_0-b=n_1 n_2 \cdots n_k \cdot c$ for some integer $c$ . This is due to the fact that the integers $n_1,n_2,\cdots,n_k$ are relatively prime. For example, from the first two equations, $n_2 \ \lvert \ n_1 \cdot c_1$ . Since $n_1$ and $n_2$ are relatively prime, $n_2 \ \lvert \ c_1$ , we have $b_0-b=n_1 \cdot n_2 \cdot c_{1,2}$ for some integer $c_{1,2}$ . Then consider this new equation along with the third equation above, we have $n_3 \ \lvert \ n_1 \cdot n_2 \cdot c_{1,2}$ . Because the integers $n_j$ are pairwise relatively prime, $n_3 \ \lvert \ c_{1,2}$ . So we can further factor $c_{1,2}$ into $n_3 \cdot c_{1,3}$ for some integer $c_{1,3}$ . Continuing this process, we can obtain $b_0-b=n_1 n_2 \cdots n_k \cdot c$ . It follows that $b_0 \equiv b \ (\text{mod} \ n_1 n_2 \cdots n_k)$ . $\blacksquare$

Theorem 2 (Corollary of Chinese Remainder Theorem)

$n_1,n_2,\cdots,n_k$

$c$

$d$

$c \equiv d \ (\text{mod} \ n_1)$

$c \equiv d \ (\text{mod} \ n_2)$

$c \equiv d \ (\text{mod} \ n_3)$

$\cdots$
$\cdots$
$\cdots$

$c \equiv d \ (\text{mod} \ n_k)$

if and only of $c \equiv d \ (\text{mod} \ n_1 n_2 \cdots n_k)$ .

Proof of Theorem 2
This is an easy consequence of Theorem 1. Let $d=a_1=a_2=\cdots=a_k$ . Then $x=d$ would be a solution to the resulting system of linear congruence equations in Theorem 1. Theorem 2 then follows from the fact that any other solution to the system is congruent to $d$ modulo $n_1 n_2 \cdots n_k$ . $\blacksquare$

___________________________________________________________________________________________________________________

Exploring Number Theory

A blog on elementary number theory

Proving Chinese Remainder Theorem

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply