[Math] Prove that $\phi(n)=\frac{n}{2}$ iff $n=2^k$ for some integer $k\geq 1$

elementary-number-theorynumber theorytotient-function

Prove that $\phi(n)=\frac{n}{2}$ iff $n=2^k$ for some integer $k\geq 1$

Attempt:
Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. Then $\phi(n)=\frac{n}{2} \implies \frac{n}{2}=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_k})$
$\implies p_1p_2\dots p_k=2(p_1-1)(p_2-1)\cdots (p_k-1)$.

Unable to go further. Please help.

The converse part:
If $n=2^k$ then $\phi(n)=\phi(2^k)=2^k(1-1/2)=n/2.$ (proved)

Best Answer

Hint: Let $p_k$ be the largest prime factor. It is a factor of:

$$2(p_1-1)(p_2-1)\cdots (p_k-1)$$

Related Question