# Why is phi(n) always an even number?

1. Jan 18, 2010

### 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 = pk, where p is a prime, because
phi(pk) = pk - 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.

2. Jan 18, 2010

### 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.

3. Jan 18, 2010

### 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

4. Jan 18, 2010

### 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.