Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

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|improve this question
1  
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

2 Answers

up vote 3 down vote

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|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
show 2 more comments
up vote 0 down vote

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|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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