Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Chinese remainder theorem

  1. Mar 2, 2010 #1
    (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. jcsd
  3. Mar 3, 2010 #2
    The proof of (a) is not complete. You have proven that [tex]R^\times \times S^\times \subset (R \times S)^\times[/tex], but not the converse.

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

    For (c), spend some time looking at what you have done so far.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook