|
Primitive Roots and Exponential Iterations |
|
|
|
For any positive co-prime integers m and r we can consider the sequence of powers r1, r2, r3, … modulo m. Since rϕ(m) = 1 (mod m), the fundamental period of this sequence is a divisor of ϕ(m). To illustrate, consider the case m = 5. The powers of each residue r from 0 to 4 (mod 5) are shown in the table below. |
|
|
|
|
|
|
|
For convenience we have defined 00 = 0 (mod m). The periods of the rows are 1, 1, 4, 4, and 2 respectively, confirming that each period is a divisor of ϕ(5) = 4. A primitive root modulo an integer m is a residue r such that the powers r1, r2, r3, …, rϕ(m) constitute a reduced residue set modulo m, meaning that they represent all the ϕ(m) numbers less than and co-prime to m. From the above table we see that the primitive roots modulo 5 are just 2 and 3. |
|
|
|
Since every primitive root is coprime to m, it follows that given any one primitive root r, all the others must be in the set r1, r2, r3, …, rϕ(m). However, some of the residues in this set may not be primitive roots, because their exponents may be divisors of ϕ(m). In the above example, the powers of the primitive root 2 include 3 (which is the other primitive root), but they also include 4 (which is not a primitive root). Thus with r = 2 we see that the primitive roots are 21 and 23, but not 22 or 24. This stands to reason, because if the exponent s is a divisor of ϕ(m) it’s clear that the powers of rs will not form a complete residue set (mod m), so rs cannot be a primitive root. Conversely, if s is coprime to m, and assuming r is a primitive root modulo m, it follows that the powers of rs do constitute a complete residue set, so rs is a primitive root. |
|
|
|
For example, if ϕ(m) = 12 and if r is a primitive root modulo m, then clearly r1, r5, r7, and r11 are primitive roots, and these are the only primitive roots, because the exponents of the other powers are divisors of 12, so they will not give complete reduced residue sets. Thus, if there is a primitive root modulo m, there are exactly ϕ(ϕ(m)) primitive roots modulo m. It also follows that no square (i.e., quadratic residue) can be a primitive root modulo any integer m greater than 2, because ϕ(m) is even for all m greater than 2. In addition, the residue -1 cannot be a primitive root, because its powers are just ±1. |
|
|
|
Now consider a simple exponential recurrence of the form xi+1
= xin (mod m) where n is a positive integer. Beginning
with some initial value x0 = r this recurrence generates the
values |
|
|
|
|
|
|
|
In this figure the shaded residues are those that continue to be occupied indefinitely under the action of the mapping. Obviously the mappings for n = 0, n = 1, and n = ϕ(m) will always be of the forms shown here, so the only non-trivial mappings are those given by the other values of n, which in this case are n = 2 and n = 3. We note that n = 3 contains the only non-degenerate cycle of iterates, oscillating between 2 and 3. It’s also worth noting that the exponents n = 1 and n = 3 are the only two cases for which all the residue classes remain filled under the action of the mapping. |
|
|
|
For larger values of m there are a variety of different tree and cycle structures represented by the mappings for different exponents. To illustrate, the figure below depicts the exponential iteration mapping with m = 19 for the exponent n = 2. |
|
|
|
|
|
|
|
It’s worth noting that if we populate the states uniformly at the start, and then apply the mapping in step-wise fashion, the states not only become non-uniformly populated, they can also have populations that oscillate. For example, after the first iteration the populations of the six states 16, 9, 5, 6, 17, 4 in the hexagonal cycle are 3, 2, 2, 1, 2, 2 respectively, and thereafter this distribution wave propagates around the hexagon. On the other hand, the population of state 0 is constantly 1, and the populations of states 1 7, and 11 are constantly 2. (States 7 and 11 exchange one element on each iteration, but the elements are assumed to be indistinguishable, so the result is essentially a constant population.) |
|
|
|
For another example, consider the case m = 23 with the exponent n = 2, which gives the exponential iteration mapping depicted below. |
|
|
|
|
|
|
|
This shows a single cycle of length 10, each element of which is fed by one “external” element, as well as by the preceding element in the cycle. (Note that the two elements feeding into any of the cyclic elements are complementary. For example, the two elements feeding into 16 are 4 and 19, and we have 4 + 19 = 23.) With n = 5 the residue classes split into four distinct cycles of length 5 as shown below. |
|
|
|
|
|
|
|
In this case all the residue classes remain uniformly populated. For the exponent n = 7 we get two complete exponential iteration cycles of length 10, as shown below. |
|
|
|
|
|
|
|
The two large cycles are just the negatives of each other, since the first cycle consists of the values 2, 13, 9, 4, … etc., and the second cycle consists of the values -2, -13, -9, -4, and so on. Thus, with m = 23 and n = 7, we see that for any initial value r other than 0, or ±1 (mod m), the exponential iterations cover all the non-zero and non-unit residues up to sign. The same is actually true for the iteration with exponent n = 2, the only difference being that in that case the initial value may not be in the ultimate cycle. |
|
|
|
Definition: For any given m, the integer n is called a primitive exponent if, beginning with any residue other than 0 and ±1, iterations of the function x → xn (mod m) cover all the non-zero and non-unit residue classes up to sign. |
|
|
|
Proposition 1: The positive integer n is a primitive exponent modulo m if and only if both m and (m–1)/2 are primes and n is a primitive root modulo (m–1)/2. |
|
|
|
Proposition 2: If m and (m–1)/2 are primes, then the number of distinct primitive exponents modulo (m–1)/2 is ϕ(ϕ(ϕ(m))) where ϕ(x) denotes the Euler totient function. |
|
|
|
Incidentally, a prime q such that 2q+1 is also a prime is known as a “Germain prime”. These were first studied by Sophie Germain in relation to the "first case" of Fermat’s Last Theorem. From Proposition 1 we see that every primitive exponential mapping corresponds to a Germain prime. Empirically such primes are fairly common, but it has never been proven that there are infinitely many such primes. |
|
|
|
Reviewing the previous example, Proposition 1 implies that there is no primitive exponential mapping modulo 19, nor is there one modulo 17 or 13, but there are such mappings modulo m = 11, 7, and 5, because in each case the integer (m – 1)/2 is also a prime, and there exist primitive roots modulo these Germain primes. For example, with m = 5 we have (m – 1)/2 = 2, which is a prime with the primitive root 1. Hence the residues 1 and 3 modulo 5 are both primitive roots modulo 2, and indeed we see that with n = 1 the residues 2 and 3 comprise negative cycles, and with n = 3 the residues 2 and 3 are in a single cycle. |
|
|
|
With m = 23 the primitive exponents (according to Proposition 1) should be the primitive roots modulo (23 – 1)/2 = 11. There are precisely four such values, namely, 2, 6, 7, and 8. We’ve already seen that 2 and 7 are indeed primitive exponents (mod 23), and it’s easy to show that 6 and 8 are also primitive exponents. With n = 6 the iteration cycle is the reverse of the cycle for n = 2, whereas with n = 8 it is the reverse of the first cycle for n = 7. Only the odd primitive root, 7, leads to two self-contained cycles. The other three (2, 6, and 8) lead to a single cycle with each element being fed by external elements. |
|
|
|
The maximum number of primitive exponents for a given m occurs when m and (m–1)/2 are both prime and the latter has the maximum possible number of primitive roots. Letting q denote (m–1)/2, we will have the maximum number of primitive roots modulo q (and therefore the maximum number of primitive exponents modulo m) if (q–1)/2 is also a prime. Under these conditions the number of primitive roots is |
|
|
|
|
|
|
|
In such a case, all the residues modulo q other than the squares and -1 are primitive roots. |
|
|
|
For example, with m = 23 we have (23–1)/2 = 11, which is a prime, so the primitive exponents modulo 23 are the primitive roots modulo 11. There are ϕ(ϕ(11)) = 4 of these, corresponding to the number of integers less than and coprime to ϕ(11) = 10. (This is the maximum possible, because (11–1)/2 = 5 is also a prime.) Given any one of the primitive roots modulo 11, the others can be generated by an exponential iteration with an exponent equal to any of the four integers less than and coprime to 10. These are the integers 3, 7, and 9. Taking n = 3, the exponential mapping modulo 11 is shown below. |
|
|
|
|
|
|
|
From this it follows that the primitive exponents modulo 23 are 2, 6, 7, and 8. In this case we only needed to know one primitive root modulo 11 (and a number coprime to 10), because the others could then be generated by exponential iteration. However, this gives an unambiguous result only in cases when m, (m–1)/2, and (m–3)/4 are all primes. In other words, we have three primes w, q, p such that q = 2w + 1 and p = 2q + 1. Sequences of primes where each prime is one greater than twice the previous one are called Cunningham chains. |
|
|
|
As an aside, it’s not known if there are infinitely many Cunningham chains of length 2 (i.e., Germain primes), let alone of length three. Hence it is not known if there are Cunningham chains of arbitrarily great length, although empirically it is possible to find fairly long chains. The first Cunningham chain of length five is 2, 5, 11, 23, 47. The first chain of length 6 is 89, 179, 359, 719, 1439, 2879. The first chain of length 7 begins with the prime 1122659, and the first chain of length 8 begins with the prime 19099919. Gunter Loh found a chain of length 13 beginning with the prime 758083947856951. |
|
|
|
If both m and (m–1)/2 are primes, but (m–3)/4 is not a prime, we can still proceed as before, except that it is slightly more difficult to determine the primitive exponents. Suppose we wish to determine the primitive exponents modulo m = 263. Since this is a prime, and since (m – 1)/2 = 131 is also a prime, we know primitive exponents modulo 263 exist, and they are the primitive roots modulo 131. Also, by Proposition 2, there are ϕ(ϕ(ϕ(263))) = 48 of these roots. Also, since 3 is coprime to 130, we know that exponential cubing gives cycles of primitive roots. We also know that no square residue is a primitive root, so we can exclude all squares, as well as the residue –1 (regardless of whether it is a square). However, since (131–1)/2 = 65 is not a prime, we cannot conclude that all the non-square and non-unit residues are primitive roots. Evaluating the iterates of x → x3 (mod 131) for non-square residues, we find the following cycles. |
|
|
|
2 8 119 106 95 111 122 57 90 116 31 54 |
|
6 85 128 104 98 88 10 83 103 56 76 126 |
|
14 124 50 26 22 37 87 97 127 67 118 30 |
|
17 66 82 120 110 40 72 29 23 115 96 93 |
|
18 68 32 |
|
19 47 71 |
|
24 69 92 |
|
42 73 78 70 |
|
51 79 86 |
|
130 |
|
|
|
Clearly the 48 primitive roots modulo 131 are given by the residues in the four cycles of length 12, so the remaining 17 residues, appearing in cycles of lengths 3, 4, and 1, are neither squares nor primitive roots. |
|
|
