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)

      Let n_1,n_2,\cdots,n_k be positive integers that are pairwise relatively prime. Let a_1,a_2,\cdots,a_k be any integers. Then the following system of linear congruence equations

        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
      \cdots
      \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)

      Let n_1,n_2,\cdots,n_k be positive integers that are pairwise relatively prime. Then for any integers c and d, the following linear congruences hold

        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

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s