# Prove the _Chinese Remainder Theorem_

This is a question from the free Harvard online abstract algebra lectures. I'm posting my solutions here to get some feedback on them. For a fuller explanation, see this post.

This problem is from assignment 6. The notes from this lecture can be found here.

Use Proposition (2.6) to prove the Chinese Remainder Theorem: Let $$m,n,a,b$$ be integers, and assume that the greatest common Divisor of $$m$$ and $$n$$ is 1. Then there is an integer $$x$$ such that $$x\equiv a \:(\mathrm{modulo}\:m)$$ and $$x\equiv b \:(\mathrm{modulo}\:n)$$.

Proposition (2.6): Let $$a,b$$ be integers, not both zero, and let $$d$$ be the positive integer which generates the subgroup $$a\mathbb{Z}+b\mathbb{Z}$$. Then
a) $$d$$ can be written in the form $$d=ar+bs$$ for some integers $$r$$ and $$s$$.
b) $$d$$ divides $$a$$ and $$b$$.
c) If an integer $$e$$ divides $$a$$ and $$b$$, it also divides $$d$$.

Since $$x\equiv a \:(\mathrm{modulo}\:m)$$ and $$x\equiv b \:(\mathrm{modulo}\:n)$$, $$x=a+km$$ and $$x=b+jn$$, for some $$k,j\in\mathbb{Z}$$. So if $$x$$ exists $$a+km=b+jn$$ and $$km-jn=b-a$$. Since gcd$$(m,n)=1$$, 1 generates the subgroup $$m\mathbb{Z}+n\mathbb{Z}$$. By Proposition (2.6), there are integers $$r$$ and $$s$$ such that $$rm+sn=1$$. Multiplying by $$b-a$$ we get $$r(b-a)m+s(b-a)n=b-a.$$ Then $$k=r(b-a)$$ and $$j=-s(b-a)$$. Therefore, $$x=a+r(b-a)m$$ is a solution to both congruences.

Again, I welcome any critique of my reasoning and/or my style as well as alternative solutions to the problem.

Thanks.

• You start by assuming the result. Later, from $r(b-a)m+s(b-a)n=b-a$, the fact that $k=r(b-a)$ is inferred. There is no justification for that, and there cannot be, linear Diophantine equations have many solutions. – André Nicolas Jan 17 '12 at 23:26

HINT $\$ By Prop. 2.6 we infer $\rm\ gcd(m,n) = 1\ \Rightarrow\ m^{-1}\$ exists $\rm\ (mod\ n)\:.\$ Therefore

THEOREM $\:$ (Easy CRT) $\rm\ \$ If $\rm\ m,\:n\:$ are coprime integers then

$\rm\displaystyle\quad\quad\quad\quad\quad \begin{eqnarray}\rm x&\equiv&\rm\ a\ (mod\ m) \\ \rm x&\equiv&\rm\ b\ (mod\ n)\end{eqnarray} \ \iff\ \ x\ \equiv\ a + m\ \bigg[\frac{b-a}{m}\ mod\ n\:\bigg]\ \ (mod\ m\:n)$

Proof $\rm\ (\Leftarrow)\ \ \ mod\ m:\ x\ \equiv\ a + m\ [\:\cdots\:]\ \equiv\ a\:,\$ and $\rm\ mod\ n\!\!:\ x\ \equiv\ a + (b-a)\ m/m\ \equiv\ b\:.$

$\rm (\Rightarrow)\ \$ The solution is unique $\rm\ (mod\ m\:n)\$ since if $\rm\ x',\:x\$ are solutions then $\rm\ x'\equiv x\$ mod $\rm\:m,n\:$ therefore $\rm\ m,\:n\ |\ x'-x\ \Rightarrow\ m\:n\ |\ x'-x\ \$ since $\rm\ \:m,\:n\:$ coprime $\rm\:\Rightarrow\ lcm(m,n) = m\:n\:.\quad$ QED

You come dangerously close to the fallacy of assuming the conclusion when you start a sentence with "if $x$ exists..." You don't really use, or need, the first couple of sentences of your write-up. Once you've got $r$ and $s$, you can just check directly that $a+(b-a)rm$ gives a solution.

note: $|m - n| \ge j \in \mathbb{Z}$ at any one time solution per states of congruents for any integer $x$.

• This doesn't make sense to me. Could you explain further? – robjohn Apr 10 '13 at 17:22