# Help with some proofs (Chinese remainder theorem)

• October 30th 2006, 03:49 PM
splash
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?

http://i3.photobucket.com/albums/y79/byee614/proofs.jpg
• October 31st 2006, 07:51 AM
ThePerfectHacker
I am :confused: confused :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$.
• October 31st 2006, 09:41 AM
ThePerfectHacker
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.