1. Proving CRT

Hi can anyone say how do I prove CRT by the following isomorphism:

If n= (m1)(m2)...(mk) where each m is relatively prime in pairs, then there is an isomorphism from Zn to ( Zm1 + Zm2 + ... + Zmk). Zn is the integers modulo n.

all I can say is that since Mi's are relatively prime then gcd of each pair will be=1. that is we can write each pair as linear combination of k*Mi+t*Mj=1. but I dont know how to take this fact to prove this isomorphism relationship and furthermore how this isomorphism will prove Chinese remainder theorem.

2. Originally Posted by hamidr
Hi can anyone say how do I prove CRT by the following isomorphism:

If n= (m1)(m2)...(mk) where each m is relatively prime in pairs, then there is an isomorphism from Zn to ( Zm1 + Zm2 + ... + Zmk). Zn is the integers modulo n.

all I can say is that since Mi's are relatively prime then gcd of each pair will be=1. that is we can write each pair as linear combination of k*Mi+t*Mj=1. but I dont know how to take this fact to prove this isomorphism relationship and furthermore how this isomorphism will prove Chinese remainder theorem.
Hint: Prove that $\displaystyle \bigoplus_{j=1}^{k}\mathbb{Z}_{m_j}$ is cyclic. Then, since $\displaystyle \left|\bigoplus_{j=1}^{k}\mathbb{Z}_{m_j}\right|=\ prod_{j=1}^{k}m_j=n$ it is trivial that it is isomorphic to $\displaystyle \mathbb{Z}_n$. What's the easiest way to show that something is cyclic? Find an element in it whose order is that of the group.

Try finishing that up and then we'll discuss the Chinese remainder theorem.

3. Originally Posted by Drexel28
Hint: Prove that $\displaystyle \bigoplus_{j=1}^{k}\mathbb{Z}_{m_j}$ is cyclic. Then, since $\displaystyle \left|\bigoplus_{j=1}^{k}\mathbb{Z}_{m_j}\right|=\ prod_{j=1}^{k}m_j=n$ it is trivial that it is isomorphic to $\displaystyle \mathbb{Z}_n$. What's the easiest way to show that something is cyclic? Find an element in it whose order is that of the group.

Try finishing that up and then we'll discuss the Chinese remainder theorem.
pardon me but I never saw such notations before, so I really didn't understand that. however showing something is cyclic is to show every element can be generated by an element that is the generator, but still I don't understand how that will help me in proving the isomorphism relationship

4. Originally Posted by hamidr
pardon me but I never saw such notations before, so I really didn't understand that. however showing something is cyclic is to show every element can be generated by an element that is the generator, but still I don't understand how that will help me in proving the isomorphism relationship
The notation is just notation. If you like better $\displaystyle \mathbb{Z}_{m_1}\times\cdots\times\mathbb{Z}_{m_k}$ or $\displaystyle \mathbb{Z}_{m_1}\oplus\cdots\oplus\mathbb{Z}_{m_k}$ in lieu of $\displaystyle \bigoplus_{j=1}^{k}\mathbb{Z}_{m_j}$. They all mean the same thing except that $\displaystyle \oplus$ is reserved for when the groups are abelian (btw $\displaystyle \bigoplus$ is an analogous index operator for $\displaystyle \oplus$ as that of $\displaystyle \sum$ for $\displaystyle +$).

Ok, so for the idea. You need a quick little lemma.

Lemma: Let $\displaystyle C_n$ denote a cyclic (this lemma will show the cyclic) group of order $\displaystyle n$. Then, $\displaystyle \mathbb{Z}_n\cong C_n$

Proof: Let $\displaystyle C_n$ be generated by $\displaystyle c$ and define $\displaystyle \theta:\mathbb{Z}_n\to C_n$ by $\displaystyle k\overset{\theta}{\longmapsto}c^k$.

Clearly $\displaystyle \theta$ is injective since $\displaystyle \theta(k)=\theta(m)\implies c^k=c^m$ now we may assume WLOG that $\displaystyle 0\leqslant m\leqslant k\leqslant n$ and so the above implies that $\displaystyle c^{k-m}=e$. But! $\displaystyle |c|=n\geqslant k-m$ and so $\displaystyle k-m$ can't be strictly positive and since it's non-negative it follows that $\displaystyle k-m=0\implies k=m$

