Multiplicative Groups in Zm

MULTIPLICATIVE GROUPS IN Zm 1. Abstract Our goal will be to find subsets of Zm that form groups under the operation of multiplication modulo m. By utilizing the isomorphism Zm ∼ = Zn ⊕ Zk , we will find multiplicative groups contained in Zn ⊕ Zk and then map these back to Zm . In particular, if m = nk with gcd(n, k) = 1, our objective is to find particular multiplicative subsets of Zn × Zk that are groups and whose first coordinate is a projection onto U (n). We will give a method to calculate the total number of these subsets, and identify the elements of which they are composed. 2. Preliminaries - Notation and the Chinese Remainder Theorem We will be examining subsets of {0, 1, 2, .....m − 1}, m ∈ Z+ , that when paired with the operation of multiplication modulo m, are closed, have a multiplicative identity element, and have a multiplicative inverse for each element. Thus we will be examining groups that consist of a binary operation of multiplication modulo m on finite sets of positive integers. Definition 2.1 (Binary Operation). Let G be a set. A binary operation on G is a function that assigns each ordered pair of elements of G an element of G. Definition 2.2 (Group). Let G be a nonempty set together with a binary operation that assigns to each ordered pair (a,b) of elements of G an element in G denoted by ab. We say G is a group under this operation if the following three properties are satisfied. (1) Associativity. The operation is associative; that is, (ab)c = a(bc) for all a, b, c in G (2) Identity. There is an element e (called the identity) in G, such that ae = ea = a for all a in G. (3) Inverses. For each element a in G, there is an element b in G (called an inverse of a) such that ab = ba = e. The topics dealt with will all be familiar to anyone that has taken a first course in Abstract Algebra. The notation will be the same as that which is used in Gallian’s Contemporary Abstract Algebra[1]. We will expect the reader to have familiarity with common group theoretic topics, including cyclic groups, finite Abelian groups, rings, and fields. However, those theorems and concepts which are integral to the development of splittings will be restated and recalled as necessary. Because the group operation will always be either addition or multiplication modulo n, the groups we examine will also all be Abelian. That is, for all a, b ∈ G, ab = ba. Also, many of the groups we will examine will be cyclic, meaning that 1 2 multiples of some element will generate the entire group. When a cyclic group A is generated by an element a we write hai = A. Generalized Chinese Remainder Theorem for Groups When dealing with an integer, it is often helpful to know its prime factorization. Breaking something into its smaller component parts allows further insight into how each part functions and contributes to the behavior of the whole. When working with finite Abelian groups, an analogous process allows us to decompose complex groups into simpler parts. We accomplish this decomposition with the help of the First Isomorphism Theorem, found in [1]. Theorem 2.1 (First Isomorphism Theorem). Let Φ be a group homomorphism from G1 to G2 . Then the mapping from G/KerΦ to Φ(G), given by gKerΦ → Φ(g), is an isomorphism. In symbols, G/KerΦ ∼ = Φ(G). Now we are ready to show how Zm can be equivalently expressed in terms of its simpler parts. Theorem 2.2 (Generalized Chinese Remainder Theorem for Groups). Suppose some positive integer m = nk where gcd(n, k) = 1. Then Zm ∼ = Zn ⊕ Zk Proof. Let m = nk where (n, k) = 1. Consider the homomorphism φ|Z → Zn ⊕ Zk given by φ(x) = ([x]n , [x]k ) [where [x]n denotes the remainder of x upon division by n]. The kernel of this homomorphism will be the set of all elements x ∈ Z such that φ(x) = ([0]n , [0]k ). Then in order to be in the kernel, it must be divisible by both n and k. As n and k are relatively prime, lcm(n, k) = nk. The least common multiple of two numbers has the property that any common multiple of two numbers is also divisible by their lcm. Then the set hnki= Ker φ. We know from the First Isomorphism Theorem that, Z/hnki ∼ = φ(Z). The group Z/hnki is also isomorphic to Znk (Also a consequence of the First Isomorphism Theorem considering the mapping Φ|Z → Znk given by Φ(x) = [x]nk ). Therefore Znk ∼ = Z/hnki ∼ = φ(Z) where φ(Z) ⊆ Zn ⊕ Zk . As Zn ⊕ Zk has only nk elements, and it is isomorphic to Znk which also has nk elements, φ(Z) = Zn ⊕ Zk . Hence Zm ∼ = Zn ⊕ Zk .  3. Introduction Given a particular Zm , how can we find subsets of it that will form a group with the operation of multiplication modulo m?. Simply taking the whole set will evidently not work. Suppose we look at the set of integers S = {0, 1, 2, 3, ...39} with the operation multiplication modulo 40. This set is not a group, although it satisfies almost all of the necessary criteria. The operation is associative. Clearly, the set is also closed under the operation. Applying the modulo 40 to any integer will yield an integer n, 0 ≤ n ≤ 40 contained in the set. Furthermore, the standard multiplicative identity 1 is contained in the set, such that for all a in S, 1a = a1 = a. All that remains to be verified are inverses, and this is precisely where it fails to be a group. The element 0 can never have an inverse (i.e. a solution to the equation x · 0 = 1 mod 40). However, if we discard 0, there are still other elements that fail to have an inverse. If we take the element 20 and multiply it by any other MULTIPLICATIVE GROUPS IN Zm 3 member of the group, the result modulo 40 will be either 0 or 20, neither of which is the identity. One method is to take a simply take a subset of S that consists only of units, that is, only those elements in S that have an inverse. In this case, the set of units is denoted U (40). U -groups will be important to splittings, and we shall examine them in more detail in the next section. Other than U (40), will there be any other subsets of S that form a group? At first glance it seems likely that we will at least need the element 1 to act as the identity. This turns out to be false. Consider the subset {5, 15, 25, 35}. With these elements we form a Cayley Table, a table used for displaying every possible multiplication in a group in an analogous manner to a multiplication table. 5 25 35 5 15 5 15 25 35 15 35 25 15 5 25 5 15 25 35 35 15 5 35 25 Notice that the element 25 behaves as the identity element in this set. Also, each row and column contains 25, thus each element has some inverse element. With closure, associativity, an identity element, an inverses, it satisfies the group criteria. Despite the fact that none of the elements of the group are units of Z40 , and despite lacking the expected identity 1, the set forms a group with the operation multiplication modulo 40. These numbers were obviously not chosen at random. If one attempted to form a group by picking and choosing elements randomly S they would quickly see the futility of the endeavor. How can we make sense of this? We will investigate the behavior of this set and apply this knowledge to see how we might construct other similar sets. 4. The group of units U (n) and its structure We now return to our first example of a set of integers that was closed under the operation of multiplication modulo 40, {5, 15, 25, 35}. Note that each of these terms is divisible by 5. If we divide each member as well as the modulus by 5, we obtain the set of integers {1, 3, 5, 7} under multiplication modulo 8. We form another Cayley table with this set and binary operation and see that, interestingly enough, it also forms a group. 1 3 5 7 1 1 3 5 7 3 3 1 7 5 5 5 7 1 3 7 7 5 3 1 Those familiar with group theory will immediately recognize this group as the group of units U (8). The group of units U (n) is a common group studied in an introductory abstract algebra class. It is the set of numbers less than n and relatively prime to n under the operation multiplication modulo n. 4 It is well known and easy to verify that one may choose any n ∈ Z+ and U (n) will be a group. It may be helpful to do a few calculations with the following U groups to see that they satisfy the properties of a group (closure, identity, inverses) U (5) = {1, 2, 3, 4}, U (10) = {1, 3, 7, 9}, U (13) = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} An examination of the structure and behavior of U (n) will be necessary for further insight into the original set {5, 15, 25, 35} and in order to understand how we might construct other similar sets. For which n is U (n) cyclic? Some of the U -groups are cyclic, such as U (5) and U (10). (consider h2i = U (5) and h3i = U (10)). In the case of U (8), we find that every element is its own inverse, and no element generates all of U (8). Hence U (8) is not cyclic. For what positive integers n is U (n) cyclic? It is precisely those n which have a primitive root modulo n, defined to be the specific integer g ∈ U (n) that generates U (n). Here is what we will be proving: Theorem 4.1 (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. Before getting started, we need to recall some concepts from number theory and familiar theorems from group theory that will be necessary for the proof. How many elements will U (n) have? Given an integer n, the number of elements less than and relatively prime to n is given by Φ(n) , where Φ is the Euler phifunction. Consider the case of U (p) for a prime p. Every integer less than p is relatively prime to p, therefore U (p) will have p − 1 elements. Also, note that for U (pk ), Φ(pk ) = pk − pk−1 (to see this, consider the number of integers that are multiples of p between 1 and pk ). We now remind the reader of two familiar theorems from group theory. Theorem 4.2 (Fundamental Theorem of Cyclic Groups). Every subgroup of a cyclic group is cyclic. Moreover, if |hai| = n, then the order of any subgroup of hai is a divisor of n: and, for each positive divisor k of n, the group hai has exactly one subgroup of order k—namely, han/k i. To apply this theorem consider the cyclic group Z6 . The divisors of 6 are 6, 3, and 2. Hence there will be exactly one subgroup each of orders 6, 3, 2, and 1, generated as follows. h1i = h5i = {0, 1, 2, 3, 4, 5} = Z6 h2i = h4i = {2, 4, 0} h3i = {3, 0} Another important theorem allows for the decomposition of any finite Abelian group into simpler parts. Theorem 4.3 (Fundamental Theorem of Finite Abelian Groups). Every finite Abelian group is isomorphic to a direct product of cyclic groups of prime-power order. Moreover, the factorization is unique except for rearrangement of the factors. Because each U (n) is finite and Abelian, it has the unique representation U (n) ∼ = Z a1 ⊕ Z a2 ⊕ ... ⊕ Zpan p1 p2 n MULTIPLICATIVE GROUPS IN Zm 5 for not necessarily distinct primes p1 to pn and ai ≥ 1. The representation as a direct product of cyclic groups is the isomorphism class of U (n). For now we will not examine the method of finding these isomorphism classes. That they exist will be sufficient. Only note that when U (n) is cyclic with order Φ(n), the isomorphism class of U (n) is ZΦ(n) . As an example, in the context of the U -groups we have been using, the isomorphism classes of U (8) and U (5) are U (5) ∼ = Z4 Z U (8) ∼ = 2 ⊕ Z2 Now we can begin to approach the topic of when U (n) will be cyclic. The proof will be broken into several cases, each examining a part of the Primitive Root Theorem. It is easy to write out and verify that for n = 1, 2, 4, U (n) is cyclic. We will first show that U (p) is cyclic for any odd prime p. Next we will show that this implies both U (p2 ) and U (pk ) are cyclic. Finally, we show that when n is divisible by more than one distinct odd prime, or by 2k for k ≥ 2, U (n) is not cyclic. The first task is to show that U (n) is cyclic for an odd prime p. We begin with a definition and two lemmas. Definition 4.1. The least common multiple of a set of positive integers {a1 , a2 , ..., am }, denoted lcm(a1 , a2 ...am ), is the smallest positive integer b such that ai |b for 1 ≤ i ≤ m. It follows1 that if for some positive integer c, ai |c for 1 ≤ i ≤ m, then b|c. Lemma 4.4. If x = lcm(a1 , a2 , ..., am ), y = lcm(b1 , b2 , ..., bm ) with bi |ai for 1 ≤ i ≤ m then y|x. Proof. If bi |ai then bi ci = ai , so that x = lcm(b1 c1 , b2 c2 , ..., bm cm ). By definition each bi ci |x, and furthermore, bi |x for 1 ≤ i ≤ m. Therefore y|x.  Lemma 4.5. Let G be a finite Abelian group and m be an element of maximal order contained in G. Then for every element b ∈ G, the order of g divides the order of m. Proof. If G is a finite Abelian group, then it is isomorphic to Zpn1 1 ⊕ Zpn2 2 ⊕ .... ⊕ Zpnk k where the pi ’s are not necessarily distinct primes. We know from [1] that an element g = (g1 , g2 , ..., gk ) has order lcm(|g1 |, |g2 |, ..., |gk |). An element of maximal order will be generated by a k-tuple of the form (1, 1, ..., 1, ). As each entry is a generator for its respective Zpni , each will have order pni i . Thus |m| = lcm(pn1 1 , pn2 2 , ..., pnk k ). i Let b be some element in G. It has the form b = (b1 , b2 , ..., bk ) where each bi is a member of Zpni . Lagrange’s Theorem states that the order of an element of a i group divides the order of the group, so for 1 ≤ i ≤ k |bi | | |pni i | The order of b is lcm(|b1 |, |b2 |, ...|bk |) and the order of m is lcm(pn1 1 , pn2 2 , ..., pnk k ). Then by the previous lemma, the order of b divides the order of m.  1See definition of lcm(a, b) given by [2]. 6 We proceed by examining U (n) for particular cases of n. Case 1: U (n) is cyclic when n = p for a prime p. The proof will assume that the reader is familiar with the concepts of fields, and polynomials defined over a field. Proof. The group U (p) has order p − 1 given by Φ(p). Each non-identity element of U (p) has some order less than or equal to p − 1 and greater than 1. Let m be an element of order n with maximal order in U (p). We proceed by contradiction. Assume U (p) is not cyclic. Then n is strictly less than p − 1. Observe that the elements of U (p) are contained in the field Zp−1 . Define a polynomial P (x) = xn −1 over Zp−1 . Then P (m) = mn − 1 = 1 − 1 = 0 and m is a root of P (x). Let g be any other element of U (p). By Lemma 1.3, the order of g divides the order of m. Then for each g, there exists a positive integer a such that a|g| = n, so that P (g) = g n − 1 = (g |g| )a − 1 = 1a − 1 = 0 Therefore all p − 1 elements of U (p) are roots of P (x), but P (x) is a polynomial of degree n and can thus have at most n roots. This contradicts the hypothesis n < p − 1, therefore n = p − 1 and U (p) is cyclic.  Case 2: U (n) is cyclic when n = p2 for a prime p Proof. As U (p) is cyclic, there exists g ∈ U (p) such that hgi = U (p). We will show that U (p2 ) is cyclic by showing that either the element g or g + p has an order of (p2 − p). Let ht be the order of g + tp where t is equal to 0 or 1. Then by definition, (g + tp)ht ≡ 1 mod p2 and (g + tp)ht ≡ 1 mod p. So, 1 ≡ (g + tp)ht (modp),     ht ht −1 ht ht −2 ≡ g ht + g (tp) + g (tp)2 + ... + (tp)ht (modp), 1 2 ≡ g ht , and g ht = 1. For any element a of a group G, with identity e, if ak = e then |a| k. Because g is a generating element of U (p) it has order (p − 1), so (p − 1)|ht . Recall the corollary to Lagrange’s theorem that states that the order of each element of a group divides the order of the group. Therefore ht divides p2 − p, the order of U (p2 ), or equivalently, ht |p(p − 1). Thus there exists positive integers a and b such that (p − 1)a = ht and bht = p(p − 1). Combining the equations yields ab(p − 1) = p(p − 1), or ab = p. Therefore either a = 1 or b = 1. We conclude that either ht = p − 1 or ht = p(p − 1). MULTIPLICATIVE GROUPS IN Zm 7 By way of contradiction, assume that ht = p − 1 for both t = 1 and t = 0 for the element g + tp. Then g p−1 ≡ 1 mod p2 and (g + p)p−1 ≡ 1 mod p2 , and 1 ≡ (g + p)p−1 (modp2 )     p − 1 p−2 p − 1 p−3 2 ≡ g p−1 + g (p) + g (p) + ... + (p)p−1 (modp2 ) 1 2   p − 1 p−2 ≡ 1+ g (p) + 0 + 0...(modp2 ) 1 ≡ 1 + (p − 1)g p−2 p(modp2 ) ≡ 1 − g p−2 p(modp2 ) Therefore p2 |(1 − (1 − g p−2 p), that is, p2 |pg p−2 . But the element g p−2 is an element of U (p2 ), and gcd(g p−2 , p) = 1, so it is not possible for p2 to divide pg p−2 because it has at most one factor of p in its prime factorization. Therefore the original assumption is false, and one of the elements g or g + p has order p2 − p. Thus U (p2 ) is cyclic.  Case 3: U (n) is cyclic when n = pk for an odd prime p. Proof. Proceeding by induction we begin with the hypothesis that U (pk ) is cyclic and generated by some element g. Also by hypothesis, each U (pi ) for i = 2 to i = k − 1 is also cyclic, and generated by the same element g. Let h be the order of the element g in U (pk+1 ), then h|pk (p − 1). Observe that g h ≡ 1 mod pk+1 ≡ 1 mod pk . Therefore, pk−1 (p − 1)|h, so either h = pk (p − 1) or h = pk−1 (p − 1). This fact will be useful shortly. Suppose that h = pk−1 (p − 1). In U (pk ), the element g has order pk−1 (p − 1), and in U (pk−1 ), the element g has order pk−2 (p − 1). Thus k−2 gp (p−1) 6= 1(modpk ) This is valid because when g is raised to any power less than its order in U (pk ), k−2 it will not be congruent to 1 mod pk . Therefore g p (p−1) = 1 + upk−1 for some k−2 integer u. Note that p does not divide u, for if it did, g p (p−1) ∼ = 1( mod pk ). Then  k−2 p g p (p−1) = (1 + upk−1 )p       p p p k−1 k−1 2 = 1+ up + (up ) + (upk−1 )2 + ... + (upk−1 )p (modpk+1 ) 1 2 2 ≡ 1 + pupk−1 (modpk+1 ) = 1 + upk (modpk+1 ) k−2 k−1 So we have (g p (p−1) )p = 1 + upk , which is equivalent to g p (p−1) = 1 + upk k−1 where p does not divide u. Then g p (p−1) 6= 1(modpk+1 ) so h,the order of g, is not pk−1 (p − 1) and therefore it must be the other option, h = pk (p − 1), and hgi = U (pk+1 ). Hence U (pk+1 ) is cyclic.  Case 4: U (n) is not cyclic when n is a product of distinct odd primes. 8 So far we have concluded that U (n) is cyclic for n equal to 1, 2, 4, p2 , and q k for odd primes q. We consider the case when n is a product of more than one odd prime. An isomorphism exists to decompose U -groups in much the same way we decompose Zn . Given two relatively prime positive integers s and t, we may write U (st) ∼ = U (s) ⊕ U (t) An isomorphism Φ from U (st) to U (s)⊕U (t) is given by Φ(x) = (x mod s, x mod t). That this mapping is operation preserving, one to one, and onto is not hard to verify. Given any n, it is also not hard to see that using this method U (n) can be expressed as a direct product of U -groups of prime power order. A theorem from [1] then tells us exactly when this direct product will be cyclic. Theorem 4.6 (Criterion for G1 ⊕ G2 ⊕ ... ⊕ Gn to Be Cyclic). An external direct product G1 ⊕ G2 ⊕ ... ⊕ Gn of a finite number of finite cyclic groups is cyclic if and only if |Gi | and |Gj | are relatively prime when i 6= j From this, the fact that U (n) is not cyclic for n that are products of distinct odd primes. Proof. Suppose that the prime factorization of n is n = pa1 1 pa2 2 · · · pakk where each pi is distinct and k ≥ 2. Then U (n) may be written as an external direct product in terms of its relatively prime parts. a U (Πki=1 pai i ) ∼ = U (pa1 1 ) ⊕ ... ⊕ U (pkk ) The order of U (pakk ) is Φ(pakk ) = pakk − pakk −1 which is always an even number (note that both terms will always be odd). Then each member of the external direct product has even order, and their orders are not pairwise relatively prime, implying U (n) is not cyclic.  Case 5: U (n) is not cyclic for n = 2k , k > 2 Proof. Consider U (n) for n = 2k , k > 2. For any cyclic group, there will be exactly one subgroup of order d for each divisor of the order of the group. Thus it is sufficient to show that U (2k ) will have two distinct subgroups of order 2 to show it is not cyclic. U (2k ) will contain every odd positive integer less than or equal to 2k , thus both 2k − 1 and 2k−1 − 1 are contained in U (2k ). Observe that (2k − 1)2 = 2k+1 − 2k + 1 = 1(mod2k ) (2k−1 − 1)2 = 22k−2 − 2k + 1 = 1(mod2k ) Then both elements generate a different subgroup of order 2, and it follows that U (2k ) is not cyclic.  All that remains is the case when n = 2pk for k ≥ 1. We may rewrite U (2pk ) as U (2pk ) ∼ = U (2)×U (pk ). Because U (2) = {1} it is trivially true that U (2)×U (pk ) ∼ = U (pk ). Hence U (2pk ) ∼ = U (2) × U (pk ) ∼ = U (pk ) Since they are isomorphic and U (pk ) is cyclic, U (2pk ) is also cyclic. This completes the proof of the Primitive Root Theorem. MULTIPLICATIVE GROUPS IN Zm 9 One last piece of information will be necessary regarding the structure of U (n). So far, we have a method of breaking U (n) down into simpler parts by first separating n into its prime factorization, and then recognizing that each of those odd prime power parts is isomorphic to a cyclic group. If n’s prime factorization contains more than one factor of 2, then there will be some U (2k ) in the initial separation of U (n) a U (Πki=1 pai i ) ∼ = U (2k ) ⊕ U (pa1 1 ) ⊕ ... ⊕ U (pkk ). In order to completely decompose U (n) into a direct product of cyclic groups, the isomorphism class of U (2n ) will be necessary. n−2 Lemma 4.7. If n ≥ 2, 52 = 1 + un 2n , where un is odd. Proof. We proceed by induction. For n = 2 observe that 52 2−2 k−2 Assume that for n = k, 52 (k+1)−2 52 = 5 = 1 + (1)(22 ). = 1 + uk (2k ) where uk is odd. Then for n = k + 1 (k−1) = 52 = 52 = (1 + uk (2k ))(1 + uk (2k )) = 1 + 2uk 2k + u2k 22k = 1 + uk 2k+1 + u2k 22k = 1 + 2k+1 (uk + u2k 2k−1 ) (k−2) (k−2) 52 (k+1)−2 Since (uk + u2k 2k−1 ) will always be odd, we may write 52 for some odd number uk+1 . This completes the proof. = 1 + uk+1 2k+1  With this lemma, we may proceed to find the isomorphism class of U (n) when n contains a factor of 4 or some higher power of 2. Theorem 4.8. For n ≥ 2, U (2n ) is isomorphic to Z2n−2 ⊕ Z2 Proof. We know by from Euler Phi function that U (2n ) has order 2n −2n−1 = 2n−1 . By the Fundamental Theorem of Finite Abelian Groups, U (2n ) will be isomorphic to some direct product of cyclic groups. Because the order of U (2n ) is 2n−1 , each cyclic group in the direct product must be some power of 2 less than or equal to n − 1. Also, since it is not cyclic, it cannot be isomorphic to Z2n−1 . Note that if an element with order 2k exists in U (2n ), then at least one member of the direct product of cyclic groups will also have an order of at least 2k . We will show that U (n) contains an element of order 2n−2 , implying Z2n−2 is a member of the external direct product of cyclic groups to which U (2n ) is isomorphic. If Z2n−2 is a member of this direct product, the remainder of the product must be a cyclic group of order 2 such that U (2n ) ∼ = Z2n−2 ⊕ Z2 n as this gives U (2 ) its appropriate order 2n−1 . From the previous lemma, we know that 5 has an order that divides 2n−2 . In order to show that 2n−2 is the order of 5 we also have to show that it is the smallest 10 number m such that 5m = 1 mod 2n . As 5 must have an order that is a power of 2 it is sufficient to show that n−3 52 6= 1 mod 2n . n−3 From the previous lemma, 52 = 1 + u2n−1 for some positive odd integer u. n−3 By way of contradiction, we suppose that 52 = 1 + q2n for a positive integer q. Thus 1 + u2n−1 = 1 + q2n , and u2n−1 = q2n . As u is odd, the previous statement must be false. Thus the order of the element 5 in U (2n ) is 2n−2 . This completes the proof.  5. kU (n) and Splittings of Zm As we saw earlier, we were able to take U (8), multiply each element as well as the multiplication modulus by 5, and the resulting set formed a group. We denote this group 5U (8). Alternatively, consider the set 8U (5) = {8, 16, 24, 32} with operation multiplication modulo 40. Constructing a Cayley Table demonstrates this is also a group. 8 16 8 24 8 16 8 16 24 32 24 32 16 32 Table 1. 24 32 32 16 24 32 16 8 8 24 8U (5) Also consider 3U (8) = {3, 9, 15, 21}. The operation will be multiplication modulo 24. We again construct a Cayley Table and verify that it is also a group (Refer to Table 2). 3 9 3 9 3 9 3 9 15 21 15 21 15 21 Table 2. 15 21 21 15 15 21 9 3 3 9 3U (8) Will it be the case that kU (n) is a group for any positive integer k? Examining 2U (8) = {2, 6, 10, 14} quickly reveals that it is not the case. We need only consider the multiplication (2)(6) = 12 to see that the group is not closed under multiplication modulo 16. It may be shown that kU (n) is only a group when gcd(n, k) = 1. To see why this is the case, we return to the first example. Recall that if gcd(n, k) = 1, Znk ∼ = Zn ⊕ Zk . Thus we may write Z40 ∼ = Z8 ⊕ Z5 . As kU (8) is a subset of the MULTIPLICATIVE GROUPS IN Zm 11 ring Znk , we may find the isomorphic subset of Z8 ⊕ Z5 given by the isomorphism φ(x) = (x mod 8, x mod 5). For example, φ(5) = (5 mod 8, 15 mod 5) = (5, 0). Continuing with the other elements, φ(15) = (7, 0), φ(25) = (1, 0), φ(35) = (3, 0). Thus kU (8) ∼ = {(1, 0), (3, 0), (5, 0), (7, 0)}. When presented in this manner, it is easy to see why 5U (8) is a group. When the ordered pairs are multiplied together component-wise, with their respective operations multiplication modulo 8 and multiplication modulo 5, 5U (8) behaves exactly the same as U (8) and is in fact isomorphic to U (8), as the 0 in the second position has no effect on the multiplication. This presents us with a method for finding other splittings of Z40 . If we can construct subsets of Z8 ⊕ Z5 that are groups, they will necessarily be groups when we map the elements back to Z40 . Using this strategy, we create another similar subset, but replace 1 with 0 in the second component. {(1, 1), (3, 1), (5, 1), (7, 1)} Clearly this also will be isomorphic to U (8). If we map these elements back into Z40 , we find that this subgroup corresponds to the set {1, 11, 21, 31}. We now turn our attention to just those subsets of Zkn that when mapped to Zk ⊕ Zn contain all of U (n) in the first component. We define this precisely as follows: Definition 5.1. Let k, n ∈ N with gcd(k, n) = 1. A subset G ⊆ Zn ⊕Zk is said to be splitting if it is a group under multiplication (mod n, mod k) and if π : Zn ⊕Zk → Zn given by π(x, y) = x restricts to a group isomorphism from G to U (n). Thus any splitting of Z8 ⊕ Z5 will have the form {(1, a), (3, b), (5, c), (7, d)} for a, b, c, d ∈ Z5 . If we preserve the first coordinate, such that the some member of the set contains each member of U (8), the set will necessarily be isomorphic to U (8), as the operation is multiplication modulo 8 in that coordinate. There are obviously conditions under which a, b, c, and d may be chosen to ensure it is a splitting. For example, the set {(1, 1), (3, 1), (5, 1), (7, 2)} is not a splitting, as the product ((3, 1)) ((7, 2)) = (5, 2) is not contained in the set. We will show what conditions on the second coordinate entries ensure that we generate a splitting. 6. Commutative Monoid Homomorphisms and Splittings Our objective now is to identify all splittings for any given Zn ⊕ Zk . Generally, a splitting of Zn ⊕ Zk will have the form {(a1 , b1 ), (a2 , b2 ), ..., (ak , bk )} where a1 , ..., ak is an exhaustive list of the elements of U (n), and b1 , ..., bk are elements of Zk that are not necessarily distinct (note that they were all 0’s or 1’s in the previous examples). Given a splitting, consider the function f : U (n) → Zk defined by by f (aj ) = bj . Thus the function assigns to each member of U (n) the corresponding element in Zk as designated by the splitting. Applying this to the first example, {5, 15, 25, 35}, 12 that corresponds to the splitting {(5, 0), (7, 0), (1, 0), (3, 0)}, the function f : U (8) → Zk is defined by f (1) = 0, f (3) = 0, f (5) = 0, f (7) = 0. A function f : A → B is said to be operation preserving if f (a)f (b) = f (ab) for all a in A and b in B. We will show that any f : U (n) → Zk that is defined by a splitting is operation preserving, and conversely, given any operation preserving function f : U (n) → Zk the ordered pairs that define the function correspond to a splitting of Zn ⊕ Zk . Let S(n, k) be the total number of splittings of Zn ⊕ Zk and let Hom(U (n), Zk ) denote the set of operation preserving functions f : U (n) → Zk (More generally Hom(A, B) is the set of operation preserving functions between two sets of elements, A and B, on which a binary operation is defined). Theorem 6.1. S(n, k) = |Hom(U (n), Zk )| Proof. We will first show that any operation preserving function corresponds to a splitting, and then that any splitting corresponds to an operation preserving function. Suppose f : U (n) → Zk is operation preserving. Then the set of ordered pairs H = {(z, f (z)) : z ∈ U (n)} is a subset of Zn ⊕ Zk . Let x, y ∈ U (n). Thus (x, f (x)), (y, f (y)) are elements of H and (x, f (x))(y, f (y )) = (xy, f (x)f (y)) = (xy, f (xy)) ∈ H. Hence H is closed under multiplication. We now need to show that H has an identity and inverses. For x ∈ U (n), the identity and inverse in H are analogous to their U (n) counterparts. For (x, f (x)) ∈ H (1, f (1))(x, f (x)) = (x, f (x)f (1)) = (x, f (x)) (x−1 , f (x−1 ))(x, f (x)) = (1, f (1)) = e Clearly the function π : H → U (n) given by π(x, y) = x is a group isomorphism. Thus H is a splitting. Now consider some splitting H ⊆ Zn ⊕Zk , and let f : U (n) → Zk be the function defined by the set of all ordered pairs of G (formed in the same manner as the first example at the beginning of section 6). Then f maps all of U (n) to a subset of Zk . Let (x, f (x)), (y, f (y)) ∈ G. Because G is a group and closed, (x, f (x))(y, f (y)) = (xy, f (x)f (y)) ∈ H By the definition of the function, the elements (xy, f (x)f (y)) and (xy, f (xy)) are in fact the same element. Hence f (x)f (y) = f (xy). Therefore any splitting G corresponds to an operation preserving function f : U (n) → Zk . So each splitting G of Zn ⊕Zk corresponds to some operation preserving function f : U (n) → Zk and each operation preserving f corresponds to some splitting G. Therefore an exhaustive list of the operation preserving functions f will also yield a list of all the splittings of Zn ⊕ Zk , and |S(n, k)| = |Hom(U (n), Zk )|.  MULTIPLICATIVE GROUPS IN Zm 13 In order to find operation preserving functions it will be necessary to characterize them. Because the set of elements Zk = {0, 1, 2, ..., k − 1} under multiplication modulo k is not always a group, the operation preserving functions are not group homomorphisms. Although Zk is not a group, it satisfies several of the required conditions. Namely the set is closed, it contains an identity element, and it is associative. Furthermore, the operation is commutative. Therefore both it and U (n) satisfy the definition of a commutative monoid. Definition 6.1 (Commutative Monoid (CM)). A commutative monoid is a set that is closed under an associative and commutative operation and has an identity element. With this in mind, we will call an operation preserving function between two commutative monoids a CM-homomorphism and given two CM’s A and B, the set of all CM-homomorphisms from A to B is the set Hom(A, B). The problem now is to find the size of Hom(U (n), Zk ), which will correspond to the number of splittings. Before attempting to count the number of elements in Hom(U (n), Zk ) (and thus, the number of splittings), we will simplify the task by showing that one need only consider n and k that are primes or powers of primes. Our goal in the following section will be to show that if n or k is a not a prime or a power of a prime, Hom(U (n), Zk ) may be broken into smaller parts utilizing the isomorphisms U (n) ∼ = U (s) ⊕ U (t) and Zk ∼ = Z` ⊕ Zj . Commutative Monoid Homomorphisms Given CM’s A and B where A ∼ = A1 ⊕ A2 ⊕ ... ⊕ Am and B ∼ = B1 ⊕ B2 ⊕ .... ⊕ Bn , our objective is to show that |Hom(A, B)| = Πni=1 Πm j=1 |Hom(Aj , Bi )| by which we reduce the problem of finding the number of elements in Hom(U (n), Zk ) to finding the number of elements for only prime power n and k. Given CM’s A1 , A2 , ..., An it is clear that the Cartesian product A1 ⊕ A2 ⊕ ... ⊕ An will also be a CM, if the operation is defined component-wise. If 1Ak is the identity element of Ak then the identity element of the Cartesian product is (1A1 , 1A2 , ..., 1An ) and it is not hard to show it will be closed, commutative, and associative. Now suppose that the sets A, B1 , and B2 are CM’s and there exist functions f : A → B1 and g : A → B2 that are CM-homomorphisms. Define a function h : A → B1 ⊕ B2 by h(a) = (f (a), g(a)) Then for every a1 , a2 ∈ A, h(a1 )h(a2 ) = (f (a1 ), g(a1 ))(f (a2 ), g(a2 )) = (f (a1 a2 ), g(a1 a2 )) = h(a1 a2 ) Thus h is operation preserving, and is a CM-homomorphism from A to B1 ⊕ B2 Conversely, if h : A → B1 ⊕B2 is a CM-homomorphism where h(a) = (f (a), g(a)) then for all a1 , a2 ∈ A (f (a1 ), g(a1 ))(f (a2 ), g(a2 )) = h(a1 )h(a2 ) = h(a1 a2 ) = (f (a1 a2 ), g(a1 a2 )) 14 So f and g are operation preserving, and thus are CM-homomorphisms. Consider the sets Hom(A, B1 ⊕ B2 ) and Hom(A, B1 )× Hom(A, B2 ). Define Φ: Hom(A, B1 ⊕ B2 ) → Hom(A, B1 )× Hom(A, B2 ) such that Φ(h) = (f, g) where h, f and g are the functions defined above such that h(a) = (f (a), g(a)). This is valid, as (f, g) was shown to be a member of Hom(A, B1 )× Hom(A, B2 ). By the same reasoning, Φ will be invertible such that Φ−1 ((f, g)) = h. Therefore there is a one to one correspondence between Hom(A, B1 ⊕ B2 ) and Hom(A, B1 )× Hom(A, B2 ). This may be extended to any number of Bk . If A, B1 , B2 , ..., Bn are commutative monoids, then Hom(A, B1 ⊕ B2 ⊕ ... ⊕ Bn ) = .. . Hom(A, B1 ⊕ ... ⊕ Bn−1 ) × Hom(A, Bn ) = Hom(A, B1 ) × Hom(A, B2 ) × ... × Hom(A, Bn ) We then note that if A × B is a Cartesian product of two sets, |A × B| = |A| · |B|. Then |Hom(A, B1 ⊕ B2 ⊕ · · · ⊕ Bn )| = |Hom(A, B1 )| · |Hom(A, B2 )| · · · |Hom(A, Bn )| We have shown that for a CM-homomorphism f : A → B where B ∼ = B1 ⊕B2 , the elements of the sets Hom(A, B1 ⊕ B2 ) or Hom(A, B1 )× Hom(A, B2 ) are essentially equivalent. An analogous result holds when A ∼ = A1 ⊕ A2 . Suppose that the sets A1 , A2 and B are CM’s and f : A1 → B and g : A2 → B are CM-homomorphisms. We define h : A1 ⊕ A2 → B by h((a1 , a2 )) = f (a1 )g(a2 ). For elements a1 , a3 ∈ A1 , and a2 , a4 ∈ A2 h((a1 , a2 )(a3 , a4 )) = h((a1 a3 , a2 a4 )) = f (a1 a3 )g(a2 a4 ) = f (a1 )f (a3 )g(a2 )g(a4 ) = f (a1 )g(a2 )f (a3 )g(a4 ) = h((a1 , a2 ))h((a3 , a4 )) Therefore h is a CM-homomorphism. Note that in this case it was necessary that the elements of B commute to show the function is operation preserving. Conversely, suppose A1 , A2 , and B are CM’s, and h : A1 ⊕ A2 → B is a CMhomomorphism and define f : A1 → B and g : A2 → B by f (a1 ) = h((a1 , 1A2 )), g(a2 ) = h((1A1 , a2 )). Where 1Ak is the identity element of Ak . Then f (a1 a2 ) = h((a1 a2 , 1A2 )) = h((a1 , 1A2 )(a2 , 1A2 )) = h((a1 , 1A2 ))h((a2 , 1A2 )) = f (a1 )f (a2 ). Hence f is a CM-homomorphism, as well as g (to show g is operation preserving is exactly the same). Consider the sets Hom(A1 ⊕ A2 , B) and Hom(A1 , B)× Hom(A2 , B). For the same reasons Φ: Hom(A, B1 ⊕ B2 ) → Hom(A, B1 )× Hom(A, B2 ) was a one to one correspondence, Π : Hom(A1 ⊕ A2 , B) → Hom(A1 , B)× Hom(A2 , B) will be a one to one correspondence, so that there are the same number of elements in each set. Now returning to the topic of counting splittings. We know that the total number of splittings equals the total number of operation preserving functions from U (n) to Zk so that S(n, k) = |Hom(U (n), Zk )|. By extending the above results, to U (n) and Zk we obtain an important theorem. Theorem 6.2. Suppose n and k have prime factorizations n = pa1 1 pa2 2 · · · par r and b k = q1b1 q2b2 · · · qsbs . Then S(n, k) = Πri=1 Πsj=1 [S(pai i , qj j )] MULTIPLICATIVE GROUPS IN Zm 15 Proof. The sets U (n) and Zk both satisfy the requirements of a CM, so the results regarding CM-homomorphisms hold for them. Suppose that k is not a power of a prime, such that k = j` where (j, `) = 1. Then we know that Zk is isomorphic to Zj ⊕ Z` , so Hom(U (n), Zk ) ∼ = Hom(U (n), Zj ⊕ Z` ), and S(n, k) = |Hom(U (n), Zk )| = |Hom(U (n), Zj ⊕ Z` )| = |Hom(U (n), Zj )||Hom(U (n), Z` )| = S(n, j)S(n, `). And if either j or ` are not a power of a prime, they may be broken down into relatively prime parts by the same process, and so on until each is a power of a prime (and may be decomposed no further). As a result, it is only necessary to consider k that are powers of primes. Suppose alternatively that n = m` where m(, `) = 1. Then U (n) ∼ = U (m) ⊕ U (`) and S(n, k) = |Hom(U (n), Zk )| = |Hom(U (m) ⊕ U (`), Zk )| = |Hom(U (m), Zk )| · |Hom(U (`), Zk )| = S(m, k)S(`, k). Again, if m and ` are not powers of primes, they may be decomposed further to powers of primes, so that we need only consider S(n, k) for which n is a power of a prime.  Example: Symbolically find the number of splittings of Z630 with n = 10, k = 63. S(10, 63) = |Hom(U (10), Z63 )|, = |Hom(U (10), Z9 )| · |Hom(U (10), Z7 )|, = |Hom(U (5), Z9 )| · |Hom(U (2), Z9 )| · |Hom(U (5), Z7 )| · |Hom(U (2), Z7 )|, = S(5, 9) · S(2, 9) · S(5, 7) · S(2, 7). Our task is reduced to finding the number of elements in the set Hom(U (pi ), Zqj ) for primes p and q and positive integers i and k. This task may be simplified further by making some simple observations about properties of CM-homomorphisms. We illustrate this with a theorem preceded by a lemma. Lemma 6.3. Suppose q is a prime and j is a positive integer. If x2 ≡ x mod q j , then x ≡ 1 mod q j or x ≡ 0 mod q j . Proof. If x2 ≡ x mod q j then q j |x(x − 1). Because q is prime, and x and (x − 1) are relatively prime, either q j |x or q j |(x − 1). If q j |x then x ≡ 0 mod q j and if q j |(x − 1) then x ≡ 1 mod q j  Theorem 6.4. If A is an Abelian group then Hom(A, Zqj ) consists of the function which maps all of A to 0 and the set Hom(A, U (q j )), the set of group homomorphisms from A to U (q j ). 16 Proof. Suppose A is an Abelian group (then it is also a CM), q is a prime, and j is a positive integer. If f : A → Zqj is a CM-homomorphism, then f (1A ) = f (12A ) = f (1A )2 and by the previous lemma either f (1A ) = 0 or 1. Let a be an element of A, and suppose f (1A ) = 0. Then f (a) = f (a)f (1A ) = f (a)(0) = 0. As a is an arbitrary element of A, f (a) = 0 for all a ∈ A. Now suppose f (1A ) = 1 and let a be an element of A. We denote the inverse of a in A by a−1 . Then f (a)f (a−1 ) = f (aa−1 ) = f (1A ) ≡ 1 mod q j . We know that the equation ax ≡ 1 mod n has a solution x for integers a and n if and only if gcd(a, n) = 1. Therefore gcd(f (a), q j ) = 1 and by the definition of U -groups f (a) is an element of U (q j ) for all a ∈ A.  This theorem tells us that the set of CM-homomorphisms Hom(U (pi ), Zqj ) consists of the homomorphism that takes every element of U (pi ) to 0, and the set of group homomorphisms from U (pi ) to U (q j ). As we know so much about the structure of U (n), this task of identifying and counting these homomorphisms will be simplified greatly. Suppose that q = 2 and j > 1. Then U (q j ) ∼ = Z2 ⊕ Zqj−2 and we we may write |Hom(U (pi ), U (q j ))| = |Hom(U (pi ), Z2 ⊕Zqj−2 )| = |Hom(U (pi ), Z2 )|·|Hom(U (pi ), Zqj−2 )| If neither p nor q are equal to 2, both U (pi ) and U (q j ) are cyclic. Thus all that remains is to count the total number of group homomorphisms between two cyclic groups and add 1 (for the homomorphism that sends every element to 0) to find the total number of splittings, S(pi , q j ). 7. Counting Group Homomorphisms Between Cyclic Groups Suppose we are given two cyclic groups A and B such that A = hai. We need to find all group homomorphisms between A and B. Recall that a group homomorphism is any mapping f : A → B that preserves the group operations of A and B. Because A and B are cyclic, there are a very limited number of homomorphisms, as the entire mapping is defined by where the generating element, a, is sent. Consider the mapping given by f (a) = x (where a generates A). Because every element of A may be expressed as ai for some positive integer i, we know where every other element of A is mapped as well, by noticing that f (ai ) = f (a)f (a) · · · f (a) = f (a)i = xi . | {z } i With this in mind, we proceed with a lemma and then a theorem. Lemma 7.1. Suppose A and B are cyclic groups where A = hai, and |A| = m. Let x be an element of B with order k. Then a mapping f : A → B given by f (ai ) = xi is a homomorphism if and only if k|m. MULTIPLICATIVE GROUPS IN Zm 17 Proof. First suppose that f is a homomorphism. Recall that if ak = e then the order of a divides k. With this in mind, observe that xm = f (am ) = f (eA ) = eB where eA and eB are the identities of their respective groups. Hence k|m. Now suppose that k|m. It is easy to see that the mapping is operation preserving. For any elements ai and aj in A, f (ai )f (aj ) = xi xj = xi+j = f (ai+j ) = f (ai aj ) It is also important that we ensure the mapping is well-defined. If ai = aj but i 6= j, we must be certain that f (ai ) = f (aj ). For a finite group G, ai = aj if and only if the order of a divides i − j. Then m|(i − j), and since k|m, we also have that k|(i − j). Hence xi = xj , and f (ai ) = f (aj ).  Therefore, in order to find a homomorphism, we must find x ∈ B such that the order of x divides the order of A, and then the appropriate homomorphism will be given by f (ai ) = xi . The lemma tells us that finding every x in B that satisfies this criteria will also yield an exhaustive list of the homomorphisms between A and B. We now examine how many, and precisely which x satisfy this condition. Lemma 7.2. If A and B are cyclic groups with orders m and n, respectively, then there are gcd(m, n) elements of B that have orders that divide m. Proof. We will prove that every member of a particular subgroup of B has an order that divides m, and furthermore, that any element with order that divides m is also a member of the same subgroup, thus showing that the members of the subgroup are precisely the members of B that have orders that divide m. We will denote gcd(m, n) as (m, n). Let b be a generating element of B and consider the subgroup S = hbn/(m,n) i. Let j = n/(m, n)Thus S = {bj , b2j , b3j , ..., b(m,n)j }. Hence S has order (m, n), and by Lagrange’s Theorem, every element of S has an order that divides (m, n), and thus also divides m. Now consider some element x ∈ B with order dividing m. Then the subgroup hxi has an order that divides m. A property of the greatest common divisor of two numbers is that every common divisor divides the greatest common divisor. Hence |x| (m, n). The Fundamental Theorem of Cyclic Groups tells us that for each positive divisor k of m, there is a unique subgroup of order m . Because |x| is a divisor of (m, n), there is a subgroup of S with order |x|. As this is the unique subgroup in B with order |x|, hxi ⊆ S and x ∈ S. Therefore the elements of S are precisely those elements which have orders that divide m, and the size of S is (m, n).  A method for counting the number of homomorphisms from cyclic groups A to B follows easily from these two lemmas. Theorem 7.3. If A = hai and B = hbi are cyclic groups with orders m and n respectively, then there are gcd(m, n) homomorphisms from A to B. 18 Proof. A list of the homomorphisms, denoted by which element a is mapped to is as follows: f1 (a) = bj , f2 (a) = b2j , ..., f(m,n) (a) = b(m,n)j | {z } (m,n)  Corollary 7.4. For cyclic groups A and B there are the same number of homomorphisms from A to B as there are from B to A, that is, Hom(A, B) =Hom(B, A). Proof. From the theorem it easily follows that |Hom(A, B)| = gcd(|A|, |B|) = gcd(|B|, |A|) = |Hom(B, A)|.  8. Conclusion Returning to the topic of splittings, we finally have all the necessary information to determine the number of splittings for a given n and k, S(n, k). We will conclude by retracing the logic outlined in the paper to see exactly how S(n, k) is determined for odd n and k, and then provide two examples. Suppose we are given n, k ∈ N such that n and k are relatively prime. The goal is to find all splittings, S(n, k). Recall that a splitting is a subset of G ⊆ Zn ⊕ Zk that is a group under multiplication ( mod n, mod k) and also has the property that a function π : G → U (n) restricts to a group isomorphism given by π(x, y) = x. It was found that splittings could be also identified by finding all of the operation preserving functions from U (n) to Zk . Next, the development of commutative monoid homomorphisms showed it was only necessary to consider cases where n and k are powers of primes, and furthermore, that the set of operation preserving functions from U (n) to Zk consists of the function that sends all of U (n) to 0, and the set of group homomorphisms from U (n) to U (k). As n and k are powers of primes, this is simplified further to finding the number of group homomorphisms between two cyclic groups. We will expand on this with a theorem and some examples. Theorem 8.1. Let n and k be odd positive integers with (n, k) = 1, and prime factorizations n = pa1 1 pa2 2 · · · par r and k = q1b1 q2b2 · · · qsbs . Then b b −1 S(n, k) = Πri=1 Πsj=1 [1 + gcd(pai − pai i −1 , qj j − qj j )]. b Proof. Utilizing Theorem 6.2, we write S(n, k) = Πri=1 Πsj=1 [S(pai i , qj j )]. Then by b b
b Theorem 6.4, S(pai i , qj j ) = [1+ |Hom U (pai i ), U (qj j ) |]. Both U (pai ) and U (qj j ) are b b −1 cyclic with orders (pai i − pai i −1 ) and (qj j − qj j ), respectively. From the previous section we are able to calculate the number of homomorphisms between cyclic groups. Hence b
b b −1 |Hom U (pai i ), U (qj j ) | = gcd(pai i − pai i −1 , qj j − qj j ) . This completes the proof. MULTIPLICATIVE GROUPS IN Zm 19  To simplify notation, the case where n or k contains a power of 2 was omitted from the theorem. If one of n or k contains a power of 2 (note that because they are relatively prime, only one or the other can be even), we make a slight modification. Recall that U (2m ) is the only case when U (pi ) is not cyclic, and it is isomorphic to Z2 ⊕ Z2m −2 . In the proof of the theorem, if some pi = 2 then the
b
value of |Hom U (pai ), U (qj j ) | would instead be |Hom Z2 ⊕Z2m−2 , Z(qbj −qbj −1 ) | = gcd(2, q bj − q bj −1 )gcd(2m−2 , q bj − q bj −1 ) = 2gcd(2m−2 , q bj − q bj −1 ). In all of the preceding arguments, n and k are interchangeable [fundamentally because gcd(n, k) = gcd(k, n)]. Thus we may switch them to obtain the following corollary. Corollary 8.2. There are the same number of splittings of Zn ⊕ Zk as of Zk ⊕ Zn . That is, S(n, k)=S(k, n). Example 1 - Finding the total number of splittings of Z34 ⊕ Z15 , S(34, 15). We need to find the number of of operation preserving functions from U (34) to Z15 , Hom(U (34), Z15 ). Decomposing to prime power parts, we may write U (34) ∼ = U (17) ⊕ U (2) and Z15 ∼ = Z5 ⊕ Z3 . Hence we need to calculate the product S(17, 5)·S(17, 3·)S(2, 5)·S(2, 3). S(17, 5)·S(17, 3)·S(2, 5)·S(2, 3) = [1+Hom(U (17), U (5))]·[1+Hom(U (17), U (3))]· [1 + Hom(U (2), U (5))] · [1 + Hom(U (2), U (3))] Then as the isomorphism classes of the U-groups are known, the last expression is equal to [1 + |Hom(Z16 , Z4 )|] · [1 + |Hom(Z16 , Z2 )|] · [1 + |Hom(Z1 , Z4 )|] · [1 + |Hom(Z1 , Z2 )|]. Because we know the amount of homomorphisms between cyclic groups, this expression is equal to [1 + (16, 4)] · [1 + (16, 2)] · [1 + (1, 4)] · [1 + (1, 2)] = (5)(3)(2)(2) = 60 Therefore there are a total of 60 splittings. Recall that the first splitting we examined was {(1, 0), (3, 0), (5, 0), (7, 0)} where n = 8 and k = 5. This corresponded to the set {5, 15, 25, 35} ∈ Z40 . We saw that there was also the splitting {(1, 1), (1, 3), (1, 5), (1, 7)} that corresponded to the set {1, 11, 21, 31}. Using the method we have developed, we can systematically discover if there are more than these two splittings. This will be illustrated in the following example. Example 2 - Find the splittings of Z8 ⊕ Z5 and their corresponding sets in Z40 Splittings will correspond to operation preserving functions f : U (8) → Z5 . One of these is the function that sends each element of U (8) to 0, {(1, 0), (3, 0), (5, 0), (7, 0)}. 20 The rest will correspond to group homomorphisms from U (8) → U (5), or equivalently, the group homomorphisms from Z2 ⊕Z2 to Z4 . In Table 3 we define both the isomorphism from Z2 ⊕ Z2 to U (8) and the isomorphism Z4 to U (5) so that after finding the appropriate homomorphisms, we may translate them back into Z8 ⊕ Z5 . Z2 ⊕ Z2 (0,0) (0,1) (1,0) (1,1) U (8) 1 3 5 7 Table 3 Z4 0 1 2 3 U (5) 1 2 4 3 From the discussion of CM-homomorphisms, we know that in order to find the homomorphisms from Z2 ⊕Z2 to Z4 we need to find homomorphisms from Z2 to Z4 . (Recall that for A1 ⊕A2 → B, if f1 : A1 → B and f2 : A2 → B are homomorphisms, then h : A1 ⊕ A2 → B is a homomorphism defined by h(a1 , a2 ) = f (a1 )f (a2 )). To find the homomorphism between two cyclic groups Z2 and Z4 , we follow the procedure outlined in the previous section. Since 1 is the generating element of both, the possible homomorphisms are defined by f1 (1) = 14/(2,4) = 12 = 2 and f2 (1) = 1(2)4/(2,4) = 14 = 0. Thus there will be a total of four possible homomorphisms h from Z2 ⊕ Z2 to Z4 , defined as follows, for (a1 , a2 ) ∈ Z2 ⊕ Z2 : h1 ((a1 , a2 )) = f1 (a1 )f1 (a2 ); h2 ((a1 , a2 )) = f1 (a1 )f2 (a2 ); h3 ((a1 , a2 )) = f2 (a1 )f1 (a2 ); h4 ((a1 , a2 )) = f2 (a1 )f2 (a2 ). Note that h4 is the homomorphism that sends all of Z2 ⊕ Z2 to the identity element ( f2 just sends every element to 0). For the others, we will plug in values to calculate where individual elements are mapped. We will demonstrate the process for finding the mapping h1 : h1 (0, 0) = f1 (0)f1 (0) = 0 + 0 = 0; h1 (0, 1) = f1 (0)f1 (1) = 0 + 2 = 2; h1 (1, 0) = f1 (1)f1 (0) = 2 + 0 = 2; h1 (1, 1) = f1 (1)f1 (1) = 2 + 2 = 0. The others may be found in the same manner. All the homomorphisms are listed in Table 4 (0,0) (0,1) (1,0) (1,1) h1 h2 h3 0 0 0 2 0 2 2 2 0 0 2 2 Table 4 h4 0 0 0 0 MULTIPLICATIVE GROUPS IN Zm 21 Now that we have the homomorphisms from Z2 ⊕ Z2 to Z4 we may map them back to U (8) and U (5) using Table 3 to find the splittings. The following splittings are listed as they corresponded to the homomorphisms. h1 → {(1, 1), (3, 4), (5, 4), (7, 1)}; h2 → {(1, 1), (3, 1), (5, 4), (7, 4)}; h3 → {(1, 1), (3, 4), (5, 1), (7, 4)}; h4 → {(1, 1), (3, 1), (5, 1), (7, 1)}. These four plus the original splitting {(1, 0), (3, 0), (5, 0), (7, 0)} are the five total splittings. Each member of the splittings exist in Z8 ⊕ Z5 . To finish, we utilize the isomorphism from Z8 ⊕ Z5 to Z40 to find the splittings that these correspond to. h1 → {1, 19, 29, 31}; h2 → {1, 11, 29, 39}; h3 → {1, 19, 21, 39}; h4 → {1, 11, 21, 31}. Using the splitting corresponding to h3 , we demonstrate with a Cayley table that this is in fact a group under the operation multiplication mod40. 1 19 29 31 1 1 19 29 31 19 19 1 31 29 29 29 31 1 19 31 31 29 19 1 References (1) Gallian, Joseph A. Contemporary Abstract Algebra: Fourth Edition. Boston, MA: Houghton Mifflin Co., 1998. (2) ”Least Common Multiple.” . Planet Math.