Find all n such that $\phi(\phi(n)) = 1$

Question

Find all n such that $\phi(\phi(n)) = 1$. I was thinking of firstly writing $\phi(n) = n\prod_{p|n} {1-1/p}$ and then again but I couldn't find a result.

Answer 1

We want $\varphi(\varphi(n))=1$. First we find all the candidates for $\varphi(n)$. So we find all $k$ such that $\varphi(k)=1$.

The obvious candidates are $k=1$ and $k=2$. There are no others. For if $k\ge 3$, then $1$ and $k-1$ are relatively prime to $k$, and distinct modulo $k$.

So we want $\varphi(n)=1$ or $\varphi(n)=2$. We have already seen that the only $n$ for which $\varphi(n)=1$ are $n=1$ and $n=2$.

Now we look for the $n$ such that $\varphi(n)=2$. The obvious ones are $3$, $4$, and $6$. We will show there are no others.

Let $\varphi(n)=2$. If $n$ is prime, we must have $n=3$. Now let $n$ be composite. If $n\gt 3$ is odd composite, let $n=ab$ where $a$ and $b$ are relatively prime and $\gt 1$. Then $\varphi(a)\ge 2$ and $\varphi(b)\ge 2$, so $\varphi(ab)\ge 4$.

Now let $n$ be even, and let $2^t$ be the highest power of $2$ that divides $n$. Let $n=2^t m$. Note that $m$ is odd.

If $t=1$, then $\varphi(n)=\varphi(m)$. Since $m$ is odd, by the previous argument we find that $\varphi(m)\ge 4$ if $m\gt 3$.

Finally, suppose that $t\ge 2$. We have $\varphi(2^t)\ge 2$, and so if $m\ge 3$ then $\varphi(n)\ge 4$.

Conclusion: The only $n$ such that $\varphi(\varphi(n))=1$ are $1,2,3,4,6$.

Answer 2

Let $k=\varphi(n)$. Then the equation becomes $\varphi(k)=1$. This implies that $k=1$ or $k=2$.

If $k=1$, then $\varphi(n)=1$ which gives $\color\red{n=1}$ or $\color\red{n=2}$.

If $k=2$, then $\varphi(n)=2$. Let $p\mid n$ where $p$ is a prime divisor of $n$. Then $\varphi(p)\mid \varphi(n)$ that is $p-1\mid 2$. So $p$ is either $2$ or $3$. It follows that $n$ is of the form $2^\alpha \times 3^\beta$. From $\varphi(n)=2$, and knowing that $2^\alpha$ and $3^\beta$ are coprime and $\varphi$ is multiplicative, we obtain $$\varphi(2^\alpha\times3^\beta)=\varphi(2^\alpha)\times \varphi(3^\beta)=2^\alpha\times 3^{\beta -1}=2$$ If $\beta =0$, then $\varphi(2^\alpha)=2$ or $2^{\alpha -1}=2$ which gives us $\alpha =2$ and hence $\color\red{n=4}$.

If $\alpha =0$, then $\varphi(3^\beta)=2$ or $3^{\beta -1}\times 2 =2$. This implies that $\beta =1$ or $\color\red{n=3}$.

If both are nonzero, since $$2^\alpha\times 3^{\beta -1}=2$$ then $\alpha =1$ and $\beta =1$ which gives $\color\red{n=6}$.