Surjectivity is clear since $\displaystyle g\in C_n\implies g=c^k$ for some $\displaystyle 0\leqslant k\leqslant n$ and so $\displaystyle k\in\mathbb{Z}_n$ and $\displaystyle \theta(k)=c^k=g$

The homomorphism property follows since $\displaystyle \theta(m+k)=c^{m+k}=c^mc^k=\theta(m)\theta(k)$.

The conclusion follows. $\displaystyle \blacksquare$

Thus, we must only prove that $\displaystyle \bigoplus_{j=1}^{k}\mathbb{Z}_{m_j}$ is cyclic and it will follow from the lemma that it is equal to $\displaystyle \mathbb{Z}_{m_1\cdots m_k}$

To see this we will prove that $\displaystyle (\underbrace{1,\cdots,1}_{k\text{ times}})$ generates $\displaystyle \bigoplus_{j=1}^{k}\mathbb{Z}_{m_k}$. To do this note that $\displaystyle |(1,\cdots,1)|$ is the least positive number such that $\displaystyle (1,\cdots,1)^d=(d,\cdots,d)=(0,\cdots,0)\quad{\col or{red}(1)}$. But, notice that the first coordinate's order is $\displaystyle m_1$ and so it will only be $\displaystyle e$ when $\displaystyle d=a_1m_1$ where $\displaystyle a_1\in\mathbb{N}$ and $\displaystyle d$ is as in $\displaystyle \color{red}(1)$. Similarly, the second slot will only be $\displaystyle e$ when $\displaystyle d=a_2m_2$ and so on and so forth. Thus, $\displaystyle |(1,\cdots,1)|$ is the first occurrence of the multiples of $\displaystyle m_1,\cdots,m_k$ matching up. In other words $\displaystyle |(1,\cdots,1)|=\text{lcm}(m_1,\cdots,m_k)$. But, since $\displaystyle \text{gcd}(m_1,\cdots,m_k)=1$ and $\displaystyle \text{lcm}(m_1,\cdots,m_k)=\frac{m_1\cdots m_k}{\text{gcd}(m_1,\cdots,m_k)}$ it follows that $\displaystyle |(1,\cdots,1)|=\text{lcm}(m_1,\cdots,m_k)=m_1\cdot s m_k$. And since $\displaystyle \left|\bigoplus_{j=1}^{k}\mathbb{Z}_{m_k}\right|=m _1\cdots m_k$ it follows that $\displaystyle (1,\cdots,1)$ generates it. Thus, $\displaystyle \bigoplus_{j=1}^{k}\mathbb{Z}_{m_k}$ is a cyclic group of order $\displaystyle r=m_1\cdots m_k$ and thus $\displaystyle \bigoplus_{j=1}^{k}\mathbb{Z}_{m_j}\cong \mathbb{Z}_r$ by our lemma.

5. Originally Posted by Drexel28
The notation is just notation. If you like better $\displaystyle \mathbb{Z}_{m_1}\times\cdots\times\mathbb{Z}_{m_k}$ or $\displaystyle \mathbb{Z}_{m_1}\oplus\cdots\oplus\mathbb{Z}_{m_k}$ in lieu of $\displaystyle \bigoplus_{j=1}^{k}\mathbb{Z}_{m_j}$. They all mean the same thing except that $\displaystyle \oplus$ is reserved for when the groups are abelian (btw $\displaystyle \bigoplus$ is an analogous index operator for $\displaystyle \oplus$ as that of $\displaystyle \sum$ for $\displaystyle +$).

Ok, so for the idea. You need a quick little lemma.

Lemma: Let $\displaystyle C_n$ denote a cyclic (this lemma will show the cyclic) group of order $\displaystyle n$. Then, $\displaystyle \mathbb{Z}_n\cong C_n$

Proof: Let $\displaystyle C_n$ be generated by $\displaystyle c$ and define $\displaystyle \theta:\mathbb{Z}_n\to C_n$ by $\displaystyle k\overset{\theta}{\longmapsto}c^k$.

Clearly $\displaystyle \theta$ is injective since $\displaystyle \theta(k)=\theta(m)\implies c^k=c^m$ now we may assume WLOG that $\displaystyle 0\leqslant m\leqslant k\leqslant n$ and so the above implies that $\displaystyle c^{k-m}=e$. But! $\displaystyle |c|=n\geqslant k-m$ and so $\displaystyle k-m$ can't be strictly positive and since it's non-negative it follows that $\displaystyle k-m=0\implies k=m$

