Totient function: $φ(2^n)$ I was wondering how to go about finding $\varphi(2^n)$.
I know that $\varphi(2)=1$ and that $φ(mn) = φ(m)φ(n)$, but in this case having $\varphi(2^n) = \varphi(2\times2\times2\cdots\times 2)$ does not work since we end up with $1$ and this is not the answer. 

It's perhaps better to go back to the definition of the totient function - how many natural numbers less than $n$ are coprime to $n$?
In the case of any $n=2^k$, clearly every odd number is coprime to $n$, and every even number is not, so $\phi(n) =\frac{2^k}{2} = 2^{k-1}$
