# Proving CRT

• Apr 6th 2010, 08:43 PM
hamidr
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.
• Apr 6th 2010, 08:55 PM
Drexel28
Quote:

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 $\bigoplus_{j=1}^{k}\mathbb{Z}_{m_j}$ is cyclic. Then, since $\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 $\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.
• Apr 6th 2010, 09:13 PM
hamidr
Quote:

Originally Posted by Drexel28
Hint: Prove that $\bigoplus_{j=1}^{k}\mathbb{Z}_{m_j}$ is cyclic. Then, since $\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 $\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
• Apr 6th 2010, 09:53 PM
Drexel28
Quote:

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 $\mathbb{Z}_{m_1}\times\cdots\times\mathbb{Z}_{m_k}$ or $\mathbb{Z}_{m_1}\oplus\cdots\oplus\mathbb{Z}_{m_k}$ in lieu of $\bigoplus_{j=1}^{k}\mathbb{Z}_{m_j}$. They all mean the same thing except that $\oplus$ is reserved for when the groups are abelian (btw $\bigoplus$ is an analogous index operator for $\oplus$ as that of $\sum$ for $+$).

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

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

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

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

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

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

The conclusion follows. $\blacksquare$

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

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

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

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

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

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

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

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

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

The conclusion follows. $\blacksquare$

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

To see this we will prove that $(\underbrace{1,\cdots,1}_{k\text{ times}})$ generates $\bigoplus_{j=1}^{k}\mathbb{Z}_{m_k}$. To do this note that $|(1,\cdots,1)|$ is the least positive number such that $(1,\cdots,1)^d=(d,\cdots,d)=(0,\cdots,0)\quad{\col or{red}(1)}$. But, notice that the first coordinate's order is $m_1$ and so it will only be $e$ when $d=a_1m_1$ where $a_1\in\mathbb{N}$ and $d$ is as in $\color{red}(1)$. Similarly, the second slot will only be $e$ when $d=a_2m_2$ and so on and so forth. Thus, $|(1,\cdots,1)|$ is the first occurrence of the multiples of $m_1,\cdots,m_k$ matching up. In other words $|(1,\cdots,1)|=\text{lcm}(m_1,\cdots,m_k)$. But, since $\text{gcd}(m_1,\cdots,m_k)=1$ and $\text{lcm}(m_1,\cdots,m_k)=\frac{m_1\cdots m_k}{\text{gcd}(m_1,\cdots,m_k)}$ it follows that $|(1,\cdots,1)|=\text{lcm}(m_1,\cdots,m_k)=m_1\cdot s m_k$. And since $\left|\bigoplus_{j=1}^{k}\mathbb{Z}_{m_k}\right|=m _1\cdots m_k$ it follows that $(1,\cdots,1)$ generates it. Thus, $\bigoplus_{j=1}^{k}\mathbb{Z}_{m_k}$ is a cyclic group of order $r=m_1\cdots m_k$ and thus $\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.(Giggle)
• Apr 13th 2010, 09:33 PM
rainyice
Quote:

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

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

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

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

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

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

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

The conclusion follows. $\blacksquare$

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

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

how long did you type for this?
• Apr 13th 2010, 09:37 PM
Drexel28
Quote:

Originally Posted by rainyice
how long did you type for this?

Like eight minutes. I type LaTeX A LOT....look at my blog haha.
• Apr 13th 2010, 09:41 PM
MissMousey
Quote:

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?
• Apr 13th 2010, 09:58 PM
Drexel28
Quote:

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.
• Apr 13th 2010, 10:08 PM
MissMousey
Quote:

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...(Thinking)...?
• Apr 13th 2010, 10:09 PM
Drexel28
Quote:

Originally Posted by MissMousey
...thank you...(Thinking)...?

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?
• Apr 13th 2010, 10:14 PM
MissMousey
Quote:

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? (Giggle)

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

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