Surjectivity is clear since $\displaystyle g\in C_n\implies g=c^k$ for some $\displaystyle 0\leqslant k\leqslant n$ and so $\displaystyle k\in\mathbb{Z}_n$ and $\displaystyle \theta(k)=c^k=g$

The homomorphism property follows since $\displaystyle \theta(m+k)=c^{m+k}=c^mc^k=\theta(m)\theta(k)$.

The conclusion follows. $\displaystyle \blacksquare$

Thus, we must only prove that $\displaystyle \bigoplus_{j=1}^{k}\mathbb{Z}_{m_j}$ is cyclic and it will follow from the lemma that it is equal to $\displaystyle \mathbb{Z}_{m_1\cdots m_k}$

To see this we will prove that $\displaystyle (\underbrace{1,\cdots,1}_{k\text{ times}})$ generates $\displaystyle \bigoplus_{j=1}^{k}\mathbb{Z}_{m_k}$. To do this note that $\displaystyle |(1,\cdots,1)|$ is the least positive number such that $\displaystyle (1,\cdots,1)^d=(d,\cdots,d)=(0,\cdots,0)\quad{\col or{red}(1)}$. But, notice that the first coordinate's order is $\displaystyle m_1$ and so it will only be $\displaystyle e$ when $\displaystyle d=a_1m_1$ where $\displaystyle a_1\in\mathbb{N}$ and $\displaystyle d$ is as in $\displaystyle \color{red}(1)$. Similarly, the second slot will only be $\displaystyle e$ when $\displaystyle d=a_2m_2$ and so on and so forth. Thus, $\displaystyle |(1,\cdots,1)|$ is the first occurrence of the multiples of $\displaystyle m_1,\cdots,m_k$ matching up. In other words $\displaystyle |(1,\cdots,1)|=\text{lcm}(m_1,\cdots,m_k)$. But, since $\displaystyle \text{gcd}(m_1,\cdots,m_k)=1$ and $\displaystyle \text{lcm}(m_1,\cdots,m_k)=\frac{m_1\cdots m_k}{\text{gcd}(m_1,\cdots,m_k)}$ it follows that $\displaystyle |(1,\cdots,1)|=\text{lcm}(m_1,\cdots,m_k)=m_1\cdot s m_k$. And since $\displaystyle \left|\bigoplus_{j=1}^{k}\mathbb{Z}_{m_k}\right|=m _1\cdots m_k$ it follows that $\displaystyle (1,\cdots,1)$ generates it. Thus, $\displaystyle \bigoplus_{j=1}^{k}\mathbb{Z}_{m_k}$ is a cyclic group of order $\displaystyle r=m_1\cdots m_k$ and thus $\displaystyle \bigoplus_{j=1}^{k}\mathbb{Z}_{m_j}\cong \mathbb{Z}_r$ by our lemma.

In the beginning of the your proof of the Lemma, why is it “0 ≤ m ≤ k ≤ n” instead of “0 ≤ m ≤ k ≤ n - 1”?

Never mind. I just figured it out.

6. Originally Posted by Drexel28
The notation is just notation. If you like better $\displaystyle \mathbb{Z}_{m_1}\times\cdots\times\mathbb{Z}_{m_k}$ or $\displaystyle \mathbb{Z}_{m_1}\oplus\cdots\oplus\mathbb{Z}_{m_k}$ in lieu of $\displaystyle \bigoplus_{j=1}^{k}\mathbb{Z}_{m_j}$. They all mean the same thing except that $\displaystyle \oplus$ is reserved for when the groups are abelian (btw $\displaystyle \bigoplus$ is an analogous index operator for $\displaystyle \oplus$ as that of $\displaystyle \sum$ for $\displaystyle +$).

Ok, so for the idea. You need a quick little lemma.

Lemma: Let $\displaystyle C_n$ denote a cyclic (this lemma will show the cyclic) group of order $\displaystyle n$. Then, $\displaystyle \mathbb{Z}_n\cong C_n$

Proof: Let $\displaystyle C_n$ be generated by $\displaystyle c$ and define $\displaystyle \theta:\mathbb{Z}_n\to C_n$ by $\displaystyle k\overset{\theta}{\longmapsto}c^k$.

