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

Printable View

- Oct 30th 2006, 02:49 PMsplashHelp 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 - Oct 31st 2006, 06:51 AMThePerfectHacker
I am :confused: confused :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$. - Oct 31st 2006, 08:41 AMThePerfectHacker
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.