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

    cwatki14

    User Avatar

    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...
     
    cwatki14, Mar 11, 2010
  2. jcsd
    Phys.org - latest science and technology news stories on Phys.org
  3. Mar 12, 2010 #2

    ystael

    User Avatar

    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.
     
    ystael, Mar 12, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook




Loading...
Similar Threads for Proof always Date
Logic behind a proof Thursday at 6:17 PM
Proof about equality. Apr 15, 2018
Proof of minimum polynomial Apr 12, 2018
Prove True/False that n^3-n is Always Divisible By 6 Apr 30, 2017
How do I use proof by contradiction to show that a concave function is always increasing? Feb 12, 2015