Proof of Chinese Remainder Theorem
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.
$\endgroup$4 Answers
$\begingroup$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}}$
$\endgroup$ 2 $\begingroup$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.
$\endgroup$ $\begingroup$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$).
$\endgroup$ $\begingroup$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.
$\endgroup$
