Why is phi(n) always an even number?

[crypto_rsa]

I know it's a dumb question but I can't figure out why the totient of n is always even (I've read in a book that it "follows immediately from the definition of the totient function", so it should not require any theorem to prove). It is clear to me that it holds true for

n = p^k, where p is a prime, because
phi(p^k) = p^{k - 1}(p - 1) and (p - 1) is even

But why is it true in the general case? I think I could use multiplicativity of phi() to prove it but I am confused by the "follows from definition" note.

 

[CRGreathouse]

I can't see how it follows immediately from the definition, either. But it's clear from the formula for phi that phi(n) is even for any n > 2.

 

[Petek]

Perhaps the author had in mind the following argument:

Suppose that 1 \leq m < n and (m,n) = 1. Then it's easy to see that (n-m,n) = 1. Also, it can't be true that m = n-m because then 2m = n and so (n,m) > 1. Thus, for each such m we have another integer (n-m), distinct from m, that also satisfies 1 \leq n-m < n and (n-m,n) = 1. So, we have partitioned the integers from 1 to n-1 that are relatively prime to n into two sets of the same size. We conclude that the number of such integers, phi (n), is even.

Petek

 

[crypto_rsa]

There is a way how to prove it using just the definition:

If x is prime to n, then also n - x is prime to n (easily proven by contradiction). Except for the case when x = n/2, x and n - x are distinct. But when x = n/2, then n/x = 2 and x is not prime to n. So the numbers which are primes to n come always in pairs and thus their total number is even.

More information can be found at http://mathforum.org/library/drmath/view/51541.html".