Problem 27 : The Chinese Remainder Theorem
I have been meaning to write this out for a long time now. This is a powerful theorem that to me allows one to effectively deduce the subspace of solutions to a series of congruence relations. As far as history goes, the earliest known statement of the theorem is present in the 3rd-century book Sun-tzu Suan-ching by Sun-tzu. Here is an embedded calculator for playing around with 2 congruences.
Theorem Statement
Suppose that we have a sequence of \(k\) natural numbers \(n_1, n_2, \ldots n_k\) that are relatively prime i.e. their greatest common divisor, gcd \((n_i,n_j) = 1 \forall i \neq j\).
Then the following system of equations,
\[\begin{gathered} x \equiv a_1 \quad\left(\bmod n_1\right) \\ \vdots \\ x \equiv a_k \quad\left(\bmod n_k\right) \end{gathered}\]has a unique solution modulo \(n_1.n_2.n_3 \ldots n_k\).
The Modulo Inverse
Before beginning the proof, I would like to define the modulo inverse. The modulo inverse say, \(x\) of \(a\) w.rt. \(m\) may be uniquely defined under certain conditions that will be clear soon.
\[a.x \equiv 1 \quad\left(\bmod m\right)\]Using the definition of modulo, \(ax - 1\) should be a multiple of \(m\).
\[\implies (ax -1) = my \\ \implies ax - my = 1\]for some integer \(y\). A careful look at the expression reveals that if \(a,m\) are not relatively prime or equivalently, gcd\((a,m) \neq 1\), we can find a divisor \(d > 1\) such that,
\[\frac{a}{d}x - \frac{m}{d}y = \frac{1}{d}\]Now we have an issue, because LHS is an integer but the RHS is a fraction. So, there is no solution for integers \(x\) and \(y\).
So, the condition for modulo inteverse of \(a\) w.r.t. \(m\) to exist, the condition that naturally arises from the definition is gcd\((m,a) = 1\).
Proof
Let \(N = \Pi_{i=1}^{k} n_i\) be the product of the relatively prime sequence \({n_i}\). To make this problem tractable, we need to uniquely consider the influence of each congruence relation in the system of congruences provided in the Theorem’s statement. To this end, we can define \(N_i = \frac{N}{n_i}\) such that \(N_i\) is a product of all the \(n_j\)’s for \(j \neq i\).
This allows us to claim that \(\exists x_i \backepsilon N_i x_i \equiv 1 \quad\left(\bmod n_i \right)\). Where we simply used the fact that gcd\((N_i,n_i) = 1\) along with the definition of the modulo inverse.
\[\implies b_i N_i x_i \equiv b_i \quad\left(\bmod n_i \right)\]Also, by design, \(b_i N_i x_i \equiv 0 \quad\left(\bmod n_j \right)\) for \(j \neq i\).
So, the sum \(X = \sum_{i=1}^{k} b_i N_i x_i\) will satisfy all the congruences. This proves the existence of the solution.
For uniqueness, we assume that \(\exists\) distinct \(X,Y\) such that \(X \equiv b_j \quad\left(\bmod n_j \right)\) and \(Y \equiv b_j \quad\left(\bmod n_j \right)\) for \(j = 1 \ldots k\).
Then, the difference of the two \(X - Y \equiv 0 \quad\left(\bmod n_j \right)\). Since, the sequence \({n_i}\) is relatively prime, the only way in which \(X - Y\) can be divisible by all \({n_i}\) is if they are also divisible by their product. So, \(N\) divides \(X - Y\). Equivalently,
\[X \equiv Y \left(\bmod N \right)\]Therefore, \(X\) and \(Y\) are the same solution modulo \(N\).