# Thread: Help with some proofs (Chinese remainder theorem)

1. ## 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?

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

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