Proving The General Chinese Remainder Theorem

Let \(k\) be some positive integer. Let \(m_1, \ldots , m_k\) be positive integers and let \(a_1 , \ldots , a_k\) be integers. The system of simultaneous congruences:

$$\begin{gather} x ≡ a_1 \bmod m_1 \\ x ≡ a_2 \bmod m_2 \\ \vdots \\ x ≡ a_k \bmod m_k \end{gather}$$

has a solution if and only if \((m_i, m_j) | a_i - a_j\) for all pairs of integers \(i\) and \(j\). When this condition is satisfied, there is a unique solution modulo \([m_1, \ldots , m_k]\). This is the general Chinese remaidner theorem.

How do we even prove this? We are going to use mathematical induction here, where \(k=2\) is the base case. The base case is already proved, so we are going to focus on the induction step.

Suppose the general Chinese remainder theorem holds true for \(k\) congruences. Does it then also hold true for \(k+1\) as well?

$$\begin{gather} x ≡ a_1 \bmod m_1 \\ x ≡ a_2 \bmod m_2 \\ \vdots \\ x ≡ a_k \bmod m_k \\ x ≡ a_{k+1} \bmod m_{k+1} \end{gather}$$

Let's say we only consider the first and last congruence of this system:

$$\begin{gather} x ≡ a_1 \bmod m_1 \\ x ≡ a_{k+1} \bmod m_{k+1} \end{gather}$$

As shown in the base case, thi system has a solution if and only if \((m_1,m_{k+1}) | a_{k+1} - a_1\), and the solution is unique modulo \([m_1,m_{k+1}]\).

We can pair \(x ≡ a_{k+1} \bmod m_{k+1}\) with any of the first \(k\) congruences to show that the pair has a solution if and only if \((m_i,m_{k+1}) | a_{k+1} - a_i\), and the solution is unique modulo \([m_i,m_{k+1}]\) where \(1 \le i \le k\).

Now let's go back to considering all of our congruences:

$$\begin{gather} x ≡ a_1 \bmod m_1 \\ x ≡ a_2 \bmod m_2 \\ \vdots \\ x ≡ a_k \bmod m_k \\ x ≡ a_{k+1} \bmod m_{k+1} \end{gather}$$

Consider a pair of congruences: \((x ≡ a_{k+1} \bmod m_{k+1})\) and \((x ≡ a_i \bmod m_i)\) where \(1 \le i \le k\). If \((m_{k+1},m_i) \nmid a_i - a_{k+1}\), then a solution for this pair does not exist. If a solution for this pair of congruences does not exist, then a solution with all \(k+1\) congruences cannot exist.

$$\begin{gathered} \left[ \begin{aligned} x ≡& a_i \bmod m_i \\ x ≡& a_{k+1} \bmod m_{k+1} \end{aligned} \right] \\ \text{doesn't have a solution} \end{gathered} \implies \left[ \begin{aligned} x ≡& a_1 \bmod m_1 \\ x ≡& a_2 \bmod m_2 \\ \vdots& \\ x ≡& a_k \bmod m_k \\ x ≡& a_{k+1} \bmod m_{k+1} \end{aligned} \right] \quad \text{ doesn't have a solution} $$

This means that for a solution for all \(k+1\) congruences to exist, each one of the \(k\) congruences with the \(k+1\)th congruence should have a solution. This means, for a solution for all \(k+1\) congruences to exist, it should be true that \((m_{k+1},m_i) | a_i - a_{k+1}\) for all \(i\) where \(1 \le i \le k\).

Also, the contrapositive of the above is:

$$ \left[ \begin{aligned} x ≡& a_1 \bmod m_1 \\ x ≡& a_2 \bmod m_2 \\ \vdots& \\ x ≡& a_k \bmod m_k \\ x ≡& a_{k+1} \bmod m_{k+1} \end{aligned} \right] \quad \text{ has a solution} \implies \begin{gathered} \left[ \begin{aligned} x ≡& a_i \bmod m_i \\ x ≡& a_{k+1} \bmod m_{k+1} \end{aligned} \right] \\ \text{ has a solution} \end{gathered} \implies (m_{k+1},m_i) | a_i - a_{k+1}$$

We can conclude that when all the \(k+1\) congruences are being solved together, if a solution can exists, then \((m_{k+1},m_i) | a_i - a_{k+1}\) for all \(i\) where \(1 \le i \le k\).

Can we prove the converse, that if \((m_{k+1},m_i) | a_i - a_{k+1}\) for all \(i\), then a solution exists? Suppose the first \(k\) congruences have a unique solution \(A\) modulo \([m_1,\ldots,m_k]\):

$$ \begin{gathered} x ≡ A ≡ a_1 \bmod m_1 \\ x ≡ A ≡ a_2 \bmod m_2 \\ \vdots \\ x ≡ A ≡ a_k \bmod m_k \\ x ≡ a_{k+1} \bmod m_{k+1} \end{gathered}$$

Any integer that is congruent to \(A\) modulo \([m_1,\ldots,m_k]\) is a solution to the first \(k\) congruences. If \((m_{k+1},m_1) | a_1 - a_{k+1}\), then \((m_{k+1},m_1) | A - a_{k+1}\), which means:

$$a_{k+1} ≡ A \bmod (m_{k+1},m_1) $$

Similarly:

$$ a_{k+1} ≡ A \bmod (m_{k+1},m_2) $$

Using this lemma:

$$ a_{k+1} ≡ A \bmod [(m_{k+1},m_1),(m_{k+1},m_2)] $$

Using this lemma:

$$ a_{k+1} ≡ A \bmod (m_{k+1}, [m_1,m_2]) $$

Similarly:

$$ \begin{aligned} a_{k+1} &≡ A \bmod (m_{k+1}, m_3) \\ a_{k+1} &≡ A \bmod (m_{k+1}, [m_1,m_2]) \\ \therefore a_{k+1} &≡ A \bmod [(m_{k+1}, m_3), (m_{k+1}, [m_1,m_2])] \\ a_{k+1} &≡ A \bmod (m_{k+1}, [m_3, [m_1,m_2]]) \\ a_{k+1} &≡ A \bmod (m_{k+1}, [m_3, m_1,m_2]]) \end{aligned}$$

Doing this multiple times:

$$ a_{k+1} ≡ A \bmod (m_{k+1}, [m_1,\ldots,m_k]) $$

If \((m_{k+1}, [m_1,\ldots,m_k])| A - a_{k+1}\), then according to the base case, the system below has a solution:

$$ \begin{gathered} x ≡ A \bmod [m_1,\ldots,m_k] \\ x ≡ a_{k+1} \bmod m_{k+1} \end{gathered}$$

If there is an integer \(x\) such that \(x\) is congruent to \(A\) modulo \([m_1,\ldots,m_k]\), and also congruent to \(a_{k+1}\) modulo \(m_{k+1}\), then \(x\) is a solution for all \(k+1\) congruences.

In conclusion, if we have a system that solves \(k\) congruences, then when we introduce the \(k+1\)th congruence, the entire system has a solution if and only if \((m_{k+1},m_i) | a_i - a_{k+1}\) for all \(i\) where \(1 \le i \le k\), and the solution is unique modulo \([m_1,\ldots, m_{k+1}]\).

Styles

(uses cookies)