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 suffices 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.
Previous Page Next Page