56 Chapter 1. Groups I Isomorphism Theorem now gives Z/ mn ∼ = im f ⊆ Im × In. But Z/ mn ∼ = Imn has mn elements, as does Im × In. We conclude that f is surjective. • For example, it follows that I6 ∼ = I2 × I3. Note that there is no isomorphism if m and n are not relatively prime. For example, I4 ∼ = I2 × I2, for I4 has an element of order 4 and the direct product (which is isomorphic to the four-group V) has no such element. Corollary 1.88 (Chinese Remainder Theorem). If m, n are relatively prime, then there is a solution to the system x ≡ b mod m x ≡ c mod n. Proof. In the proof of Theorem 1.87, we showed that the map f : Z → Im × In, given by a → ([a]m, [a]n), is surjective. But ([b]m, [c]n) = ([a]m, [a]n) says that [a]m = [b]m and [a]n = [c]n that is, a ≡ b mod m and a ≡ c mod n. • In light of Proposition 1.38, we may say that an element a ∈ G has order n if a ∼ = In. Theorem 1.87 can now be interpreted as saying that if a and b are commuting elements having relatively prime orders m and n, then ab has order mn. Let us give a direct proof of this result. Proposition 1.89. Let G be a group, and let a, b ∈ G be commuting elements of orders m and n, respectively. If (m, n) = 1, then ab has order mn. Proof. Since a and b commute, we have (ab)r = arbr for all r, so that (ab)mn = amnbmn = 1. It suﬃces to prove that if (ab)k = 1, then mn | k. If 1 = (ab)k = akbk, then ak = b−k. Since a has order m, we have 1 = amk = b−mk. Since b has order n, Proposition 1.26 gives n | mk. As (m, n) = 1, however, we have n | k a similar argument gives m | k. Finally, since (m, n) = 1, we have mn | k. Therefore, mn ≤ k, and mn is the order of ab. • Corollary 1.90. If (m, n) = 1, then φ(mn) = φ(m)φ(n), where φ is the Euler φ-function. Proof. 29 Theorem 1.87 shows that the function f : Imn → Im × In, given by [a] → ([a]m, [a]n), is an isomorphism. This corollary will follow if we prove that f(U(Imn)) = U(Im) × U(In), for then φ(mn) = |U(Imn)| = |f(U(Imn))| = |U(Im) × U(In)| = |U(Im)| · |U(In)| = φ(m)φ(n). If [a] ∈ U(Imn), then [a][b] = [1] for some [b] ∈ Imn, and f([ab]) = ([ab]m, [ab]n) = ([a]m[b]m, [a]n[b]n) = ([a]m, [a]n)([b]m, [b]n) = ([1]m, [1]n) that is, [1]m = [a]m[b]m and [1]n = [a]n[b]n. Therefore, f([a]) = ([a]m, [a]n) ∈ U(Im) × U(In), and f(U(Imn)) ⊆ U(Im) × U(In). 29See Exercise 2.41 on page 101 for a less cluttered proof.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright no copyright American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.