For any prime p, the set of residues (excluding 0) modulo p form a group of order p-1 under multiplication. For example, with p = 5 we have the group of order 4: 1 2 3 4 1 1 2 3 4 2 2 4 1 3 3 3 1 4 2 4 4 3 2 1 Of course, we can also construct a group of order p-1 using the residues modulo p-1 and the operation of addition. For example, with p = 5 we have the additive group modulo 4: 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2 Notice that there are isomorphisms between this group and the previous multiplicative group. One isomorphism is the mapping Additive Multiplicative Group Group 0 1 3 2 1 3 2 4 This leads us to write the additive group (mod 4) in the form 0 3 1 2 0 0 3 1 2 3 3 2 0 1 1 1 0 2 3 2 2 1 3 0 In general it is always the case that there is an isomorphism (usually several) between the multiplicative group of non-zero residues modulo p and the additive group of residues modulo p-1. Now, suppose we take each element of the multiplicative group and interatively apply the exponentiation x -> x^k for some fixed k. We will find that this leads to a set of closed cycles of various lengths, and each residue belongs to exactly one of these cycles. Thus we can say that exponentiation induces a partition of the non-zero elements of Z_p into sub-sets. The isomorphism with the additive group of order p-1 enables us to analyze this partition. Notice that, in the multiplicative group, the operation x -> x^k can be performed by starting with the identity element (i.e., 1) and multiplying by x a total of k times. In the isomorphic additive group this corresponds to starting with the identity element (i.e., 0) and adding the number y that maps to x a total of k times. Thus the exponentiation x -> x^k (mod p) maps to the multiplication y -> ky (mod p-1). Clearly if k is not coprime to p-1, the cycles induced by this operation will not be a complete partition of the group, because if k has a common factor with p-1, there is no exponent j such that k^j = 1 (mod p-1), and hence for some y the eventual cycle given by y k^j does not include y. Therefore, if we are considering only complete partitions, we can limit ourselves to exponents (multiplicands) k coprime to p-1. On this basis, the length of the cycle containing the element y is the least integer j such that y = y k^j (mod p-1). Since k is coprime to p-1, we know there is a number ord(k) such that k^ord(k) equals 1 modulo p-1, so the cycle length cannot exceed this, and in fact it must be a divisor of ord(k). In general we know that k^phi(n) = 1 (mod n) where phi() is the Euler totient function. Also, since n = p-1 is even and k is odd, this can be strengthened to k^phi(n/2) = 1 (mod n). Hence every cycle length for the exponent (multiplicand) k must be a divisor of phi((p-1)/2). It's possible for the cycle length to be less than phi((p-1)/2) because, since p-1 is not prime, there can exist a number q other than 1 such that qy = y (mod p-1). For example, (3)(2) = 2 (mod 4). Hence for each exponent (multiplicand) k, the elements wil fall into cycles of various lengths. For example, with p=109 and k=43 we have the exponentiation 6-cycle [2,19,17,107,90,92,2,...] and the 18-cycle [11,37,91,70,67,44,59,30,62,98,72,18,39,42,65,50,79,47,11,...] and twenty other cycles. In all, the non-zero elements of Z_109 split under the action of x -> x^43 into 21 disjoint cycles, each of length 1, 2, 3, 6, 9, or 18. Letting m[n] signify m different cycles of length n, the exponential partition of the 108 non-zero elements of Z_109 induced by the exponent k=43 has the form 6[1] + 3[2] + 4[3] + 2[6] + 4[9] + 2[18] = 108 Although every cycle length must be a divisor of phi((p-1)/2), not every such divisor necessarily occurs as a cycle length. For example, the length of an exponentiation cycle in Z_113 must be a divisor of phi(112/2) = 24, so we COULD have cycles of length [1], [2], [3], [4], [6], [8], [12], or [24], but in fact Z_113 splits under x -> x^43 entirely into cycles of lengths [1], [2], or [4] as follows 14[1] + 21[2] + 14[4] = 112 On the other hand, taking the exponent 11 instead of 43, we find that the mapping x -> x^11 splits Z_113 as 2[1] + 3[2] + 4[3] + 2[4] + 6[6] + 4[12] = 112 Checking each of the 48 possible exponents, the exponential partitions of Z_113 can be summarized as shown in the table below: partition exponent (mod 113) [1] [2] [3] [4] [6] [12] ------------------ --- --- --- --- --- --- 1 113 0 0 0 0 0 3,19,59,75 3 3 0 2 8 4 5,45,61,101 5 2 0 2 8 4 9,25 9 4 16 0 8 0 11,51,67,107 3 3 4 2 6 4 13,69 5 26 0 14 0 0 15 and 71 15 49 0 0 0 0 17,33 17 0 0 0 16 0 23,39 and 79,95 3 7 4 0 14 0 27,83 3 27 0 14 0 0 29,85 29 14 0 14 0 0 31,47 and 87,103 3 7 0 0 16 0 37,53,93,109 5 2 8 2 4 4 41 9 52 0 0 0 0 43,99 15 21 0 14 0 0 55 and 111 3 55 0 0 0 0 57 57 28 0 0 0 0 65,81 17 0 32 0 0 0 73,89 9 4 0 0 16 0 97 17 48 0 0 0 0 In each case, the exponent(s) that generate a given partition are of the form g, g^5, g^7, and g^11, all taken modulo phi(p). For example, the exponents 11,51,67,107 are related by g = 11 g^5 = 107 g^7 = 67 g^11 = 51 (mod 112) The powers 1,5,7,11 are the four numbers less than and coprime to 12, which is the maximum cycle length for any exponential cycle in Z_113. On the other hand, the exponent 57 occurs by itself, because 57 = 57^5 = 57^7 = 57^11 (mod 112) There are 20 distinct partition structures in the above table, but four of the entries (those with an "and" conjunction) actually represent two different partitions with respect to which elements of Z_p are contained in the various segments. For example, one of the 6-cycles with exponent 31 is {3,47,92,38,101,43,3,...} whereas the corresponding cycle with exponent 87 is {3,-47,92,-38,101,-43,3,...}, so they are equivalent only up to sign. Thus, there are really 24 distinct exponential partitions of Z_113 (not considering the order of the elements in each cycle.) Clearly if n induces a certain partition, and if mn = 1 (mod 112), then m induces the same partition (with the terms appearing in reverse order). This accounts for the inverse pairs of exponents, and also explains the singular exponents 1, 41, 57, 97, which are their own inverses modulo 112. Also, if 2mn = 2 (mod 112) then m may induce a partition that is equivalent up to sign, with the alternate terms negated. For example, we have (23)(39) = 1 (mod 112) (79)(95) = 1 (mod 112) 2(23)(95) = 2 (mod 112) 2(39)(79) = 2 (mod 112) and the exponential sequences x -> x^e with these four exponents and initial value x=3 are e exponentiation sequence --- ------------------------------ 23 3 39 101 59 92 103 3 ... 39 3 103 92 59 101 39 3 ... 79 3 74 101 54 92 10 3 ... 95 3 10 92 54 101 74 3 ... I suspect that, in general, the number of distinct exponential partitions of Z_p is always Q = phi(phi(p)/2), and that the exponents are themselves partitioned according to powers coprime to the maximum cycle length. To determine the maximum cycle length, which we know is a divisor of phi((p-1)/2), we can consider the sequences reduced modulo the various divisors of p-1. For example, 112 = (7)(16), and we know the cycle in Z_7 has a max period of phi(7)=6, whereas the max period in Z_16 is just phi(16/4) = 4. (We can strenghten the basic Fermat congruence k^phi(n)=1 (mod d) by a factor of 4 when n is multiply even and the base is odd, as in the present case, by the same argument that we used to strengthen it by a factor of 2 when n is simply even.) Hence the overall cycle length can be no greater than the least common multiple of 6 and 4, which is 12.

Return to MathPages Main Menu