# 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

## 3 Answers

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