Help with some proofs (Chinese remainder theorem)

**splash** · October 30th 2006, 02:49 PM

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?

**ThePerfectHacker** · October 31st 2006, 06:51 AM

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$ .

**ThePerfectHacker** · October 31st 2006, 08:41 AM

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.

Thread: Help with some proofs (Chinese remainder theorem)

LinkBack

Thread Tools

Display

Help with some proofs (Chinese remainder theorem)

Similar Math Help Forum Discussions

Chinese Remainder Theorem

Chinese remainder theorem

Chinese Remainder Theorem

Chinese Remainder Theorem

Chinese Remainder Theorem

Search Tags