Results 1 to 5 of 5

Math Help - Phi function help

  1. #1
    Member
    Joined
    Jul 2008
    Posts
    78

    Phi function help

    The Euler Phi function counts the number of positive integers less than or equal to n, which are relatively prime to n.

    Prove that if n is odd, then , and if n is even, then . I don't really know how to begin.

    Here's my attempt to prove the first part, if n is odd, .

    Let the prime decomposition of n be .

    So,



    But it seems like this would work for all n, not just odd n, so my above proof must be wrong.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Who tells thou that among the prime decomposition the p_i's are different from 2?
    Instead decompose n>1 as n=2^m*p1^(a1)*...*pk^ak where m>=0
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    See result 2(b) here
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jul 2008
    Posts
    78
    Thank you guys for the reply. I think I got it now.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    recall that \varphi(ab)=\varphi(a)\varphi(b), whenever \gcd(a,b)=1. now if n is odd, then \gcd(2,n)=1. so \varphi(2n)=\varphi(2)\varphi(n)=\varphi(n).

    if n is even, then n=2^km, for some m, k \geq 1, with \gcd(2,m)=1. therefore: \varphi(2n)=\varphi(2^{k+1} m)=\varphi(2^{k+1}) \varphi(m)=

    (2^{k+1} - 2^k)\varphi(m)=2(2^k - 2^{k-1})\varphi(m)=2\varphi(2^k)\varphi(m)=2\varphi(2^k m)=2\varphi(n). \ \ \ \square
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 20
    Last Post: November 27th 2012, 05:28 AM
  2. Replies: 0
    Last Post: October 19th 2011, 04:49 AM
  3. Replies: 4
    Last Post: October 27th 2010, 05:41 AM
  4. Replies: 3
    Last Post: September 14th 2010, 02:46 PM
  5. Replies: 2
    Last Post: September 2nd 2010, 10:28 AM

Search Tags


/mathhelpforum @mathhelpforum