Why does the CRT formula yield a solution of a congruence system?

Question

I understand there is a method for solving simultaneous modular equations. For example; $$x = 2 \mod{3}$$ $$x = 3 \mod{5}$$ $$x = 2 \mod{7}$$ We find numbers equal to the product of every given modulo except one of them - giving $5 \cdot 7$, $3 \cdot 7$ and $3 \cdot 5$. We then find the multiplicative inverses of these numbers with modulo equal to the number missing from the product. The numbers found are then 2, 1 and 1 in this case. The value of x is then given by: $$x = 2 \cdot (5 \cdot 7) \cdot 2 + 3 \cdot (3 \cdot 7) \cdot 1 + 2 \cdot (3 \cdot 5) \cdot 1 = 233 = 23 \mod{3\cdot5\cdot7}$$

But I do not understand how this method correctly gives the value of $x$. I understand that the Chinese remainder theorem proves that there is a unique value of $0\le x \lt 3\cdot5\cdot7 \mod{3\cdot5\cdot7}$ but can someone please explain why this method finds this value of x?

Answer 1

This is a generalisation of the formula for the solutions of a system of two congruences modulo two coprime numbers $a$ and $b$?. This formula uses a Bézout's relation: $\;ua+vb=1$ and it is: $$\begin{cases} x\equiv \alpha\mod a,\\ x\equiv \beta\mod b, \end{cases} \quad\text{which is }\qquad x\equiv \beta ua+\alpha vb\mod ab$$

Indeed we have $\;\beta ua+\alpha vb\equiv \alpha vb\equiv \alpha\mod a$ since $\;vb\equiv 1\mod a$. Similarly modulo $b$.

Now, as $v \equiv b^{-1}\bmod a\:$ and $\;u\equiv a^{-1}\bmod b$, this formula can be written as $$x\equiv \beta\, a (a^{-1}\bmod b)+\alpha\, b(b^{-1}\bmod a)\mod ab.$$

Some details with the example in the question:

In each term of $x$: $$ 2 \cdot (5 \cdot 7) \cdot 2 + 3 \cdot (3 \cdot 7) \cdot 1 + 2 \cdot (3 \cdot 5) \cdot 1 $$ the first factor is the r.h.s. of a congruence equation mod. $m_i$, the second (between parentheses) is the product of the other moduli and the last factor is the inverse of the former mod. $m_i$.

For instance, consider the first congruence: as $5\cdot 7\equiv 2\mod 3$, which is its own inverse, and $\equiv 0\mod 5,7$,we see that $$(5\cdot7)\cdot 2\begin{cases}\equiv 1\mod3,\\[1ex]\equiv 0 \mod 5,7 \end{cases}\quad\text{hence }\quad\alpha\cdot(5\cdot7)\cdot 2\begin{cases}\equiv \alpha\mod3\\[1ex]\equiv 0 \mod 5,7 \end{cases}$$ So we obtain a formula analog to Lagrange's interpolation formula: $$ \alpha \cdot (5 \cdot 7) \cdot 2 + \beta \cdot (3 \cdot 7) \cdot 1 + \gamma\cdot (3 \cdot 5) \cdot 1 \equiv\begin{cases}\alpha\mod 3, \\[1ex]\beta\mod 5,\\[1ex]\gamma\mod 7. \end{cases}$$

Answer 2

Existence of a solution $\,x\,$ of the congruence system becomes clearer if we highlight the innate linearity at the heart of the Chinese Remainder Theorem [CRT] formula, i.e.

