# prove that there are infinitely many k such that $\phi(n) = k$ has precisely two solutions

I am asked to prove that there are infinitely many $k$ such that $\phi(n) = k$ has precisely two solutions.
I think for any prime number $p \mid n$, we have $(p-1) \mid \phi(n)$. But I am not sure how to proceed from here.
Could someone please give me some hint on this?

## 1 Answer

HINT: Suppose that $p_1^{k_1}p_2^{k_2}\ldots p_m^{k_m}$ is the prime factorization of $n$. Then

$$\varphi(n)=\prod_{i=1}^m\left(p_i^{k_i}-p_i^{k_i-1}\right)=\prod_{i=1}^mp_i^{k_i-1}(p_i-1)\;.$$

Thus, you have to find numbers that can be expressed in the form

$$\prod_{i=1}^mp_i^{k_i-1}(p_i-1)\tag{1}$$

in exactly two different ways. For example, $2=3^{1-1}(3-1)=2^{2-1}(2-1)$, and there is no other way to express $2$ in the form $(1)$, so the equation $\varphi(n)=2$ has precisely the two solutions $n=3$ and $n=4$. Another example is $4=5^{1-1}(5-1)=2^{3-1}(2-1)$.

• I am thinking of Fermat primes. Am I on the right track? Thanks for the hint! – Ra1nWarden Feb 16 '15 at 21:20