Section 1.4. Lagrange’s Theorem 31 Definition. If n ≥ 1, then the Euler φ-function φ(n) is defined by φ(n) = |{k ∈ Z : 1 ≤ k ≤ n and (k, n) = 1}|. Theorem 1.39. (i) If G = a is a cyclic group of order n, then ak is a generator of G if and only if (k, n) = 1.19 (ii) If G is a cyclic group of order n and gen(G) = {all generators of G}, then |gen(G)| = φ(n), where φ(n) is the Euler φ-function. Proof. (i) If ak generates G, then a ∈ ak , so that a = akt for some t ∈ Z. Hence, akt−1 = 1 by Proposition 1.26, n | (kt−1), so there is v ∈ Z with nv = kt−1. Therefore, 1 is a linear combination of k and n, and so (k, n) = 1. Conversely, if (k, n) = 1, then ns + kt = 1 for s, t ∈ Z hence a = ans+kt = ansakt = akt ∈ ak . Therefore, a, hence every power of a, also lies in ak , and so G = ak . (ii) Since G = {1,a,...,an−1}, this result follows from Proposition 1.38. • Proposition 1.40. The intersection i∈I Hi of any family of subgroups of a group G is again a subgroup of G. In particular, if H and K are subgroups of G, then H ∩ K is a subgroup of G. Proof. This follows easily from the definitions. • Corollary 1.41. If X is a subset of a group G, then there is a subgroup X of G containing X that is smallest in the sense that X ⊆ H for every subgroup H of G that contains X. Proof. There do exist subgroups of G that contain X for example, G contains X. Define X = X⊆H H, the intersection of all the subgroups H of G containing X. By Proposition 1.40, X is a subgroup of G of course, X contains X because every H contains X. Finally, if H0 is any subgroup containing X, then H0 is one of the subgroups whose intersection is X that is, X = H ⊆ H0. • There is no restriction on the subset X in the last corollary in particular, X = ∅ is allowed. Since the empty set is a subset of every set, we have ∅ ⊆ H for every subgroup H of G. In particular, ∅ ⊆ {1}, and so ∅ = {1}. Definition. If X is a subset of a group G, then X is called the subgroup generated by X. 19The gcd (greatest common divisor) of k and n is denoted by (k, n). If (k, n) = 1, we say that k and n are relatively prime.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2010 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.