1
$\begingroup$

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.

  • 1
    Can you make a the list of all numbers less than $2^4$ and coprime with it?2012-03-13
  • 0
    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).2012-03-13
  • 0
    Note that $\phi$ is multiplicative, but not completely multiplicative. $\phi(mn)=\phi(m)\phi(n)$ holds only for _coprime_ m and n.2012-03-13

2 Answers 2

3

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?

  • 0
    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.2012-03-13
  • 0
    @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?2012-03-13
  • 0
    @J.D.- I'm unable to think of a way to prove that2012-03-13
  • 0
    @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?!2012-03-13
  • 0
    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}$2012-03-13
  • 0
    @JohnSmith the problem said iff. So if $n = 2^k$, we have $n/2 = 2^{k-1}.$ And.. if $n = 2^k$ (we're still under the same assumption), then $\varphi(n) = \varphi(2^k) = 2^{k-1} = n/2.$ (by the property of $\varphi(p^k) = ..$)2012-03-13
  • 0
    Oh man! I totally forgot about substituting for n on the L.H.S.. Thank you!2012-03-13
1

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