Why is phi(n) always an even number?

  • Thread starter crypto_rsa
  • Start date
  • #1

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
CRGreathouse
Science Advisor
Homework Helper
2,820
0
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
362
7
Perhaps the author had in mind the following argument:

Suppose that 1 [itex]\leq[/itex] 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 [itex]\leq[/itex] 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
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".
 
Last edited by a moderator:

Related Threads for: Why is phi(n) always an even number?

Replies
8
Views
2K
  • Last Post
Replies
2
Views
2K
Replies
13
Views
15K
Replies
9
Views
13K
Replies
7
Views
9K
  • Last Post
Replies
9
Views
3K
Replies
4
Views
3K
Replies
5
Views
2K
Top