Take the 2-minute tour ×
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.

Thanks.

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

4 Answers 4

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|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|improve this answer

I would offer the tip of proving the 'generalized' CRT for commutative rings with identity.

It is a simple generalizations of what you are trying to show, I will post the solution up after you attempt it if you wish.

share|improve this answer
    
... though you need to know the first isomorphism theorem; I do remember seeing the 15 minutes of maybe his third lecture and I am confidentish he introduces these stuff - correct me if I mistaken. –  Adam Jan 18 '12 at 0:12

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

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

Your Answer

 
discard

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.