Phi Phi

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⁴ = 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⁴ 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 = 2p^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 φ₁(n) = φ(n) and φ₂(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

• Three applications of Euler’s theorem
• Smith’s determinant

[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.