I want to prove why $\phi(n)$ is even for $n>3$.
So far I am attempting to split this into 2 cases.
Case 1: $n$ is a power of $2$. Hence $n=2^k$. So $\phi(n)=2^k-2^{k-1}$. Clearly that will always be even.
Case 2: $n$ is not a power of $2$. This is where I am unsure where to go. I figure I will end up using the fact that $\phi(n)$ is multiplicative, and I think I'll get a $(p-1)$ somewhere in the resulting product which will make the whole thing positive, as $p$ is prime implies $(p-1)$ is even.
Best Answer
You can do it via the formula as you do, but you can also simply use the definition that $\phi(n)$ is the number of numbers $k$, with $1 \le k \le n$, such that $\gcd(n, k) = 1$.
Clearly, if $\gcd(k, n) = 1$, then $\gcd(n - k, n) = 1$ as well, so (for $n > 2$) all the numbers relatively prime to $n$ can be matched up into pairs $\{k, n-k\}$. So $\phi(n)$ is even.