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. 

Take a prime $p$. By definition
$$\phi(p^n)=\#\{q\leq p^n,\,\,\gcd(p^n,q)=1\}$$
Let's count. Between $1$ and $p^n$ we have $p^{n-1}$ numbers who have $p$ in their prime factorisation and so
$$\phi(p^n)=p^n-p^{n-1}=p^{n-1}(p-1)$$
For $p=2$ we get $\phi(2^n)=2^{n-1}$ 
