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


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

  • 1
    $\begingroup$ Why on earth did someone downvote this? I showed my work and had a clear question here. $\endgroup$ – user399664 Dec 16 '16 at 2:02
  • $\begingroup$ 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?" $\endgroup$ – 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.

  • $\begingroup$ I am saying I can't say that $j = hu$ and $k = hv$ $\endgroup$ – user399664 Dec 16 '16 at 2:41
  • $\begingroup$ @user399664 But they are valid solutions, so what do you mean by you "can't say that"? $\endgroup$ – Bill Dubuque Dec 16 '16 at 2:43
  • $\begingroup$ As in all I can really say is $hm_1u + hm_2v = m_1j + m_2k$ $\endgroup$ – user399664 Dec 16 '16 at 2:44
  • $\begingroup$ @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. $\endgroup$ – Bill Dubuque Dec 16 '16 at 2:46
  • $\begingroup$ 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? $\endgroup$ – user399664 Dec 16 '16 at 2:48

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.