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

```

```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search