# Why is Euler's Totient function always even?

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.

• proofwiki.org/wiki/… – lab bhattacharjee Mar 7 '14 at 3:24
• It seems like your proof is 99% finished already :) – Niklas B. Mar 7 '14 at 4:05
• It is not difficult to show that $\phi (n)$ is even for $n\geq 3$ so the image of $\phi$ is composed of $1$ and even numbers. However, not all even numbers are in the image. It is interesting to explore just what even numbers are in this set. – Rodney Coleman Mar 9 '14 at 16:53

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.

• +1 for a fine 'first principles' proof - though I would note that for the one 'degenerate-pair' case where $k=n-k$, of course $\gcd(k, n)\neq 1$... – Steven Stadnicki Mar 7 '14 at 3:06
• This is a very nice proof. – Pedro Tamaroff Mar 7 '14 at 3:06
• @StevenStadnicki: Yes, that's why I wrote "(for $n > 2$)", as $k = n - k$ and $\gcd(k, n) = 1$ can happen when $n = 2$ and $k = 1$. :-) For larger $n$ though, $k = n - k$ means that $n = 2k$ and $\gcd(n, k) = \gcd(2k, k) = k > 1$. You're right that it's worth noting explicitly... – ShreevatsaR Mar 7 '14 at 3:07
• such a short, elegant and satisfying proof.. many Thanks!! – Bibekpandey Aug 31 '17 at 8:31

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.

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.

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.

A proof using group theory: Let $Z_n$ denote the cyclic group of order $n$. There exists a nontrivial order 2 element of $Aut(Z_n)$ for all $n>2$, namely the (additive) inversion map. Since $|Aut(Z_n)|=\phi(n)$, this implies that $\phi(n)$ is even for all $n>2$.

• Inversion map might be clarified to mean mapping to an additive inverse. This previous Math.SE Question would be worth adding as a link for the proposition about $Aut(Z_n)$. – hardmath Aug 20 '14 at 4:30

$\varphi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_k})$ where $p_i$'s are prime factors of $n$. Finally in numerator part every term of $(1-\frac{1}{p_i})$ is even, and all the pis in denominator will be cancelled by $n$ in numerator. So it is even.

I saw a proof related to group theory in the answers. I would like to comment on it since I have a related idea but I cannot due to my low reputation. His proof is a little bit advance and I could not understand it well as I am new to the field.

However, I came with my own proof:

From group Theory, let $Z_n$ be the group modulo n under addition. Then, every co-prime-to-n element in this group is paired with its inverse which is a co-prime as well[i.e. they have the same order = n]. Thus, the number of co-primes divisible by 2 as required.

I am not sure if this proof works well, but seems to have a good idea.