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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.