# Deriving Chinese Remainder Theorem from gcd Bezout identity

First off, assume we have the function $\text{egcd}(a, b)$ which returns the variables $g, u, v$ such that $au + bv = g = \gcd(a, b)$.

Now we want to find the solution $x$ in the congruence system

$x \equiv r_1 \bmod m_1$

$x \equiv r_2 \bmod m_2$

where $\gcd(m_1, m_2) = 1$

These can be rewritten as

$x = r_1 + m_1j$

$x = r_2 - m_2k$

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 integer $h$ make $h \gcd(m_1, m_2) = r_2 - r_1$.

Then

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

becomes $hm_1u + hm_2v = m_1j + m_2k$

At this point I am lost because I don't think we can just assume that $hm_1u = m_1j$ and extact $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

Your argument reverses: if $$\,j,k\,$$ are integers such that $$\ j\, m_1+ k\, m_2 =\, r_2 - r_1\,$$ then $$\ x\ :=\ \color{#c00}{r_1} +\, j\ \color{#c00}{m_1}\ =\,\ \color{#0a0}{r_2}\, -\ k\ \color{#0a0}{m_2}\$$ is a solution of the given system of congruences because $$\,x\equiv \color{#c00}{r_1}\!\!\pmod{\!\color{#c00}{m_1}},$$ $$x\equiv \color{#0a0}{r_2}\!\pmod{\!\color{#0a0}{m_2}}.\,$$ Since you have already found one such solution for $$j,k,\,$$ viz. $$\,j=hu,\,k = hv\,$$ (as below), you need only substitute it above to obtain a CRT solution $$\,x.$$

$$\overbrace{(hu)}^{\Large j}\,m_1+\, \overbrace{(hv)}^{\Large k}\,m_2\,=\,r_2-r_1$$

Remark $$\$$ Combining your $$(\Rightarrow)$$ and the above $$(\Leftarrow)$$ inferences yields

\exists\, x\in\Bbb Z\!:\ \begin{align}x\equiv r_1\!\!\!\pmod{\!m_1}\\ x\equiv r_2\!\!\!\pmod{\!m_2}\end{align}\iff \exists\, j,k\in\Bbb Z\!:\ j\,m_1 + k\, m_2 =\, r_2-r_1

Clearly $$\,d := \gcd(m_1,m_2)\mid r_1-r_2 \,$$ is a necessary condition for the latter to be solvable, and it is also sufficient by Bezout (or, constructively, by the extended Euclidean algorithm), i.e. scale the Bezout equation $$\, a m_1\! + b m_2 = d\,$$ by $$\, c = \large \frac{r_2\,-\,r_1}{d}$$ to get $$\,ca\,m_1\!+cb\,m_2 = r_1-r_2 \,$$ so, as above, $$\,x := r_1 - ca\,m_1 = r_2 + cb\,m_2\,$$ is a solution.

So the congruence system is solvable $$\iff d=\gcd(m_1,m_2)\mid r_2-r_1.\,$$ When so 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$$.

See hee for a worked example from this viewpoint.

• 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