Find all positive integers $n$ for wich $\phi(\phi (n))$ divides $n$.
Problem
Source: Philippine Mathematical Olympiad P8
Tags: number theory
20.02.2024 09:34
case bash :/ $n=1,3,2^a.3^b,2^a.5,2^a.7$ where $b$ is nonnegative integer and $a$ is a positive integer.
20.02.2024 13:10
First of all, since we can remove factors of $p$ from both terms if $p^3 \mid n$, we may w.l.o.g. assume that $n$ is cubefree (and then later add arbitrary powers of those primes dividing $n$ twice). Next, note that if $n$ has $k$ odd prime factors, then $2^k \mid \varphi(n)$ and hence $2^{k-1} \mid \varphi(\varphi(n))$ so that $k \le 3$. But if $k=3$, then in fact $4 \mid n$, and hence $2^4 \mid \varphi(n)$ and then $2^3 \mid \varphi(\varphi(n))$, contradiction. Hence $k \le 2$. If $k=2$, we get that $2 \mid n$. If $4 \mid n$, then $\frac{n}{2}$ is still a solution, so w.l.o.g. $n=2p^aq^b$ with $p,q$ odd and $a,b \in \{1,2\}$. Then $\varphi(n)=(p-1)(q-1)p^{a-1}q^{b-1}=4m$ is divisible by $4$. But then $\varphi(\varphi(n))=\varphi(4m)=2\varphi(2m)$ will be divisible by $4$ unless $\varphi(2m)$ is odd i.e. $m=1$. But then $(p-1)(q-1) \le 4$ which is absurd. If $k=1$, again we get that if $4 \mid n$, then also $\frac{n}{2}$ is a solution, so we are left with the cases $n \in \{p,2p,p^2,2p^2\}$. In the first two cases we have $\varphi(n)=p-1$, so $\varphi(p-1) \mid 2p$. But clearly it is smaller than and hence coprime to $p$, hence $\varphi(p-1) \mid 2$. But this is easily checked to be only possible for $p \in \{3,5,7\}$. Hence we get the solutions $n \in \{3,6,10,14\}$ and more generally $n \in \{3,2^a \cdot 3, 2^a \cdot 5, 2^a \cdot 7\}$. In the second case $n \in \{p^2,2p^2\}$ we have $\varphi(n)=p(p-1)$ and so $(p-1)\varphi(p-1) \mid 2p^2$ and so $p-1 \mid 2$ and hence $p=3$. Hence we get the solution $n=18$ and more generally $n \in \{2^a \cdot 3^b\}$. Finally, if $k=0$ we get the solutions $n \in \{1,2,4\}$ and more generally $n=2^a$. Summarizing, we get the solutions - $n=1$ and $n=3$. - $n=2^k \cdot 3^m$ with $k \ge 1, m \ge 0$. - $n=5 \cdot 2^k$ and $n=7 \cdot 2^k$ with $k \ge 1$.