When is $\phi(n)$ a prime number?

Question

I was thinking about this problem today. If $p$ divides $n$, then $p-1$ must divide $\phi(n)$. But $p-1$ is even for all primes greater than $2$, so must $\phi(n) = 2$ - the only even prime? I feel like this argument is shaky and not very rigorous!

Answer 1

If your argument still feels shaky after people explain to you why your conclusion is correct it probably means that you came to the right conclusion by a long and perhaps wrong path.

The main thing to remember is that if $p$ is prime, then $\phi(p) = p - 1$. In $\mathbb Z^+$, there is only one even prime, 2, as you already know. All higher primes are odd. So then if $p$ is an odd prime, then $\phi(p) = p - 1$ is even.

Remember also that $\phi(n)$ is a multiplicative function. Let's say $p$ is an odd prime. Then, for example, if $q$ is some positive integer, prime or composite (doesn't matter as long as $\gcd(p, q) = 1$) then $\phi(pq) = \phi(p) \phi(q)$. Since $p$ is an odd prime and $\phi(p)$ is even, then $\phi(p) \phi(q)$ must be even as well, even if $\phi(q)$ does not contribute to 2's exponent.

And since all larger even integers are composite, you're looking for $p = 3$. It looks like $\phi(3) = 2$ is the only... um, wait a minute, remember that $\phi(2) = 1$ and therefore $\phi(6) = 2$. Okay, that's it, those are the only two solutions.

EDIT: I goofed, I forgot about 4. If $p$ is a prime, $n$ is an integer greater than 1 and $q$ is any positive integer coprime to $p$, then $\phi(p^n q) = \phi(p^n) \phi(q)$. Since $p^n = (p - 1)p^{n - 1}$, we still have $\phi(p^n q)$ even. Setting $p = 2$, $n = 2$, $q = 1$, we get $\phi(4) = 2$.

Now, to make sure I haven't forgotten any other solutions, I avail myself to this important inequality: $\phi(n) > \sqrt n$ for all $n > 6$. So, for instance, $\phi(7)$ has got to be at least 3, but we already established it can't be odd, so it must be at least 4.