Why is Euler's Totient function always even?

Question

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.

Answer 1

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.

Answer 2

Suppose $n>3$. If $n$ has an odd prime factor, say $p$; then $n=p^km,(m,p)=1$ and $\varphi (n)=\varphi(p^k)\varphi(m)=(p-1)p^{k-1}\varphi(m)$, with $p-1$ even. If $n$ has no odd prime factors, then $n=2^k$ with $k>1$ so $\varphi(2^k)=2^{k-1}$ is even.

Answer 3

Hint $\ $ The map $\,x\mapsto -x\pmod n\,$ has no fixed points so pairs-up the residues coprime to $n.\,$

Remark $\ $ Such use of reflections (or involutions) to pair-up terms frequently proves handy, e.g. see prior posts here on Wilson's theorem (in groups), esp. this one to start.

Answer 4

This answer will use some slightly more advanced machinery to get a short answer.

If $n\geq 3$ (you don't need to assume $n > 3$) then $-1\neq 1$ in $\mathbb{Z}/n\mathbb{Z}$, but $(-1)^2 = 1$, so $-1$ is an element of order $2$ in $(\mathbb{Z}/n\mathbb{Z})^{\times}$, which means that $|(\mathbb{Z}/n\mathbb{Z})^{\times}| = \varphi(n)$ is even by Lagrange.

Answer 5

One very intuitive proof is to notice that $$\left(\frac n2 +k \right)+\left(\frac n2 -k \right)=n$$ So, if $d$ divdes $n$, then $d$ divides both or none of $\left(\frac n2 +k \right)$ and $\left(\frac n2 -k \right)$. So, either there is at least one $d$ which divides all of $n$, $\left(\frac n2 +k \right)$ and $\left(\frac n2 -k \right)$, or there is no such $d$.

This means either both or none of $\left(\frac n2 +k \right)$ and $\left(\frac n2 -k \right)$ are coprime to $n$.

Note that we don't even need $\frac n2$ to be an integer. All we need are to have $\left(\frac n2 +k \right)$ and $\left(\frac n2 -k \right)$ to be integers.