Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/