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

Question

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)

Answer 1

Expanding on Thomas's hint, and writing out the comments:

Wikipedia on Euclid's Lemma:

If a prime divides the product of two numbers, it must divide at least one of those numbers.

I'll leave you to figure out why this can be applied to a product of more than two numbers.

$p_k$ is the largest prime factor, and it's a factor of $2(p_1−1)(p_2−1)⋯(p_k−1)$.

Euclid's lemma says it must divide at least one of them. So which one does it divide?

Assume $p_k > 2$. Then $p_k \nmid 2$

Does $p_k | (p_1-1)$? $p_k | (p_2-1)$? Etc.

For the other case, $p_k = 2$, the problem is over.

Answer 2

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)$$

Answer 3

Write $n$ as $n=2^km$, where $\gcd(m,2) = 1$. This gives us $$\phi(n) = \phi(2^k) \phi(m) = 2^{k-1} \phi(m) \,\,\,\, (\spadesuit)$$ We are also given that $$\phi(n) = \dfrac{n}2 = 2^{k-1}m \,\,\,\, (\clubsuit)$$ Comparing $(\spadesuit)$ and $(\clubsuit)$, we obtain that $\phi(m) = m$. This means $m=1$ is the only possibility, since for $m > 1$, we have $\phi(m) < m$. Hence, we obtain $n=2^k m$.