Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.


share|cite|improve this question
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 3

up vote 4 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer
This doesn't make sense to me. Could you explain further? – robjohn Apr 10 '13 at 17:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.