# How to prove $\phi(n) = n/2$ iff $n = 2^k$? [duplicate]

How can I prove this statement ? $\phi(n) = n/2$ iff $n = 2^k$

I'm thinking n can be decomposed into its prime factors, then I can use multiplicative property of the euler phi function to get the $\phi(n) = \phi(p_1)\cdots\phi(p_n)$. Then use the property $\phi(p) = p - 1$. But I'm not sure if that's the proper approach for this question.

-

## marked as duplicate by Martin Sleziak, Claude Leibovici, Newb, Lee Yiyuan, ShuchangMar 22 '14 at 6:43

Can you make a the list of all numbers less than $2^4$ and coprime with it? –  Mariano Suárez-Alvarez Mar 13 '12 at 3:42
I trust you are being brief in your description? You are using $n$ to denote two different things (the number, and the index of the primes) and it is not true that if $n=p_1\cdots p_k$ is an expression of $n$ into a product of primes, then $\phi(n)=\phi(p_1)\cdots\phi(p_k)$, unless you assume the primes are pairwise distinct (in which case, you are only talking about squarefree integers). –  Arturo Magidin Mar 13 '12 at 3:43
Note that $\phi$ is multiplicative, but not completely multiplicative. $\phi(mn)=\phi(m)\phi(n)$ holds only for coprime m and n. –  Charles Mar 13 '12 at 17:23

Edit: removed my full answer to be more pedagogical.

You know that $\varphi(p) = p-1$, but you need to remember that $\varphi(p^k) = p^{k-1}(p-1).$ Can you take it from here?

-
I'm thinking if I assume $n=2^k$ and substitute on the right hand side of the eq., it becomes $\phi(n) = 2^{k-1}$. So I'm guessing I need to show that to be true. But I'm failing at how to do that. –  devcoder Mar 13 '12 at 4:04
@JohnSmith Remember $n = 2^k.$ You want to show that $\varphi(n) = n/2.$ So really this problem is solved once you can show that $2^{k-1} {\color{red} =} n/2.$ Can you? –  user2468 Mar 13 '12 at 4:06
@J.D.- I'm unable to think of a way to prove that –  devcoder Mar 13 '12 at 4:16
@JohnSmith Okay. You know that $$n = 2^k$$ Now, if you divide each side by $2$, you get $$\frac{n}{2} = \frac{2^k}{2} =\ ??$$ can you see it happening?! –  user2468 Mar 13 '12 at 4:17
I see that. That's what I said in my first comment to your answer. I might be failing to understand correctly but here's my understanding. We assumed $n = 2^k$ from the statement in the question, by assumption $n/2 = 2^{k-1}$ always. I get that part. I can agree with how we got here after our assumption. The problem I'm facing after this assumption is how to show that $\phi(n) = 2^{k-1}$ –  devcoder Mar 13 '12 at 4:23

Suppose $n = 2^{k}$ for some $k \geq 0$. Given that $\varphi(n) = n \prod_{p \mid n}(1 - \frac{1}{p})$, it follows that $\varphi(2^{k}) = 2^{k} (1 - \frac{1}{2}) = \frac{n}{2}$. Now assume the converse, that $n = 2\varphi(n)$ for some positive integer $n$. Then $n = 2 n \prod_{p \mid n}(1 - \frac{1}{p})$ implies $2 \prod_{p \mid n}(p - 1) = \prod_{p \mid n} p$. Since the left side is even, so must be the right side. This implies that $2$ divides $n$. Moreover, $\prod_{2 < p \mid n}(p - 1) = \prod_{2 < p \mid n} p$ is impossible to satisfy, so $n = 2^{k}$ for some $k$.

-