Proving Phi(m) Is Even

Date: 04/22/98 at 14:30:41
From: John Damaso
Subject: Why phi(m) is always even for m>2

QUESTION: Explain why phi(m) is always even for m > 2.

Here is what I know:

* phi(m) is the number of positive integers less than m that are 
  relatively prime to m.

* phi(2) = 1     phi(8) = 4
  phi(3) = 2     phi(9) = 8
  phi(4) = 2     phi(10)= 4
  phi(5) = 4     phi(11)= 10
  phi(6) = 2
  phi(7) = 6

* phi(p) = p-1, where p is prime

Help me, please.

Date: 04/22/98 at 16:02:40
From: Doctor Rob
Subject: Re: Why phi(m) is always even for m>2

Observe phi(2^e) = 2^(e-1), since all odd numbers and no even numbers 
are relatively prime to 2^e. For e > 1, so m = 2^e > 2, this is even.

Now for all other m > 2, m has an odd prime divisor p. Then let p^e 
be the highest power of p dividing m, so m = p^e*n, and GCD(n,p) = 1.  
Then phi(m) = phi(p^e)*phi(n). Now x and p^e are relatively prime if 
and only if x and p are relatively prime if and only if x is not 
divisible by p. There are exactly 1 out of every p numbers up to p^e 
divisible by p, so:

     phi(p^e) = p^e - p^e/p = p^e - p^(e-1) = (p-1)*p^(e-1)

and p-1 is an even number. Thus phi(m) is phi(n) times an even 
number, so it is even.

This relies on the fact that if GCD(a,b) = 1, 
phi(a*b) = phi(a)*phi(b). Look at the array:

         1         2      ...   a-1    a
        a+1       a+2     ...  2*a-1  2*a
        ...       ...           ...   ...
     (b-1)*a+1 (b-1)*a+2  ...  b*a-1  b*a

There are phi(a*b) entries realtively prime to a*b. The elements of 
each column are congruent to each other modulo a. The first row forms 
a complete system of residues modulo a. Thus phi(a) columns contain 
numbers relatively prime to a, and the others contain no such numbers.  

Now look at any column with elements relatively prime to a. Since a 
and b are relatively prime, the entries of this column form a complete 
system of residues for b. Thus it contains precisely phi(b) elements 
relatively prime to b. Thus there are phi(a) columns containing phi(b) 
elements relatively prime to both a and b, so there are phi(a)*phi(b) 
elements relatively prime to both a and b. 

But GCD(x,a*b) = GCD(x,a)*GCD(x,b), because GCD(a,b) = 1, so 
GCD(x,a*b) = 1 if and only if GCD(x,a) = GCD(x,b) = 1. Thus there are 
phi(a)*phi(b) elements relatively prime to a*b. But we saw at the 
beginning that there are phi(a*b) entries relatively prime to a*b.
Thus phi(a*b) = phi(a)*phi(b).

Here is another reason. If 0 < x < m is relatively prime to m, so is 
m-x. These are different unless m is even and x = m/2. But m/2 divides 
m evenly, so their GCD(m/2,m) = m/2, and that is equal to 1 if and 
only if m = 2. Thus if m > 2, the relatively prime numbers less than m 
can be arranged in pairs (x, m-x) of distinct ones, with none left 
over. Thus their number must be even.

-Doctor Rob,  The Math Forum
Check out our web site! http://mathforum.org/dr.math/