1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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