Let $n_{1},\ n_{2},\ n_{3},\ \cdots,\ n_{r}$ be positive integers such that $\gcd(n_{i}, n_{j})=1$ for $1 \le \quad i\neq j \quad \le r$

Then the simultaneous linear congruences $ x\equiv a_i \pmod {n_i} $ for all $1 \le i \le r$ has a solution satisfying all these equations. Moreover the solution is unique modulo $n_1 n_2 n_3 \cdots n_r$.

Proof of Existence. I skip proof of uniqueness. Let $n=n_{1}n_{2}n_{3}\cdots n_{r}$. For each integer $k=1,2,3,\ \cdots,\ r$, let $N_{k} =n_{1}n_{2}n_{3}\cdots n_{k-1}n_{k+1}\cdots n_{r}$ = the product of all the moduli $n_{i}$ with the modulus $n_{k}$ missing.

(1) How can you prefigure to consider this, to start the proof? This product is uncanny?

We are given that $\gcd(n_i, n_j)=1$ for $i\neq j$. By reason of $\gcd(a,b) = \gcd(a,c) =1,$ then $\gcd(a, bc) = 1$. Thence $\gcd(N_k, n_k ) = 1$.

Consider if the linear congruence $N_k x\equiv 1 \pmod{n_k}$ has any solutions.

(2) Where does $N_{k}x\equiv 1 \pmod{n_k}$ hail from? How can you prefigure to consider this?

Since $\gcd(N_k, n_k) = 1$, thence by reason of the Linear Congruence Theorem, the linear congruence $N_{k}x\equiv 1 \pmod {n_k}$ has a unique solution. Dub it $x_k$, thence $$ \color{magenta}{ N_k x_k \equiv 1\pmod{n_k}. \tag{♯} }$$

We construct a solution which satisfies all the given simultaneous linear congruences:

$$ x^* =a_1 N_1 x_1 + a_2 N_2 x_2 + a_3 N_3 x_3 +\cdots + a_r N_r x_r $$

(3) Where does this construction hail from? Can you calculate this?

Let us see if this satisfies the first given linear congruence $ x\equiv a_1 \pmod {n_1} $.

By the above definition of $N_{2},\ N_{3},\ N_{4}, \ldots, N_{r}$ these numbers are multiplies of $n_{1}$.

Therefore $ a_{2}N_{2}x_{2}\equiv 0\pmod {n_1}, a_{3}N_{3}x_{3}\equiv 0 \pmod {n_1} \cdot,\ a_{r}N_{r}x_{r}\equiv 0 \pmod {n_1} $,

Thence if I take $x^*$ to modulus $n_1$, then by cause of $\color{magenta}{(♯)}$ $$\begin{align} x^* & \equiv a_{1}N_{1}x_{1}+a_{2}N_{2}x_{2}+a_{3}N_{3}x_{3}+\cdots+a_{r}N_{r}x_{r} \pmod {n_1} \\ & \equiv a_{1} \color{magenta}{ N_{1}x_{1} }+0+0+\cdots+0 \\ & \equiv a_{1} \color{magenta}{ 1 } \pmod {n_1} \end{align}$$

Hence $x^*$ satisfies the first simultaneous congruence $x\equiv a_1 \pmod {n_1}$. Similarly we can show that the solution constructed satisfies the remaining congruences.


(1) I agree that the product is not that natural at first sight, and maybe someone will give an intuitive or better interpretation, but here is how I see the proof strategy with an analogy of linear algebra : we try to build the $x^{*}$ that verifies the conditions $x^{*} \equiv a_i \mod{n_i}$. Somehow, these conditions can be seen as "projection" equations : when we take the congruence modulo one of the $n_k$s, we need to satisfy a given equation. The hypothesis on the $gcd$s would be a "freedom" hypothesis in a vector space. Once you see the problem like this, this is natural to try to build something similar to a basis (ie coordinates system), such that we can set easily the wanted values $x^{*} \mod{n_k}$ independently.

The product is the first step toward this goal. We know that the product of all $n_k$ is obviously zero modulo any $n_k$, but by removing one, you build a number $N_k$ that is zero modulo any $n_i$ EXCEPT $n_k$ (because of relative primality, it is even invertible modulo $n_k$). You can find some similar constructions e.g. in Lagrange interpolation, when you build very similarly polynomials $L_k$ that are null at any $b_i$ (where $b_i$ are given real numbers) except $b_k$, and there are several other examples. Here, these $N_k$ act as filters, selecting only one value when taking the modulo $n_k$. Well, that's interesting, because if you take a linear combination of these numbers, you can indeed do something like a decomposition on a basis : let $$y=\sum_{i=1}^{r} a_i N_i$$ , then you can do a "projection" and check that : $$y \equiv a_i N_i \mod{n_i}$$

