$\varphi(n) \mid n$

Find all $n \in \mathbb{N}$ such that $\varphi(n) \mid n$.

Solution


Assume that for some positive integer $n$ we have $\varphi(n) \mid n$. First we prove that there is at most one odd prime dividing $n$. Let

$$n=2^s p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$$

where $p_1, p_2, \dots, p_k$ are dinstinct odd prime numbers. Then we get

$$\varphi(n)=2^{s-1} \prod_{i=1}^{k} p_i^{a_i-1} (p_i-1)$$

Noting that $p_i-1$ is even, we get that $p_i-1=2m_i$ for some integer $m_i$ thus

$$\varphi(n)=2^{s-1+k} \prod_{i=1}^{k} p_i^{a_i-1} m_i$$

and in particular $2^{s-1+k} \mid \varphi(n)$. However $2^{s+1} \nmid n$. Therefore, if $k>1$ then we cannot have $n \mid \varphi(n)$. That is there is at most one odd prime divisor of $n$.

So, we have to consider $4$ cases.

• $n=1$
• $n=2^a$
• $n=p^b$
• $n=2^a p^b$

where $p$ is an odd prime number and $a, b$ are positive integers. When $n=1$ it obviously holds that $\varphi (n) \mid n$. When $n=2^a$  we get $\varphi(n)=2^{a-1}$ so $\varphi(n) \mid n$. If $n=p^b$ then $\varphi(n)$ is even so $\varphi(n) \nmid n$. So, the only case that is left is when $n=2^a p^b$ . In this case , if $\varphi(n) \mid n$ we get:

$$(p-1)2^{a-1} p^{b-1} \mid 2^a p^b$$

which mean $p-1 \mid 2p$. Since $p-1$ and $p$ are coprime this can only happen if $p-1 \mid 2$ that is if $p-1=1$ or $p-1=2$.  However, since we are assuming that $p$ is odd , this means that $p=3$. Therefore, this can only happen if $p=2^a 3^b$.

Summing all the results up we have that $n=1, \; n=2^a, \; n=2^a 3^b$.