# $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?

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 $$$$2^k \le m \le 3^k \qquad(*)$$$$ 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.

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}$$.