$1 = \phi(\phi(\cdots\phi(n)\cdots))$, where Euler's totient is applied $k$ times, then $n\leq 3^k$

Suppose that $n$ and $k$ are positive integers such that $1 = \phi(\phi(\cdots\phi(n)\cdots))$, where the Euler's totient function is repeated $k$ times. Prove that $n \leq 3^k$.

My work so far: I'm thinking of doing induction. If $\phi$ is only done once, then $n$ must be $1$ or $2$ since those are the only values when $\phi (n) = 1$. I'm not sure how to continue this induction proof, and should I also attempt a proof of contradiction?

Solution 1:

I think the following approach makes the result very intuitive.

You can define a new function $c(m)$, the number of "2" needed to construct the number $m$, in the following way: if you write $m$ as a product of primes and in every step you change every odd prime $p$ to $p-1$ in the factorization of what is left and continue this way until you get a power of 2, $2^k$ then define $c(m)=k$.

For example $c(2^k)= k$, for 3 we get $2^1$ so $c(3)=1$, for 7 we get $7 \to 2\cdot 3 \to 2^2 $ so $c(7) = 2$ for 15 we get $$ 15=3\cdot 5 \to 2 \cdot 4 = 2^3 $$ so $c(15) = 3$, for $m=67$ you get $$ 67 \to 2\cdot 3 \cdot 11 \to \cdot 2^3 5 \to 2^5 $$ so $c(67) = 5$, and so on.

It is immediate from the definition that $$ c(1) = 0\quad c(2^k)=c(3^k) = k $$ and that $$ c(nm) = c(n)+c(m) $$ and so the function is completely additive.

Now it is very easy to prove that if $c(m) = k$ then \begin{equation} 2^k \le m \le 3^k \qquad(*)\end{equation} Again you can proceed recursively observing that $2^k < 3^k$, $2^k \le 2^k+1 \le 3^k$ and that if $2^k \le n \le 3^k$ then $$ 2^{k+s} \le 2^s n + 1 \le 3^{k+s} $$ and then apply this backwards to the above procedure to find $c(m)$.

Now the link with your problem is that (directly from the formula for $\phi(n)$)
$$c(\phi(m)) = \begin{cases} c(m)\quad&\text{if $m$ is odd}\\ c(m)-1 &\text{if $m$ is even}\end{cases} $$

But if $m>2$ then $\phi(m)$ is always even so you can see that $$c(\phi(\phi(\overset{(k}\dots \phi(m)\dots ))) = \begin{cases} c(m)-k+1\quad&\text{if $m$ is odd}\\ c(m)-k &\text{if $m$ is even}\end{cases}$$

And from this it follows that the least number of applications of $\phi$ to arrive from a number $m$ to 1 is : $$ k = \begin{cases} c(m)+1\quad&\text{if $m$ is odd}\\ c(m) &\text{if $m$ is even}\end{cases}$$ And combining this with (*) you get your problem.

Solution 2:

Let $n= 2^e \cdot p_1^{e_1}\cdots p_s^{e_s}$ be the prime factorization of $n$, with $p_i$ odd primes. We adopt the notation $\varphi_k(n)$, meaning that we apply the Euler totient function to $n$, recusively $k$ times. We also define $a(n)$ to be the smallest integer $k$, s.t. $\varphi_k(n)=1$. In other words, $a(n)$ tells us how many times we need to apply $\varphi$ to reduce $1$ to $k$.

I claim that $a(n) = e_1(a(p_1)-1) + \cdots + e_s(a(p_s)-1) + \max\{1,\nu_2(n)\}$, where $\nu_2(n)$ stands for the highest power of $2$ that divides $n$. In particular, by above we have $\nu_2(n) = e$. I don't really have a rigorous proof of this, but it is closely related with how many $2$'s are produced while reducing $n$ to $1$ by applying $\varphi$ repeatedly. What I mean under this is I think better illustrated in an example. We have $\varphi(7)=6 = 2 \cdot 3$, so that is one power of $2$ produced. Then $\varphi(2 \cdot 3) = 2$, so another power of $2$ produced (note that we produced a "new" power of $2$, coming from $3$, while we killed the other one). It shouldn't be very hard to see that $a(n)$ is the number of $2$'s produced plus $\max\{\nu_2(n),1\}$. Indeed, as the only odd value that $\varphi$ assumes is $1$ we get that we'll be done reducing $n$ to $1$ once we kill all the powers of $2$. However, at each step (except at the first one if $n$ is odd, in which case we don't kill any) we kill exactly one power of $2$. Using the multiplicativity of $\varphi$ and counting the number of $2$ produced in the reduction of $n$ we get the formula above.

We'll now show that $a(p) \ge 1 + \log_3(p)$ for odd primes. Clearly the formula holds for $p=3$. Now suppose that $p$ is an odd prime s.t. $2^k \le p < 2^{k+1}$ for some $k \ge 2$. Moreover, suppose that the claim is true for all prime numbers less than $2^k$. As $\varphi(p) = p-1$ we have that $a(p) = 1 + a(p-1)$. $p-1$ is an even integer and we have $p-1 = 2^e \cdot p_1^{e_1}\cdots p_s^{e_s}$, which each $p_i$ is an odd prime less than $2^k$. Then by the formula:

$$a(p) = 1 + a(p-1) = 1 + e_1(a(p_1)-1)+ \cdots +e_s(a(p_s)-1) + e$$ $$\ge 1 + \log_3(p_1^{e_1} \cdots p_s^{e_s}) + \log_3(3^e)$$ $$\ge 1 + \log_3\left(3^e \cdot \frac{p-1}{2^e}\right)$$ $$ \ge 1 + \log_3(p)$$

where we made use of the fact that $e \ge 1$. Thus, the claim is true for odd primes.

Finally, we prove that $a(n) > \log_3(n)$. If $n$ is odd, then

$$a(n) = e_1(a(p_1)-1) + \cdots + e_s(a(p_s)-1) + 1 \ge \log_3(p_1^{e_1}\cdots p_s^{e_s}) + 1 = 1 + \log_3(n) > \log_3(n)$$

If $n$ is even, we have:

$$a(n) = e_1(a(p_1)-1) + \cdots + e_s(a(p_s)-1) + e \ge \log_3\left(3^e \cdot \frac{n}{2^e}\right) > \log_3(n)$$

At the end, suppose that $\varphi_k(n) = 1$. This means $k \ge a(n) > \log_3(n)$. Exponentiating both sides we get $n < 3^k$

In general, if $\varphi_k(n) = 1$, then $n$ is "much smaller" than $3^k$. As seen above we almost always we have that $n < 3^{k-1}$. If I'm not mistaken the only exceptions are the numbers of the form $2\cdot 3^{k-1}$ and $3^{k-1}$.