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.
Best Answer
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}}$