Proving Phi(m) Is EvenDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/