Find $m \in \mathbb{N}$ such that $\varphi(m)$ is a prime number.

Question

Find all natural numbers $m$ such that $\varphi(m)$ is a prime number.

Let $a$ is coprime with $m$. By using Euler's theorem and Fermat's little theorem, we have $a^{\varphi(m)} \equiv 1 \mod m$ and $a^{m-1} \equiv 1 \mod m$.

This is the only thing I have. Please help me. Thank you very much.

Answer 1

If $m$ is prime, then $\phi(m)=m-1$ is prime only if $m=3$. ($m=2$ doesn't work, so $m$ is odd, then $m-1$ is even, and $2$ is the only even prime).

If $m$ isn't prime, there are two cases:

1. $m=p^k$ with $p$ prime.
2. $m=pq$ with $(p,q)=1$, $\,p,q\not =1$.

If $m=p^k$, then $\phi(m)=p^{k-1}(p-1)$ is prime, then $p=2$, $k=2$, so $m=4$.

If $m=pq$, then since $\varphi(m)=\varphi(p)\varphi(q)$ is prime, meaning one of them, say $\varphi(p)=1$, then $p=2$. Since $\varphi(q)$ is prime, since $q$ can't contains factors of $2$, using the same reasoning above, then it can only be $3$.

This gives the only $m$ to be $3,4,6$.