But you don't know $N_i$'s value modulo $n_i$, and you are not already done. You would like to get rid of this annoying $N_i$'s value :

(2) We do something like a normalization. If we could transform $N_i$'s to a new "basis" $N'_i$ such that $$N'_i \equiv 1 \mod {n_i}$$, this would be perfect. This is exactly what is done : the $gcd$'s hypothesis allow you to find an inverse $x_i$ for $N_i \mod {a_i}$, and doing the multiplication, you get a new "unitary basis" $N'_i = x_i N_i$. Once again, you do quite the same than with Lagrange polynomials, when dividing by $X-b_k$ in $L_k=\frac{\prod_{i \neq k}(X-b_i)}{X-b_k}$ such that $L_k(b_k)=1$. Now you just have to :

(3) Build your solution by decomposing it on the new "coordinate system" you just elaborated $$x^{*} = \sum_{i=1}^{r} a_i N'_i$$

You can indeed calculate this, because the inverse $x_i$ you have to find in (2) is given by the extended Euclid algorithm (that gives the bezout coefficients $u,v$ such that $u n_i + v N_i = 1$, then taking the congruence you see that in fact $v \mod{n_i}$ is a solution). Once you have $x_k$, since you have $n_k$ and $a_k$, nothing prevents you from practically compute $x^{*}$.


An example might help. Suppose we wish to solve the simultaneous congruences \begin{align} x &\equiv 2 \pmod{8}\\ x &\equiv 5 \pmod{9}\\ x &\equiv 6 \pmod{25}\\ \end{align}

Note that $8, 9,$ and $25$ are pairwise prime and $8 \times 9 \times 25 = 1800$. The CRT states that the mapping $$f:\mathbb Z_{1800} \to \mathbb Z_{8}\times \mathbb Z_{9} \times \mathbb Z_{25}$$ defined by $f(\bar x) = (\bar x, \bar x, \bar x)$ is a group isomorphism. We are specifically seeking an $x$ such that $f(\bar x) = (\bar 2, \bar 5, \bar 6)$.

Because $f$ is an isomorphism, there exists integers $e_1, e_2, $ and $e_3$ such that \begin{align} f(\bar{e_1}) &= (\bar 1, \bar 0, \bar 0)\\ f(\bar{e_2}) &= (\bar 0, \bar 1, \bar 0)\\ f(\bar{e_3}) &= (\bar 0, \bar 0, \bar 1)\\ \end{align}

It follows that $x \equiv 2e_1 + 5e_2 + 6e_3 \pmod{1800}$.

So we need to find the values of $e_1, e_2,$ and $e_3$.

From $(\bar{e_1}, \bar{e_1}, \bar{e_1}) = f(\bar{e_1}) = (\bar 1, \bar 0, \bar 0)$, we conclude that \begin{align} e_1 &\equiv 1 \pmod 8\\ e_1 &\equiv 0 \pmod{9}\\ e_1 &\equiv 0 \pmod{25}\\ \end{align} So $e_1$ must be a multiple of $9$ and of $25$. So, for some $z, \; e_1 = z\cdot9 \cdot 25 = 225z$. Then \begin{align} e_1 &\equiv 1 \pmod 8\\ 225z &\equiv 1 \pmod 8\\ z &\equiv 1 \pmod 8\\ e_1 &\equiv 225 \pmod{1800} \end{align}

Similarly \begin{align} e_2 &\equiv 1 \pmod 9\\ 200z &\equiv 1 \pmod 9\\ 2z &\equiv 1 \pmod 9\\ z &\equiv 5 \pmod 9\\ e_2 &\equiv 1000 \pmod{1800} \end{align}

and \begin{align} e_3 &\equiv 1 \pmod{25}\\ 72z &\equiv 1 \pmod{25}\\ -3z &\equiv 1 \pmod{25}\\ z &\equiv 8 \pmod{25}\\ e_3 &\equiv 576 \pmod{1800} \end{align}

So \begin{align} x &\equiv 2e_1 + 5e_2 + 6e_3 \pmod{1800}\\ x &\equiv 2 \cdot 225 + 5 \cdot 1000 + 6 \cdot 576 \pmod{1800}\\ x &\equiv 450 + 5000 + 3456 \pmod{1800}\\ x &\equiv 8906 \pmod{1800}\\ x &\equiv 1706 \pmod{1800}\\ \end{align}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.