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

  • 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
  • 1
    $\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

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.

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