1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It's not clear which part proves troublesome. Often it is the linearity that I describe in my answer. If it is something else then please elaborate and I can add further details. $\endgroup$ – Bill Dubuque Jan 31 at 18:19
0
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ The brave anonymous downvoter struck again! $\endgroup$ – Bernard Feb 1 at 20:47
2
$\begingroup$

It helps to highlught linearity at the heart of the Chinese Remainder Theorem [CRT] formula.

$$\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]}\\ \\ \Rightarrow\ \ x\,\equiv\, &a&\ ({\rm mod}\ \color{#c00}3),\ \ x\equiv &b&\ ({\rm mod}\ 4),\ \ x\equiv &c&\ ({\rm mod}\ 5)\\ \end{eqnarray}$$

since, e.g. reduced $ $ mod $\ \color{#c00}3,\,$ the 2nd and 3rd summands are $\equiv 0,\,$ both having factors of $\,\color{#c00}3.\,$

The key idea is that the braced terms are $\equiv 1$ mod one modulus, and $\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\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 the basic cases 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\,$ is the inverse of the product $36= 5\cdot 7$ of all the other moduli. Thus 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.

Edit $ $ To answer a question in a comment: above explains why the standard CRT formula is a solution of the congruence system, i.e. it yields the sought values for each modulus $\,x\equiv a_i\pmod{\!m_i}.\,$ That this solution is unique modulo the moduli product $M = m_1 m_2\cdots m_k$ follows from the proof of CRT. Let's recall this direction of the CRT proof. If $\,x,\,x'$ are two solutions then $\!\bmod m_i\!:\ x'\equiv a_i\equiv x.\,$ Thus $\,x'-x\,$ is divisible by all moduli $\,m_i\,$ so it is divisible by their lcm, which is their product $M$, since they are all pairwise coprime. Therefore $\,x'\equiv x\pmod{\!M},\,$ i.e. solutions are unique modulo the product of the moduli.

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 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 doing each operation componentwise in the vectors, e.g. above $$\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.

$\endgroup$
  • $\begingroup$ what is the reason why x lies in mod m at the last? $\endgroup$ – mathmaniage May 2 at 11:48
  • $\begingroup$ @mathmaniage It is not clear what you are asking. Please elaborate. $\endgroup$ – Bill Dubuque May 2 at 14:30
  • 1
    $\begingroup$ @mathmaniage The OP's question asked only about the existence half of CRT, i.e. why the CRT solution formula is correct. Your question is about the uniqueness half of CRT, i.,e, why it is the only solution modulo the product of the moduli. I edited the answer to explain this too. $\endgroup$ – Bill Dubuque May 2 at 15:38
  • 1
    $\begingroup$ @mathmaniage CRT tells us how to construct a particular solutions $x_0$ of the system of congruences. Further it implies that an integer $x$ is a solution $\iff x\equiv x_0 \pmod{\!M},\,$ so solutions are unique $\bmod M.\,$ This completely characterizes the integer solutions of the congruence system. Are you asking why lcm = product for pairwise coprime integers? $\endgroup$ – Bill Dubuque May 2 at 17:04
  • 1
    $\begingroup$ @mathmaniage Great! $\endgroup$ – Bill Dubuque May 3 at 3:58
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ @fleabood, but that misses the point that K obtained in step 1 , K obtained in step 2 and in step 3 the sum of which is the solution upto modnmv $\endgroup$ – mathmaniage May 1 at 8:40

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.