Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Why is phi(n) always an even number?

  1. Jan 18, 2010 #1
    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.
     
  2. jcsd
  3. Jan 18, 2010 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Jan 18, 2010 #3
    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
     
  5. Jan 18, 2010 #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: Apr 24, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Why is phi(n) always an even number?
Loading...