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.


  • 1
    $\begingroup$ 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. $\endgroup$ – 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

| 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.

| 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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