For which natural numbers are $\phi(n)=2$?

Question

I found this exercise in Beachy and Blair: Abstract algebra:

Find all natural numbers $n$ such that $\varphi(n)=2$, where $\varphi(n)$ means the totient function.

My try:

$\varphi(n)=2$ if $n=3,4,6$ and I think that no other numbers have this property. So assume $n>7$.

Case 1: $n$ is prime, since $\varphi(n)=n-1$ for primes, no numbers here will have the desired property

Case 2: $n$ is of the form $n=p^k$ for some prime $p$ and $k\in\mathbb{N}, k\ge 2$. By Eulers formula we get $$ \varphi(n)=p^k-p^{k-1} $$ which clearly is greater than $2$ since $n>7$.

Case 3: $n$ is the product of different primes and is squarefree (each prime comes up at most once in the prime factorisation of $n$). Assume $$ n=\prod_{i=1}^{m} p_i $$ by Eulers formula $$ \varphi(n)=n\prod_{p_i \ prime \ factor}\Big(1-\frac{1}{p_i}\Big) $$ which gives $$ \varphi(n)=p_1p_2\cdot\ldots\cdot p_m\Big(1-\frac{1}{p_1}\Big)\Big(1-\frac{1}{p_2}\Big)\cdot \ldots\cdot \Big(1-\frac{1}{p_m}\Big) $$ rearranging and multiplying out gives $$ (p_1-1)(p_2-1)\cdot\ldots\cdot (p_m-1) $$ which once again has to be greater than $2$ since $n>7$.

Case 4: $n$ is a product of different primes and not squarefree. This is similar to Case 3 but we get some more factors in the product so if there were no integers in Case 3 there cannot be here eighter.

Now my first question is: Is my reasonning correct? Ususally when I have to divide the solution up into so many cases I feel that I haven't grasped the problem properly, but I couldn't come up with anything better.

Any suggestions?

Thank you in advance

Answer 1

Let $n = \prod p_i^{k_i}$ be the prime factorization of $n$.

Then $\phi(n) = \prod p_i^{k_i - 1}(p_i-1)$.

So if $2 = 1^w*2^1 = \prod p_i^{k_i - 1}(p_i-1)$ then all the $(p_i -1) $ equal either $1$ or $2$ so all the $p_i$ equal either $2$ or $3$.

So either we have

$n = p^k$ and either $p=2$ or $3$;

So 1) $n = 2^k$ or 2)$n = 3^k$

Or we have

3) $n = 2^k3^m$

If 1) then $\phi(n) = 2^{k-1}(2-1) = 2$ so $k= 2$ and $n=4$.

If 2) then $\phi(n) = 3^{k-1}(3-1) = 2$ so $k = 1$ and $n =3$.

If 3) then $\phi(n) = 2^{k-1}(2-1)3^{m-1}(3-1)$ so $k =1$ and $m =1$ and $n=6$.

Those are the only three cases.

Answer 2

It's fairly trivial to prove that $\phi(n)$ is divisible by $2$ for any $n \ge 3$. So if $n$ has two coprime factors, both bigger than $3$ we have that $4 \mid \phi(n)$. Therefore the only remaining cases are $n=2p^k$ and $n=p^k$, where $p$ is an odd prime. You should be able to derive a constrain for $p$ and $k$ from here, by noting that $\phi(p^k) \ge \phi(p) = p-1$

Answer 3

For every prime $p\geq 4$ and ever natural number $k$ you have $p^k-p^{k-1}>2$. Since $φ(ab)=φ(a)φ(b)$ if $(a,b)=1$ this means that if you have a prime number $p\geq4$ which $p|n$ then $φ(n)>2$. Therefore only $2$ and $3$ can divide $n$. But $2^{k_1}-2^{k_1-1}=2^{k_1-1}$ and $3^{k_2}-3^{k_2-1}\geq2$ for $k_2\geq2$ therefore $k_2$ can be only $0,1$ and $k_1$ can be only $0$,$1$,$2$.

Now we check.

If $k_1=0$ then only $3|n$ so $n=3$.

If $k_1=1$ then $2$ doesn't contribute to the function so again $k_2=1$ and now $n=6$.

Finally, if $k_1=2$ then $φ(4)=2$ and this forces $k_2=0$.

So you were right, $n$ can only be $3,4,6$.