# Homework Help: Chinese remainder theorem

1. Mar 2, 2010

### rainwyz0706

(a) Let R and S be rings with groups of units R∗ and S ∗ respectively. Prove that
(R × S)∗ = R∗ × S ∗ .
(b) Prove that the group of units of Zn consists of all cosets of k with k coprime to n.
Denote the order of (Zn )∗ by φ(n); this is Euler’s φ-function.
(c) Now suppose that m and n are coprime; prove that φ(mn) = φ(m)φ(n).

I think I know how to do the first one. Let v1 in R and v2 in S, then there exist u1 in R*, u2 in S* such that u1v1=1, u2v2=1. v1 × v2 is in R×S, we have (u1u2)(v1v2)=1, then u1u2 is in (R×S)*. Hence the proof is complete. Is that correct?
for (b), I think the extended euclidean algorithm is helpful here: kK+nN =1, but I'm sure how to come up with a complete proof. Same with the third one.
Could anyone give me some hints here? Any help is greatly appreciated!

2. Mar 3, 2010

### ystael

The proof of (a) is not complete. You have proven that $$R^\times \times S^\times \subset (R \times S)^\times$$, but not the converse.

For (b), your observation is indeed exactly what you need. What does the equation $$kK + nN = 1$$ look like in $$\mathbb{Z}_n$$?

For (c), spend some time looking at what you have done so far.