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

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

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

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.

• Thank you for the answer. I understand the solution. Now $p_k=max({p_i})=2$, then $p_i=2$ for all $i=1,2,\cdots k-1$. Then $n=p_1\dots p_k=2^k$. Is it not correct? – user1942348 Apr 26 '15 at 9:21
• I don't know. I'd have to look more closely at your entire argument to tell. One thing that's throwing me off is that you use $k$ in several places in your argument, but I'm not sure you intend for it to be the same $k$. Sorry I couldn't help you. Good luck. – r12 Apr 26 '15 at 10:37

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

• Please explain in details. – user1942348 Apr 25 '15 at 14:54
• Sorry, that's it for today. This is a nearly complete hint. – Thomas Andrews Apr 25 '15 at 14:55
• @user1942348 but $p_k$ is co-prime to any $m$ if $m<p_k$, so $p_k-1 \dots p_1-1$ are all co-prime to $p_k$ so $p_k|2$. – Alexey Burdin Apr 25 '15 at 14:59
• @AlexeyBurdin Not understand, would you please explain. – user1942348 Apr 25 '15 at 15:06
• @user1942348: Let $p_k$ be the largest prime among $p_1,\dots,p_k$, so $p_i-1<p_k$ , so $(p_i-1,p_k)=1$ due to $p_k$ is a prime and $p_i-1<p_k$. So $((p_1-1)(p_2-1)\dots(p_k-1),p_k)=1$. But $p_k|2(p_1-1)(p_2-1)\dots(p_k-1)$ so $p_k|2$. – Alexey Burdin Apr 25 '15 at 15:24

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