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.

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