Results 1 to 12 of 12

Math Help - Proving CRT

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    15

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by hamidr View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2010
    Posts
    15
    Quote Originally Posted by Drexel28 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by hamidr View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Apr 2010
    Posts
    37
    Quote Originally Posted by Drexel28 View Post
    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.
    Last edited by MissMousey; April 13th 2010 at 09:31 PM. Reason: Figured out question
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Feb 2010
    Posts
    84
    Quote Originally Posted by Drexel28 View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by rainyice View Post
    how long did you type for this?
    Like eight minutes. I type LaTeX A LOT....look at my blog haha.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Apr 2010
    Posts
    37
    Quote Originally Posted by Drexel28 View Post
    Like eight minutes. I type LaTeX A LOT....look at my blog haha.

    Where can I get a copy of LaTEX?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by MissMousey View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Apr 2010
    Posts
    37
    Quote Originally Posted by Drexel28 View Post
    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......?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by MissMousey View Post
    ...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?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Apr 2010
    Posts
    37
    Quote Originally Posted by Drexel28 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving y^2=-4x
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: May 27th 2010, 08:48 AM
  2. proving
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 11th 2010, 01:49 AM
  3. Please me proving this.
    Posted in the Differential Equations Forum
    Replies: 1
    Last Post: March 28th 2010, 12:29 AM
  4. Proving an identity that's proving to be complex
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: July 21st 2009, 02:30 PM
  5. Proving
    Posted in the Trigonometry Forum
    Replies: 4
    Last Post: March 27th 2008, 09:27 PM

Search Tags


/mathhelpforum @mathhelpforum