# Deriving Chinese Remainder Theorem from gcd Bezout identity

We want to find the solution $$x$$ to the congruence system

\begin{align} x &\equiv r_1 \!\!\!\pmod{\!m_1}\\ x &\equiv r_2 \!\!\!\pmod{\!m_2}\end{align},\ \ {\rm where}\ \ \gcd(m_1, m_2) = 1

These can be rewritten as

\begin{align} x &= r_1 + m_1 j\\ x &= r_2 - m_2k\end{align}

for unknown integers $$j, k$$. So we set those two equations as equal and rearrange them to

$$m_1j + m_2k = r_2 - r_1$$

Now assume we perform $$\text{egcd}(m_1, m_2)$$, which gives us the solution to

$$m_1u + m_2v = \gcd(m_1, m_2)$$

Let the integer $$\,h\,$$ make $$\,h \gcd(m_1, m_2) = r_2 - r_1$$.

Then $$\qquad hm_1u + hm_2v = h\gcd(m_1, m_2) = r_2 - r_1 = m_1j + m_2k$$

At this point I am lost because I don't think we can just assume $$hm_1u = m_1j$$ and extract $$j = hu$$.

How do I get the values of $$j$$ or $$k$$ so I can get the value of $$x$$?

• Why on earth did someone downvote this? I showed my work and had a clear question here. – user399664 Dec 16 '16 at 2:02
• I just upvoted to compensate. save yourself the emotional and intellectual energy of trying to understand the illogic of voting here. You could give your post a better title, though. "Can the Chinese Remainder Theorem be proved this way?" or "How to proceed in this proof of the Chinese Remainder Theorem, if possible?" – symplectomorphic Dec 16 '16 at 2:06

Correct, if $$x$$ is a root of the congruences then $$\, x= j\,m_1 + r_1 = -k\, m_2 + r_2\,$$ has roots $$\,j,k\in\Bbb Z$$.

This argument reverses: if $$\,j,k\,$$ are integers with $$\ j\, \color{#c00}{m_1}+ k\, \color{#0a0}{m_2} =\, \color{#0a0}{r_2} - \color{#c00}{r_1}\,$$ then by $$\rm\color{#c00}{re}\color{#0a0}{arranging}$$ $$\ x :=\ \color{#c00}{r_1} +\, j\ \color{#c00}{m_1}^{\phantom{|}}\ =\,\ \ \color{#0a0}{r_2}\: -\,\ k\ \color{#0a0}{m_2}\$$ is one solution of the given system of congruences because $$\,x\equiv \color{#c00}{r_1}\!\!\pmod{\!\!\color{#c00}{m_1}}^{\phantom{|^|}}\!\!\!,$$ $$x\equiv \color{#0a0}{r_2}\!\pmod{\!\!\color{#0a0}{m_2}}.\,$$ Since you've already discovered one such solution for $$\,j,k,\,$$ viz. $$\,j=hu,\,k^{\phantom{|^|}}\!\! = hv,\,$$ you need only substitute into the above rearranged CRT solution for $$\,x.$$

Remark  Combining both directions above and adding a final gcd equivalence yields the following

Theorem \ \ \left.\exists\, x\in\Bbb Z\!: \begin{align}x\equiv r_1\!\!\!\pmod{\!m_1}\\ x\equiv r_2\!\!\!\pmod{\!m_2}\end{align}\right\} \begin{array}{l}\!\iff \exists\,j,k\in\Bbb Z\!:\ j\,m_1\! + k\, m_2 =\, r_2\!-r_1 \\ \!\iff\, \gcd(m_1,\,m_2)\mid r_2 -r_1\end{array}

Proof  Clearly $$\,d := \gcd(m_1,m_2)\mid r_2-r_1 \,$$ is a necessary condition for the equation to have roots $$\,j,k\in \Bbb Z,\,$$ by $$\,d\mid m_1,m_2\Rightarrow\, d^{\phantom{|}}_{\phantom{i}}\!\mid j m_1\! + km_2 = r_2 - r_1.\,$$ Further this condition is also sufficient by Bezout (or, constructively, by the extended Euclidean algorithm), i.e. we can scale the Bezout equation $$\, a m_1\! + b m_2 = d\,$$ by $$\, c = \large \frac{r_2\,-\,r_1^{\phantom{.}}}{d}\,$$ to get $$\,ca\,m_1\!+cb\,m_2 = r_2-r_1 \,$$ so, as above, rearranging this yields a congruence system solution: $$\ x\, :=\, r_1 + ca\,m_1 = r_2 - cb\,m_2$$.

Thus the congruence system is solvable $$\iff d=\gcd(m_1,m_2)\mid r_2-r_1, \,$$ i.e. iff the pair of congruences is consistent mod their moduli gcd, and when true we can constructively read off a solution from the Bezout equation for the moduli by translating it into the equivalent system language as above, i.e. scale the Bezout equation to obtain the residue difference $$\,r_1-r_2\,$$ then rearrange it as above to obtain $$\,x.\,$$ Here is a worked example from this viewpoint. Thus we've the following simple Bezout-based CRT method for solving congruence systems

$$\! \small \textbf{ scale the Bezout equation for the moduli gcd}\!$$ $$\small \textbf{ to get the residue difference, then }\rm\color{#c00}{re}\color{#0a0}{arrange}$$

If you are familiar with ideals and cosets then the above can be expressed more succinctly as

$$\bbox[9px,border:1px solid #c00]{r_1\! +\! m_1\Bbb Z\,\cap\, r_2\! +\! m_2\Bbb Z \neq \phi \iff r_1-r_2 \in m_1\Bbb Z+m_2\Bbb Z}\qquad\qquad$$

Generally a congruence system is solvable $$\iff$$ each pair of congruences is solvable as above, and we can solve the system by successively replacing a pair of congruences by the single congruence obtained from solving the pair of congruences. By induction we eventually obtain a single congruence, which is the solution of the entire congruence system.

• I am saying I can't say that $j = hu$ and $k = hv$ – user399664 Dec 16 '16 at 2:41
• @user399664 But they are valid solutions, so what do you mean by you "can't say that"? – Bill Dubuque Dec 16 '16 at 2:43
• As in all I can really say is $hm_1u + hm_2v = m_1j + m_2k$ – user399664 Dec 16 '16 at 2:44
• @user399664 What we can say is that the values $\,j =hu\,$ and $\,k=hv\,$ are solutions of $\ jm_1+km_2 = r_2 - r_1\$ (see the overbraced equation above).. That is all that we need. – Bill Dubuque Dec 16 '16 at 2:46
• So it is correct to say that $x = r_1 + m_1hu$ and $x = r_2 - m_2hv$? Both of these $x$'s will always be the same? – user399664 Dec 16 '16 at 2:48