I was reading something this afternoon and ran across φ(φ(*m*)) and thought that was unusual. I often run across φ(*m*), the number of positive integers less than *m* and relative prime to *m*, but don’t often see Euler’s phi function iterated.

## Application of φ∘φ

This section will give an example of a theorem where φ(φ(*m*)) comes up.

First of all, Euler’s theorem says that given an integer *m* > 1 and an integer *g* relatively prime to *m*, then

*g*^{φ(m)} = 1 (mod *m*).

Now Euler’s theorem gives a value of *t* such that *g*^{t} = 1 (mod *m*). It doesn’t say this is the smallest *t*, only that it’s a possible value of *t*. If φ(*m*) *is* the smallest such value of *t*, then *g* is called a **primitive root mod m. **

For example, let *m* = 10. Then φ(10) = 4, and so a primitive root mod 10 is a number *g* such that *g*^{4} = 1 mod 10, but *g*^{t} is not congruent to 1 mod 10 for *t* = 1, 2, or 3. Now 3 is a primitive root mod 10 because 3^{4} ends in 1, but 3, 3², and 3³ do not end in 1.

There are no primitive roots mod 12. A primitive root mod *m* has to be relatively prime to *m* [1], and so there are only four candidates: 1, 5, 7, and 11. Each of these is congruent to 1 mod 12 when squared, so for none of them is 4 = φ(12) the smallest exponent that gives a number congruent to 1.

Now we’re ready to state our theorem, Theorem 2.34 from The Joy of Factoring by Samuel Wagstaff, Jr.

An integer *m* > 1 has a primitive root if and only if *m* = 2, *m* = 4, *m* = *p*^{e} , or *m* = 2*p*^{e}, where *p* is an odd prime and *e* is a positive integer. If m has a primitive root, then it has exactly φ(φ(*m*)) of them in 1 ≤ *g* ≤ *m*.

This theorem could have told us that 10 has primitive roots and 12 doesn’t, and it could tell us that 10 has exactly φ(φ(*m*)) = 2 primitive roots. We found one of them, 3, and the other is 7.

## Higher iterates

Let φ_{1}(*n*) = φ(*n*) and φ_{2}(*n*) = φ(φ(*n*)). In general, let φ_{k} be the function defined by iterating the *phi* function *k* times. If we apply φ to any integer enough times, we’ll get 1. For each *n*, let *k*(*n*) be the smallest value of *k* such that φ_{k}(*n*) = 1. Then Erdős *et al* proved that *k*(*n*) is between log(*n*)/log(3) and log(*n*)/log(2).

To illustrate this, let *n* = 20220630. The theorem above predicts we’ll have to apply φ between 16 and 25 times before we get to 1. The following code shows *k*(*n*) = 21.

from sympy import totient n = 20220630 k = 0 while n > 1: n = totient(n) k += 1 print(k)

Note that “totient” is another name for Euler’s φ function.

## Related posts

[1] If *g* shares a factor bigger than 1 with *m*, then so does every positive power of *g*, and so no power of *g* is congruent to 1 mod *m*. In particular, *g*^{φ(m)} cannot be 1.