The Chinese Remainder Theorem
The Chinese Remainder Theorem
Recall from the Systems of Linear Congruences that if we have a collection of linear congruences, say $\{ a_ix \equiv b_i \pmod m_i : i \in I \}$ (called a system), then a solution to the system is a set of $x$ which satisfy all of these linear congruences simultaneously.
We noted that while some systems of linear congruences may have solutions - others may not.
We will now look at a very well-known theorem that gives us a condition for when such a system has a solution.
Theorem 1 (The Chinese Remainder Theorem): Let $x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \vdots \\ x \equiv a_k \pmod {m_k}$ be a system of linear congruences and suppose that $(m_i, m_j) = 1$ for all $i, j \in \{ 1, 2, ..., k \}$ with $i \neq j$. Then there exists a unique solution to this linear congruence modulo $m_1m_2...m_k$. |
- Proof: Note that if $k = 1$ the theorem is trivially true.
- So consider the case when $k = 2$. Then we have the following system of linear congruences:
\begin{align} \quad x & \equiv a_1 \pmod {m_1} \\ \quad x & \equiv a_2 \pmod {m_2} \end{align}
- Since $x \equiv a_1 \pmod {m_1}$ there exists a $k_1 \in \mathbb{Z}$ with $x = a_1 + k_1m_1$ and substituting this into the second linear congruence gives us:
\begin{align} \quad (a_1 + k_1m_1) \equiv a_2 \pmod {m_2} \end{align}
- Or equivalently:
\begin{align} k_1m_1 \equiv (a_2 - a_1) \mod {m_2} \end{align}
- Now we know that $(m_1, m_2) = 1$, so, there must exist a unique solution $t$ for $k_1$ modulo $m_2$. So there exists a $k_2 \in \mathbb{Z}$ such that:
\begin{equation} k_1 = t + k_2m_2 \end{equation}
- Substituting this back into the original equation for $x$ and we get:
\begin{align} x &= a_1 + k_1m_1 \\ x &= a_1 + (t + k_2m_2)m_1 \\ x &= a_1 + t + km_1m_2 \end{align}
- Note that $x \equiv a_1 \pmod m_1$ and $x \equiv a_2 \pmod m_2$ so both linear congruences are satisfied.
- The completion of the proof requires a careful induction argument which we will omit. $\blacksquare$