Section 1.6. Quotient Groups 57 For the reverse inclusion, if f([c]) = ([c]m, [c]n) ∈ U(Im) × U(In), then we must show that [c] ∈ U(Imn). There is [d]m ∈ Im with [c]m[d]m = [1]m, and there is [e]n ∈ In with [c]n[e]n = [1]n. Since f is surjective, there is b ∈ Z with ([b]m, [b]n) = ([d]m, [e]n), so that f([1]) = ([1]m, [1]n) = ([c]m[b]m, [c]n[b]n) = f([c][b]). Since f is an injection, [1] = [c][b] and [c] ∈ U(Imn). • Corollary 1.91. (i) If p is prime, then φ(pe) = pe − pe−1 = pe 1 − 1 p . (ii) If n = p11 e · · · ptt e is the prime factorization, where p1,...,pt are distinct primes, then φ(n) = n 1 − 1 p1 · · · 1 − 1 pt . Proof. Part (i) holds because (k, pe) = 1 if and only if p k, while part (ii) follows from Corollary 1.90. • Lemma 1.92. Let G = a be a cyclic group. (i) Every subgroup S of G is cyclic. (ii) If |G| = n, then G has a unique subgroup of order d for each divisor d of n. Proof. (i) We may assume that S = {1}. Each element s ∈ S, as every element of G, is a power of a. If m is the smallest positive integer with am ∈ S, we claim that S = am . Clearly, am ⊆ S. For the reverse inclusion, let s = ak ∈ S. By the Division Algorithm, k = qm + r, where 0 ≤ r m. Hence, s = ak = amqar = ar. If r 0, we contradict the minimality of m. Thus, k = qm and s = ak = (am)q ∈ am . (ii) If n = cd, we show that ac has order d (whence ac is a subgroup of order d). Clearly (ac)d = acd = an = 1 we claim that d is the smallest such power. If (ac)m = 1, where m d, then n | cm, by Proposition 1.26 hence cm = ns = dcs for some integer s, and m = ds ≥ d, a contradiction. To prove uniqueness, assume that x is a subgroup of order d [every subgroup is cyclic, by part (i)]. Now x = am and 1 = xd = amd hence md = nk for some integer k. Therefore, x = am = (an/d)k = (ac)k, so that x ⊆ ac . Since both subgroups have the same order d, it follows that x = ac . • The next theorem will be used to prove Theorem 2.46: the multiplicative group Ip × is cyclic if p is prime. We will use Proposition 2.71(iii) in the next proof it says that n = ∑ d|n φ(d) for every integer n ≥ 1. Theorem 1.93. A group G of order n is cyclic if and only if, for each divisor d of n, there is at most one cyclic subgroup of order d. Proof. If G is cyclic, then the result follows from Lemma 1.92.

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.