When is U(n) Cyclic An Algebraic Approach

When is U (n) Cyclic? An Algebraic Approach Early in a typical abstract algebra course we learn that the set U (n) = {0 < x ≤ n | gcd(x, n) = 1} is a group under multiplication mod n for every n ≥ 1. This first appears as example 11 in Chapter 2 of Gallian’s excellent text [2], for instance. These groups are particularly nice: it is not hard to see, but not immediately obvious, that they are groups; they are important in some modern cryptographic applications; and they figure prominently in elementary number theory. Some of the groups U (n) are cyclic and some are not, and the two categories can be completely characterized by the form of the prime factorization of n. If U (n) is cyclic then we can write U (n) = hgi for some g ∈ Zn , relatively prime to n. In number theory g is known as a primitive root modulo n; we will call the characterization of those n with primitive roots the Primitive Root Theorem, or PRT. I recently taught an abstract algebra course using Gallian’s text, and I wanted to prove the PRT for the class. Though this result is standard in elementary number theory books (See, e.g., in [3]), the number-theoretic notation and proofs would have led me farther afield than I cared to go. I failed to find an algebraic proof of the result, but put one together by mining the proof in [3] for hints. The proof uses many results and exercises from [2]; this made it a satisfying conclusion to my course. Most of the proof requires only group theory, though some field theory and experience with polynomial rings is required at the very end. This proof should be accessible to students who have been through any standard undergraduate course. I will refer explicitly to theorems and exercises in [2]. Here is what we are shooting for: Theorem. (Primitive Root Theorem) U (n) is cyclic if and only if n is 1, 2, 4, pk , or 2pk , where p is an odd prime and k ≥ 1. Preliminaries First, we need some facts from number theory. The number of elements in U (n) is commonly denoted by φ(n), the Euler phi-function or totient function. When p is prime, φ(p) = p − 1, because every number in {1, 2, . . . , p − 1} is relatively prime to p. Also, φ(pk ) = pk − pk−1 for 2 prime p, because precisely pk−1 of the pk integers in {1, 2, . . . , pk } are multiples of p, and all other integers in that range that are relatively prime to pk . Note for future reference that if p is an odd prime, or if p = 2 and k ≥ 2, then pk − pk−1 is even. (This is all we will need about φ, but it is also Q true that if m and n are relatively prime then φ(mn) = φ(m)φ(n). Thus φ(n) = ki=1 (pai i − pai i −1 ) Q if n = ki=1 pai i is the prime factorization of n.) It is easy to check the primitive root theorem for n = 1, 2, 4 directly. (Don’t take my word for it—do it!) Recall that every cyclic group has exactly one subgroup of order d for each d that divides the order of the group. Thus we may show that U (2k ) is not cyclic for k > 2 by showing that U (2k ) contains two distinct elements of order 2, each of which generates a subgroup of order 2. We leave this as an exercise; it is number 54 in chapter 4 of Gallian. In Chapter 8, External Direct Products, Gallian characterizes the direct products that are cyclic groups: If G ∼ = G1 ⊕ · · · ⊕ Gm , then G is cyclic if and only if the Gi are cyclic and their orders are pairwise relatively prime. Gallian also proves (modulo some exercises left to the reader) that if m = n1 n2 · · · nk , and the ni are pairwise relatively prime, then U (m) ∼ = U (n1 ) ⊕ · · · ⊕ U (nk ). It is now not hard to see that U (n) is not cyclic if n is divisible by two distinct odd primes or by 4 and an odd prime, using the fact (mentioned earlier) that pk − pk−1 is even when p is an odd prime or p = 2 and k ≥ 2, together Q a with U ( ki=1 pai i ) ∼ = U (pa11 ) ⊕ · · · ⊕ U (pkk ). (Exercise 46 of Chapter 8 is essentially this result.) Now we know that the only groups that might be cyclic are U (pk ) and U (2pk ). (A different algebraic proof of this much appeared in [1].) In what follows, p always denotes an odd prime. Since U (2pk ) ∼ = U (2) ⊕ U (pk ) ∼ = U (pk ), we need only show that U (pk ) is cyclic. We will show that, if U (p) is cyclic, then U (p2 ) is cyclic; that this implies that U (pk ) is cyclic for k > 2; and, finally, that U (p) is cyclic. If G is a finite group, every g ∈ G has an order, denoted |g|, which is the smallest positive integer m such that g m = e (e is the identity of the group). Recall that g k = e if and only if |g| divides k, and that Lagrange’s Theorem tells us that |g| divides |G|. For the first step, we suppose that U (p) is cyclic and show that U (p2 ) is cyclic. Let U (p) = hgi, g ∈ {1, 2, . . . , p − 1}. We will show that either g or g + p generates U (p2 ). Let ht be the order of g + tp, t = 0 or 1, so that (g + tp)ht ≡ 1 (mod p2 ); then (g + tp)ht ≡ 1 (mod p) as well. Now     ht ht −1 ht ht −2 ht ht 1 ≡ (g + tp) = g + g tp + g (tp)2 + · · · + (tp)ht ≡ g ht (mod p), 1 2 3 so the order of g in U (p) divides ht , that is, (p − 1) divides ht . Since ht is the order of an element of U (p2 ), we also know that ht divides |U (p2 )| = p(p − 1). Thus, ht = p − 1 or ht = p(p − 1); we want to show that the latter is true for at least one of t = 0 or t = 1. Suppose not, so that g p−1 ≡ (g + p)p−1 ≡ 1 Then p−1 (g + p) =g p−1 (mod p2 ).     p − 1 p−2 p − 1 p−3 2 + g p+ g p + · · · + pp−1 , 1 2 or, modulo p2 , 1 ≡ 1 + (p − 1)g p−2 p, so 0 ≡ (p − 1)g p−2 p. But p2 does not divide (p − 1)g p−2 p. This contradiction implies that either g or g + p has order p(p − 1), and generates U (p2 ). Now we suppose that g generates U (p2 ) and show that g generates U (pk ), k ≥ 2. We proceed by induction. Suppose that g generates U (p2 ) and U (pi ), for all i such that 2 ≤ i ≤ k, where k ≥ 2. In particular, in U (pk ), the order of g is pk−1 (p − 1) and, if k > 2, in U (pk−1 ) the order of g is pk−2 (p − 1). Let h denote the order of g in U (pk+1 ); we want to show that h = pk (p − 1). Since g h ≡ 1 (mod pk+1 ), it is also true that g h ≡ 1 (mod pk ). This means that the order of g in U (pk ) divides h, that is, pk−1 (p − 1) divides h. Also, h divides |U (pk+1 )|, that is, h divides pk (p − 1), because h is the order of an element of U (pk+1 ). Thus h = pk (p − 1) or h = pk−1 (p − 1); we need to k−1 show that the latter is not possible. It suffices to show that g p (p−1) 6≡ 1 (mod pk+1 ). We know k−2 k−2 that g p (p−1) 6≡ 1 (mod pk ) and g p (p−1) ≡ 1 (mod pk−1 ), by the induction hypothesis (or by k−2 direct verification if k = 2). Thus g p (p−1) = 1 + bpk−1 for some b not divisible by p. Then gp k−1 (p−1) = (1 + bpk−1 )p       p p 2 2k−2 p k−1 =1+ bp + b p + ··· + bp−1 p(p−1)(k−1) + bp ppk−p . 2 p−1 1 Since pk − p ≥ k + 1, pk+1 divides the last term in this sum. The binomial coefficient by p when 1 ≤ i ≤ p − 1, because p is prime and   p p! = , i i!(p − i)! p i
is divisible with every factor in the denominator i!(p − i)! less than p. Together with the fact that 2k − 2 ≥ k, this means that pk+1 divides every term in the preceding sum except the first two, so gp k−1 (p−1) ≡ 1 + bpk (mod pk+1 ). Since p does not divide b, k−1 (p−1) gp 6≡ 1 (mod pk+1 ), which is what we were after—now we know that g generates U (pk+1 ). 4 Completing the Cycle Finally, it all comes down to U (p). We need to know that some g ∈ U (p) has order m = p − 1. Pick g to have order m in U (p), with m as large as possible. If h is any element of U (p), then |h| divides |g|, for suppose not. Then we may write |h| = q r a and |g| = q s b, where q is prime, r > s, and q does not divide either a or b. That is, if |h| does not divide |g|, it must be because some prime q appears more often in the factorization of |h| than the factorization of |g|. Now in U (p), r r s r−s (ha g)q b = (hq a )b (g q b )q = 1, so |ha g| divides q r b. Thus the order of ha g must be q t c, where t ≤ r and c|b. If t < r, then 1 = (ha g)q r−1 b = (hq r−1 a )b (g q r−1 b ) = (hq r−1 a )b , so |h| divides q r−1 ab, a contradiction. On the other hand, if c < b, then 1 = (ha g)q rc r = (hq a )c g q rc r = gq c, so |g| divides q r c, another contradiction. Thus t = r and c = b, and the order of ha g is q r b > q s b = |g|, yet another contradiction, since g was chosen to have largest possible order. Hence, |h| divides |g| = m. Now we need a bit of field theory and we’re done. For every h ∈ U (p), hm = 1, that is, h is a root of the polynomial xm − 1, so xm − 1 has p − 1 roots in U (p) and in Zp . But since Zp is a field, xm − 1 can have at most m roots. Thus p − 1 ≤ m, so in fact the order of g is p − 1 and U (p) is cyclic. References [1] David J. DeVries, The group of units in Zm , this Magazine 62 (1989), 340. [2] Joseph A. Gallian, Contemporary Abstract Algebra, Fourth Edition, Houghton Mifflin, Boston, MA, 1998. [3] Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery, An Introduction to the Theory of Numbers, Fifth Edition, John Wiley & Sons, Inc., New York, NY, 1991.