Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

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.

share|cite|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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?

share|cite|improve this answer
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$.

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.