Results 1 to 3 of 3

Math Help - Help with some proofs (Chinese remainder theorem)

  1. #1
    Junior Member
    Joined
    Oct 2006
    Posts
    43

    Help with some proofs (Chinese remainder theorem)

    Is this the right forum for this? I need some help getting started with a couple of proofs. Can anyone get me started in the right direction?

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    I am confused by the map,
    f(n+pq\mathbb{Z})=(n+p\mathbb{Z},n+q\mathbb{Z})
    Because the sets,
    \mathbb{Z}_{pq},\mathbb{Z}_p,\mathbb{Z}_q are all finite and cannot be expressed as the ideals of \mathbb{Z}.

    However,
    What you want to show is the isomorphism,
    \mathbb{Z}/ \mathbb{Z}_{pq} \simeq \mathbb{Z}/ \mathbb{Z}_p\times \mathbb{Z}/ \mathbb{Z}_q
    Using the map defined above. Then it would make sense.
    Do you understand me?
    ---
    Okay here is the proof on what I said.

    First we are given a function,
    \phi:\mathbb{Z}/ \mathbb{Z}_{pq}\to \mathbb{Z}/ \mathbb{Z}_p\times \mathbb{Z}/ \mathbb{Z}_q
    As, \phi(n+pq\mathbb{Z})=(n+p\mathbb{Z},n+q\mathbb{Z})
    We need to show that this map is well-defined.
    Assume there are two ways to express the same element of \mathbb{Z}/ \mathbb{Z}_{pq}
    As,
    n+pq\mathbb{Z} and m+pq\mathbb{Z}
    Since m is in the same coset we can express it as,
    m+pq\mathbb{Z}=n+pqk+\mathbb{Z} for some integer k.
    Now we show that they map this element into the same ordered coset pair.
    (n+p\mathbb{Z},n+p\mathbb{Z})
    (n+pqk+p\mathbb{Z},n+pqk+q\mathbb{Z})=(n+p\mathbb{  Z},n+q\mathbb{Z})
    Because pqk is an element of p\mathbb{Z} and q\mathbb{Z}.
    Thus the map is well-defined.

    We now show that this map is a homomorphism between these two groups.
    First if A=a+pq\mathbb{Z}\in \mathbb{Z}/ \mathbb{Z}_{pq} and B=b+pq\mathbb{Z}\in \mathbb{Z}/ \mathbb{Z}_{pq}
    Then, (a+pq\mathbb{Z})(b+pq\mathbb{Z})=(ab+pq\mathbb{Z})
    Thus, we need to see whether or not,
    \phi(AB)=\phi(A)\phi(B)
    That is,
    (ab+p\mathbb{Z},ab+q\mathbb{Z})=(a+p\mathbb{Z},a+q  \mathbb{Z})\cdot (b+p\mathbb{Z},b+q\mathbb{Z})---> True for all.
    Thus it is indeed a homomorphism.

    Now, we see if this function is injective.
    \phi(a+pq\mathbb{Z})=\phi(b+pq\mathbb{Z})
    Thus,
    (a+p\mathbb{Z},a+q\mathbb{Z})=(b+p\mathbb{Z},b+q\m  athbb{Z})
    So, b=pk and b=qj for some integers k,j then, b=pqs for some integer s; note the important fact that \gcd(p,q)=1 otherwise we cannot conclude that b has this form. That means that b is in the same coset as a. Thus, a+pq\mathbb{Z}=b+pq\mathbb{Z} this show the function is indeed injective.

    The last thing is whether any element of \mathbb{Z}/ \mathbb{Z}_p\times \mathbb{Z}/ \mathbb{Z}_q can be obtained from a map.
    Does there exists a x+pq\mathbb{Z} such that can be mapped into,
    (a+p\mathbb{Z},b+q\mathbb{Z})
    For any a,b?

    Meaning, a x such that a=x+pk and b=x+qj. Note the last two equations are saying,
    x\equiv a(\mbox{ mod } p)
    x\equiv b(\mbox{ mod } q)
    And we can find such an x!.
    That is the Chinese Remainder Theorem.
    If we chose,
    x=aqy+bpz
    Where,
    qy\equiv 1 (\mbox{ mod } p)
    pz\equiv 1 (\mbox{ mod } q)
    Then, x is a simultaneous solution to the congruence.
    Thus, we proved isomorphism!

    Note, the last two congruences has solutions to them because, \gcd(p,q)=1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    There is a more elegant way to prove this, without solving that congruence via Chinese Remainder Theorem, though I did not find a proper map.

    We know that,
    \phi: \mathbb{Z}/\mathbb{Z}_{pq}\to \mathbb{Z}/ \mathbb{Z}_p \times \mathbb{Z}/ \mathbb{Z}_q
    Is a one-to-one map.

    Then if we can find a map,
    \psi:\mathbb{Z}/ \mathbb{Z}_p \times \mathbb{Z}/ \mathbb{Z}_q\to  \mathbb{Z}/\mathbb{Z}_{pq}
    That is also one-to-one.

    Then, you can conclude that the sets has the same cardinality.

    Now there is a theorem, that if a function is injective and maps a finitie set into another finite set of equal cardinality then that function is also surjective.

    So if you can find a one-to-one mapping function backswards then you automatically know that your injective is a bijection which assures us of a solution to those congruences.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 10th 2010, 01:24 PM
  2. Chinese remainder theorem
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 20th 2009, 12:57 PM
  3. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: July 31st 2009, 07:34 AM
  4. Chinese Remainder Theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 1st 2008, 01:27 AM
  5. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 10th 2006, 07:28 AM

Search Tags


/mathhelpforum @mathhelpforum