I'm currently going through Harvard's Abstract Algebra lectures. I was doing one of the homework's and wanted to make sure that my thinking was correct. The problem states

Using the Lemma that $m\mathbb{Z} + n\mathbb{Z} = gcd(m,n)\mathbb{Z}$, prove the Chinese Remainder Theorem which states given integers $m, n, a, b$ where $gcd(m,n) = 1$, there exists an integer $x$ such that $x \equiv{a} \pmod{m}$ and $x \equiv{b} \pmod{n}$

I think my general outline for the proof is okay, but I'm getting a little stuck in formalizing what it is I wish to say.

If $gcd(m, n) = 1$ then $m\mathbb{Z} + n\mathbb{Z} = \mathbb{Z}$

So, given that x is an integer, $x \in \mathbb{Z}$.

So, $(x - a), (x - b) \in \mathbb{Z}$.

So, $(x - a), (x - b) \in m\mathbb{Z} + n\mathbb{Z}$.

Take $a \in m\mathbb{Z}$ and $b \in n\mathbb{Z}$. Then, $(x - a) \in m\mathbb{Z}$ and $(x - b) \in n\mathbb{Z}$. This completes the proof.

So, I feel like the general outline is there, but I don't know if every step can be properly justified.

Any and all help would be greatly appreciated.


Hint $\,\ \Bbb Z = m\Bbb Z+n\Bbb Z \,\Rightarrow\, a-b = mj+nk\,\Rightarrow\!\!\!\! \underbrace{a-mj}_{\large \equiv\ a\pmod{\!\! m}}\!\!\!\!\! =\!\!\!\!\! \overbrace{b+nk}^{\large \equiv\ b\pmod{\!\! n}}$

  • $\begingroup$ Ah...of course...Thanks. $\endgroup$ Jan 31 '17 at 17:02
  • $\begingroup$ See here for more on CRT via Bezout rearrangement. $\endgroup$ Mar 6 '20 at 18:33

Just follow the enouncement of the theorem. Given $n,m,a,b\in\mathbb{Z}$, s.t. $gcd(m,n)=1$, we want to find $x$. So as Bill says, we use the Lemma to say that it exists $j,k$ s.t. $a+mj=b+nk$, so just define $x:=a+mj$. You can generalize this result using that (*)$\exists k_i,s.t.gcd(\lbrace n_i\rbrace)=\sum k_in_i$ to finite i's. The extension gives a solution to the system $x=a_i(mod n_i)$ and the prove is as follows. First, for each i we'll solve system $x_i=1(modn_i),x_i=0(modn_j),j\neq i$. Using the (*), we have that, as $n_j$ relative primes, exists $k_j$ s.t., $$1-k_in_i=\sum_{j\neq i}k_in_i$$ and the term of right satisfices what we want. Then, taking $x=\sum a_ix_i$ we've prove the theorem.


HINT : There is an easy way to prove the CRT by considering the map $\Bbb Z \rightarrow \Bbb Z_m \oplus \Bbb Z_n: x\mapsto (x \mod(m),x \mod(n)) $, and proving it is a surjection. Make use of the facts that this map is a ring homomorphism and that $\Bbb Z_{mn} \cong \Bbb Z_m \oplus \Bbb Z_n$ (under the assumption that $(m,n) = 1$).


We can make a proof of this theorem by "Analysis-Synthesis" :

Analysis : We want to build $x \pmod{mn}$ :

Suppose that such a $x$ checks $x\equiv a \pmod m$ and $x\equiv b\pmod n$. That means that there exist $k,l \in \mathbb{Z}$ such that : $x=mk+a$ and $x=nl+b$.

Moreover we have $\gcd(m,n)=1$ so by Bachet-Bézout theorem there exits $u,v \in \mathbb{Z}$ such that : $um+vn=1$.

Now we multiply this relation by $x$ it gives : $umx+vnx=x$.

This is equivalent to : $umx+vnx\equiv x\pmod{mn}$.

This is equivalent to : $um(nl+b)+vn(mk+a)\equiv x\pmod{mn} \Leftrightarrow umb+vna \equiv x \pmod{mn}$.

Synthesis : We want that the $x$ built checks the properties :

So we respectively have : $x\equiv umb \pmod n$ and $x\equiv vna \pmod m$.

Then as $\gcd(m,n)=1$ we can notice that $m$ and $n$ are invertible respectively in $Z/nZ$ and $Z/mZ$. Their inverse elements are respectively $u=m^{-1}$ and $v=n^{-1}$ otherwise we will obtain the wrong congruences.

We have proof the existence of $x$. In general with this method in most case there is automatically uniqueness.

Howewer we can check that if there exist two different solutions $x$ and $y$ which satisfy all the properties then they are the same.


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.