Clearly $\displaystyle \theta$ is injective since $\displaystyle \theta(k)=\theta(m)\implies c^k=c^m$ now we may assume WLOG that $\displaystyle 0\leqslant m\leqslant k\leqslant n$ and so the above implies that $\displaystyle c^{k-m}=e$. But! $\displaystyle |c|=n\geqslant k-m$ and so $\displaystyle k-m$ can't be strictly positive and since it's non-negative it follows that $\displaystyle k-m=0\implies k=m$

Surjectivity is clear since $\displaystyle g\in C_n\implies g=c^k$ for some $\displaystyle 0\leqslant k\leqslant n$ and so $\displaystyle k\in\mathbb{Z}_n$ and $\displaystyle \theta(k)=c^k=g$

The homomorphism property follows since $\displaystyle \theta(m+k)=c^{m+k}=c^mc^k=\theta(m)\theta(k)$.

The conclusion follows. $\displaystyle \blacksquare$

Thus, we must only prove that $\displaystyle \bigoplus_{j=1}^{k}\mathbb{Z}_{m_j}$ is cyclic and it will follow from the lemma that it is equal to $\displaystyle \mathbb{Z}_{m_1\cdots m_k}$

To see this we will prove that $\displaystyle (\underbrace{1,\cdots,1}_{k\text{ times}})$ generates $\displaystyle \bigoplus_{j=1}^{k}\mathbb{Z}_{m_k}$. To do this note that $\displaystyle |(1,\cdots,1)|$ is the least positive number such that $\displaystyle (1,\cdots,1)^d=(d,\cdots,d)=(0,\cdots,0)\quad{\col or{red}(1)}$. But, notice that the first coordinate's order is $\displaystyle m_1$ and so it will only be $\displaystyle e$ when $\displaystyle d=a_1m_1$ where $\displaystyle a_1\in\mathbb{N}$ and $\displaystyle d$ is as in $\displaystyle \color{red}(1)$. Similarly, the second slot will only be $\displaystyle e$ when $\displaystyle d=a_2m_2$ and so on and so forth. Thus, $\displaystyle |(1,\cdots,1)|$ is the first occurrence of the multiples of $\displaystyle m_1,\cdots,m_k$ matching up. In other words $\displaystyle |(1,\cdots,1)|=\text{lcm}(m_1,\cdots,m_k)$. But, since $\displaystyle \text{gcd}(m_1,\cdots,m_k)=1$ and $\displaystyle \text{lcm}(m_1,\cdots,m_k)=\frac{m_1\cdots m_k}{\text{gcd}(m_1,\cdots,m_k)}$ it follows that $\displaystyle |(1,\cdots,1)|=\text{lcm}(m_1,\cdots,m_k)=m_1\cdot s m_k$. And since $\displaystyle \left|\bigoplus_{j=1}^{k}\mathbb{Z}_{m_k}\right|=m _1\cdots m_k$ it follows that $\displaystyle (1,\cdots,1)$ generates it. Thus, $\displaystyle \bigoplus_{j=1}^{k}\mathbb{Z}_{m_k}$ is a cyclic group of order $\displaystyle r=m_1\cdots m_k$ and thus $\displaystyle \bigoplus_{j=1}^{k}\mathbb{Z}_{m_j}\cong \mathbb{Z}_r$ by our lemma.

how long did you type for this?

7. Originally Posted by rainyice
how long did you type for this?
Like eight minutes. I type LaTeX A LOT....look at my blog haha.

8. Originally Posted by Drexel28
Like eight minutes. I type LaTeX A LOT....look at my blog haha.

Where can I get a copy of LaTEX?

9. Originally Posted by MissMousey
Where can I get a copy of LaTEX?
Define "get a copy of". If you mean where can you learn to use it? There are a bagillion (precise matehamtical term) tutorials on the web, just google them. If you mean to use in like word? I use mathtype.

10. Originally Posted by Drexel28
Define "get a copy of". If you mean where can you learn to use it? There are a bagillion (precise matehamtical term) tutorials on the web, just google them. If you mean to use in like word? I use mathtype.

...thank you......?

11. Originally Posted by MissMousey
...thank you......?
You're like the third person who's given me the sardonic thank you when I said to Google something today! What's up with that?

12. Originally Posted by Drexel28
You're like the third person who's given me the sardonic thank you when I said to Google something today! What's up with that?
Emoticon included?

I was just shocked a bit by your response...but I'll go Google.

Thank you for your help. Have a good night/morning.