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 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.