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