$$\begin{eqnarray} x\, =\ &a&\!\color{#0a0}{\overbrace{(-5\cdot 7)}^{\large \equiv\, 1\ ({\rm mod}\ \color{#c00}3)}} \,+\, &b& \overbrace{(\color{#c00}3\cdot 7)}^{\large \equiv\, 1\ ({\rm mod}\ 5)}\, +\, &c&\overbrace{(\color{#c00}3\cdot 5)}^{\large \equiv\, 1\ ({\rm mod}\ 7)}\quad {\bf[CRT]}\\ \\ \Longrightarrow\ \ x\,\equiv\ &a&\ ({\rm mod}\ \color{#c00}3),\ \ x\equiv &b&\ ({\rm mod}\ 5),\ \ x\equiv &c&\ ({\rm mod}\ 7)\\ \end{eqnarray}$$

since, e.g. when reduced $\!\bmod \color{#c00}3,\,$ the 2nd and 3rd summands are $\equiv\color{#c00} 0,\,$ both having factors of $\,\color{#c00}3,\,$ so the formula reduces to $\, x\equiv a\color{#0a0}{(1)} \color{#c00}{+ 0 + 0}\equiv a,\,$ as sought. Similarly reducing the CRT formula $\!\bmod 5\,$ and $\!\bmod 7\,$ shows $\,x\equiv b\pmod{\!5}\,$ and $\,x\equiv c\pmod{\!7},\,$ resp. hence the CRT formula for $\,x\,$ does indeed yield a simultaneous solution of all $3$ congruences in our system, as sought.

Key Idea the overbraced terms are $\color{#0a0}{\equiv 1}\:\!$ mod one modulus, and $\color{#c00}{\equiv 0}\:\!$ mod all others. More clearly, if we write the system in vector form $\ x\equiv (a,b,c)\,$ mod $\,(3,5,7)\,$ then $\rm\,[CRT]$ becomes

$\qquad x\, :=\, a\,\color{#0a0}{(1,0,0)} + b\,(0,1,0) + c\,(0,0,1)\equiv (a.b,c)\ $ as desired. $\qquad [\bf Linearity]$

by the green term $\,\color{#0a0}{g \equiv 1}\ ({\rm mod}\ 3),\ \color{#0a0}{g\equiv 0}\ ({\rm mod}\ 5),\ \color{#0a0}{g\equiv 0}\ ({\rm mod}\ 7),\ $ i.e. $\ \color{#0a0}{g^{\phantom{|^|}}\!\!\!\equiv (1,0,0)}\ {\rm mod}\ (3,5,7),\, $ and similarly for $\,(0,1,0)\,$ and $\,(0,0,1).$

Thus once we compute the solutions for the "basis" vectors $(1,0,0),\ (0,1,0),\ (0,0,1)$ we can exploit [Linearity] to generate the general solution as a linear combination of these basic solutions.

Solving for the basis is easy: $\,{\color{#0a0}{5,7\mid g}\,\Rightarrow\, 35\mid g},\, $ so $\bmod 3\!:\ \color{#0a0}{1\equiv g} \equiv 35n\equiv -n\,\Rightarrow\, n\equiv -1,\,$ i.e. $\,n =\,$ inverse of the product $35 = 5\cdot 7$ of all other moduli. Hence the common CRT formula.

The innate algebraic structure will be clarified if you later study abstract algebra, where you will learn the ring theoretic view of CRT, and vector spaces and modules (elaborated briefly below).

---

Uniqueness $ $ The solutions of the system $\,x\equiv a_i\pmod{\!m_i},\, i = 1,\ldots, k\,$ are unique modulo the moduli product $M = m_1 m_2\cdots m_k,\,$ i.e if $\,x,\,x'\,$ are solutions then $\,x\equiv x'\pmod{\!M}.\,$ Indeed, being solutions $\Rightarrow x'\equiv a_i\equiv x\pmod{\!m_i}\,$ so $\,x'-x\,$ is divisible by all $\,m_i\,$ so it is divisible by their lcm, which is their product $M$, since the $\,m_i$ pairwise coprime (by hypothesis). Hence the least natural solution is $\,x\bmod M$. [This proof is a special case of the fact that general solution of a linear system of equations is given by adding any particular solution to the general solution of the associated homogeneous system, e.g. see here and its links. In our case the associated homogeneous system is $$\,x\equiv 0\!\!\pmod{m_i}\iff m_i \mid x\iff {\rm lcm}(m_i)\!=\!M\mid x\iff x = nM\qquad\quad$$ so the general solution is $\,x = x_0 + nM\,$ for any particular root $\,x_0,\,$ e.g. from CRT formula].

---

Product Ring View $ $ The arithmetical essence of the matter will be clarified structurally if you study abstract algebra, where CRT becomes a ring isomorphism $\,\Bbb Z/M\, \cong\, \Bbb Z/m_1 \times \cdots \Bbb Z/m_k.\,$ This means that an integer $\!\bmod M\,$ can be represented as vector $(k$-tuple) whose components are its values in each factor
$$n\bmod \overbrace{m_1\cdots m_k}^{M}\,\mapsto\, (n\bmod m_1, \ldots, n\bmod m_k)$$

CRT says this map is a bijection, and gives a formula showing how to recover the value of $\,n\bmod M\,$ from the values $\,n\bmod m_i\,$ in its vector rep. Further this vector representation is compatible with addition and multiplication by performing each operation componentwise, e.g. $$\begin{align} -5\cdot 7\ \ +\ \ 3\cdot 7\ \ +\ \ 3\cdot 5\ \ \ &\equiv\,\ 1\ \ \ \ \ \ \ \ \ \pmod{3\cdot 5\cdot 7}\\[.3em] \iff \ (1,0,0)\!+\!(0,1,0)\!+\!(0,0,1) &\equiv\, (1,1,1)\! \pmod{3,\,5,\,7}\end{align}\qquad$$

Hence these vectors with componentwise addition and multiplication yield essentially the same "number system" as the integers $\!\bmod M.\,$ This arithmetical similarity of number systems is made more precise in abstract algebra via the notion of isomorphic rings.

---

Lagrange Interpolation formula is a special case of above CRT formula, as explained here.

Answer 3

Taking Bill Dubuque's graphic answer and graphically expanding on it:

$x = 2 \cdot\overbrace{ (5 \cdot 7) \cdot 2}^{\equiv 1 \pmod 3\\ \equiv 0 \pmod 5\\ \equiv 0 \pmod 7} + 3 \cdot \overbrace{(3 \cdot 7) \cdot 1}^{\equiv 0 \pmod 3\\ \equiv 1 \pmod 5\\ \equiv 0 \pmod 7} + 2 \cdot \overbrace{(3 \cdot 5) \cdot 1}^{\equiv 0 \pmod 3\\ \equiv 0 \pmod 5\\ \equiv 1\pmod 7}\equiv\, \overbrace{2,\,3,\,2\pmod{3,5,7}}^{\equiv 2 + 0 +0\pmod 3\\ \equiv0+3+0 \pmod 5\\ \equiv 0+0+2\pmod 7}$

======

Think about what you, yourself just stated.

If take this sum $x = 2 \cdot (5 \cdot 7) \cdot 2 + 3 \cdot (3 \cdot 7) \cdot 1 + 2 \cdot (3 \cdot 5) \cdot 1$ and $\mod 3$ it, then $(5\cdot 7)$ and $2$ are inverses so $2\cdot[(5\cdot 7)\cdot 2]\pmod 3\equiv 2\cdot 1\pmod 3 \equiv 2 \pmod 3$. ANd the other terms are multiples of $3$ so they are $\equiv 0 \pmod 3$. So $x\equiv 2 \pmod 3$.

If you take that term $x = 2 \cdot (5 \cdot 7) \cdot 2 + 3 \cdot (3 \cdot 7) \cdot 1 + 2 \cdot (3 \cdot 5) \cdot 1$ and $\mod 5$ it, then $3\cdot 7$ and $1$ are inverses so $3\cdot[(3\cdot 7) \cdot 1] \equiv 3 \cdot 1 \equiv 3 \pmod 5$. ANd the other terms are multiples of $5$. So the sum $x \equiv 3 \pmod 5$.

And so on.

....

If you want to solve

$x \equiv a \pmod m$

$x \equiv b \pmod n$

$x \equiv c \pmod v$ then

And assuming you were able find $(nv)^{-1}\mod m; (mv)^{-1}\mod n; $and $(nm)^{-1}\mod v$

Then Let $K = a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)$

Note: $K \pmod m \equiv$

$a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)\pmod m\equiv$

$a*1 + [b(mv)^{-1}v]m + [c(nm)^{-1}n]m \pmod m\equiv$

$a*1 + 0 + 0 \equiv a\pmod m$.

And likewise:

$K \pmod n \equiv$

$a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)\pmod n\equiv$

$[a(nv)^{-1}v]n + b*1 + [c(nm)^{-1}m]n \pmod n\equiv$

$0 + b*1 + 0 \equiv b\pmod n$.

And

$a(nv)^{-1}(nv) + b (mv)^{-1}(mv) + c(nm)^{-1}(nm)\pmod v\equiv$

$[a(nv)^-1n]v + [b(mv)^{-1}m]v + c*1 \pmod v\equiv$

$0 + 0 + c \equiv c\pmod m$.

So $K$ is A solution.

If $m,n,v$ are pairwise relative prime then $K$ is a unique solution upto $\mod nmv$.