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

Homework Help: Proof:phi(m) is always even if m>2

  1. Mar 11, 2010 #1
    So I am aiming to prove that phi(m) is always even if m>2.
    What I have thus far
    If n is an integer such that (n,m)=1 where 1<n<m then (m-n,m)=1. Note: If (m-n,m) are not coprime this would imply that m-n divides m. This is a contradiction.
    Now, consider the case where m is even and n=m/2. Clearly m/2 divides m and the gcd(m/2,m)=m/2. m/2=1 iff m=2.

    I am just a little lost how I can use this information to imply that phi(m) is always even...
     
  2. jcsd
  3. Mar 12, 2010 #2
    I don't understand this part by itself. If [tex]m - n[/tex] is not coprime to [tex]n[/tex], it is not coprime to [tex]n[/tex], nothing more. However, it is true that if [tex](n, m) = 1[/tex] then [tex](m - n, m) = 1[/tex]; you just need a better proof.

    As for the argument as a whole: you have the flesh, but you are missing the bones.

    [tex]\phi(m)[/tex] is the size of a set. What set? The set [tex]RP(m)[/tex] of numbers [tex]1 \leq n \leq m[/tex] which are relatively prime to [tex]m[/tex].

    How do you show that the size of a set is even? One way is to divide it into pairs.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook