Exercise 2.3.42* (Solve $\phi(n) \mid n$)

Proof. Note that $\varphi (1)=1\mid 1$ . Assume now $n>1$, and write $n=p_1^{a_1}\cdots p_k^{a_k}$ its decomposition in prime factors, where $a_i>0,k\ge 1$ and $p_1<p_2<\cdots <p_k$. Then $\varphi (n)\mid n$ is equivalent to

Therefore

• If $k=1$, then $p_1-1\mid p_1$, which implies $p_1=2$, and $n=2^i$ for some positive integer $i$.

  Conversely, if $n=2^i,i\ge 1$, then $\varphi (n)=2^{i-1}\mid n$.

• If $k>1$, then one factor of $(p_1-1)\cdots (p_k-1)$ is even, so $2\mid p_1\cdots p_k$. This implies that $p_1=2$. Then

  $$(p_2-1)\cdots (p_k-1)\mid 2p_2\cdots p_k,$$

  where $p_2,\dots ,p_k$ are odd primes.

  For every index $i$, $2\le i\le k$, $p_i-1\mid 2p_2\cdots p_k$. Then $p_i-1\mid 2$, or $p_i-1\mid p_j$ for some index $j$. Since $p_j$ is prime and $p_i\ne 2$, we obtain $p_i-1=p_j$. This is impossible, since $p_i-1$ is even, and $p_j$ odd. Therefore $p_i=3$, and $k=2$, so $n=2^i{3}^j$, $i>0,j>0$.

  Conversely, if $n=2^i{3}^j,i>0,j>0$, then

  $$\varphi (n)=2^{i-1}{3}^{j-1}2=2^i{3}^{j-1}\mid 2^i{3}^j=n.$$

To conclude, $n\mid \varphi (n)$ if and only if $n=2^i$ for $i\ge 0$, or $n=2^i{3}^j$, where $i>0,j>0$. □