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^2, and 3^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 Erds 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.

The post Phi Phi first appeared on John D. Cook.