Results 1 to 3 of 3

Thread: 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
    10
    I am confused by the map,
    $\displaystyle f(n+pq\mathbb{Z})=(n+p\mathbb{Z},n+q\mathbb{Z})$
    Because the sets,
    $\displaystyle \mathbb{Z}_{pq},\mathbb{Z}_p,\mathbb{Z}_q$ are all finite and cannot be expressed as the ideals of $\displaystyle \mathbb{Z}$.

    However,
    What you want to show is the isomorphism,
    $\displaystyle \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,
    $\displaystyle \phi:\mathbb{Z}/ \mathbb{Z}_{pq}\to \mathbb{Z}/ \mathbb{Z}_p\times \mathbb{Z}/ \mathbb{Z}_q$
    As, $\displaystyle \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 $\displaystyle \mathbb{Z}/ \mathbb{Z}_{pq}$
    As,
    $\displaystyle n+pq\mathbb{Z}$ and $\displaystyle m+pq\mathbb{Z}$
    Since $\displaystyle m$ is in the same coset we can express it as,
    $\displaystyle m+pq\mathbb{Z}=n+pqk+\mathbb{Z}$ for some integer $\displaystyle k$.
    Now we show that they map this element into the same ordered coset pair.
    $\displaystyle (n+p\mathbb{Z},n+p\mathbb{Z})$
    $\displaystyle (n+pqk+p\mathbb{Z},n+pqk+q\mathbb{Z})=(n+p\mathbb{ Z},n+q\mathbb{Z})$
    Because $\displaystyle pqk$ is an element of $\displaystyle p\mathbb{Z}$ and $\displaystyle q\mathbb{Z}$.
    Thus the map is well-defined.

    We now show that this map is a homomorphism between these two groups.
    First if $\displaystyle A=a+pq\mathbb{Z}\in \mathbb{Z}/ \mathbb{Z}_{pq}$ and $\displaystyle B=b+pq\mathbb{Z}\in \mathbb{Z}/ \mathbb{Z}_{pq}$
    Then, $\displaystyle (a+pq\mathbb{Z})(b+pq\mathbb{Z})=(ab+pq\mathbb{Z})$
    Thus, we need to see whether or not,
    $\displaystyle \phi(AB)=\phi(A)\phi(B)$
    That is,
    $\displaystyle (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.
    $\displaystyle \phi(a+pq\mathbb{Z})=\phi(b+pq\mathbb{Z})$
    Thus,
    $\displaystyle (a+p\mathbb{Z},a+q\mathbb{Z})=(b+p\mathbb{Z},b+q\m athbb{Z})$
    So, $\displaystyle b=pk$ and $\displaystyle b=qj$ for some integers $\displaystyle k,j$ then, $\displaystyle b=pqs$ for some integer $\displaystyle s$; note the important fact that $\displaystyle \gcd(p,q)=1$ otherwise we cannot conclude that $\displaystyle b$ has this form. That means that $\displaystyle b$ is in the same coset as $\displaystyle a$. Thus, $\displaystyle a+pq\mathbb{Z}=b+pq\mathbb{Z}$ this show the function is indeed injective.

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

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

    Note, the last two congruences has solutions to them because, $\displaystyle \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
    10
    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,
    $\displaystyle \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,
    $\displaystyle \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: Nov 20th 2009, 12:57 PM
  3. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: Jul 31st 2009, 07:34 AM
  4. Chinese Remainder Theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 1st 2008, 01:27 AM
  5. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Apr 10th 2006, 07:28 AM

Search Tags


/mathhelpforum @mathhelpforum