Exponential Partitions
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