1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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