Results 1 to 5 of 5

Math Help - Euler Function Inequality

  1. #1
    Newbie
    Joined
    Feb 2010
    From
    Santa Monica, California
    Posts
    7

    Euler Function Inequality

    Hi all, I've been stumped by this proof:

    Prove that if n is any odd positive integer and k is a natural number such that n > 2^k, then phi(n) >= k + 1

    So far I've only been able to use the fact that n is odd to say that phi(2n) = phi(n) since phi(2n) = phi(2) * phi(n). I'm not sure if this is even relevant, but it seems like it could be useful. Any help is appreciated.

    Thank you
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Hello !

    phi(2n) = phi(n)
    This is wrong, it only holds if n is an odd prime number, which cannot be controlled in your question.

    Note that \varphi{ \left ( 2^k \right ) } = k. This might be useful.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by Bacterius View Post
    Hello !


    This is wrong, it only holds if n is an odd prime number, which cannot be controlled in your question.
    it's not wrong! if \gcd(m,n)=1, then \varphi(mn)=\varphi(m)\varphi(n). what do you get if you put m=2 and assume that n is odd?

    Note that \varphi{ \left ( 2^k \right ) } = k. This might be useful.
    sorry but this is wrong! for any positive integer k: \ \varphi(2^k)=2^{k-1}.

    Tand, if 0 \leq j \leq k, then 2^j \leq 2^k < n and \gcd(2^j,n)=1. how many elements does the set \{2^j: \ 0 \leq j \leq k \} have?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Haha, I got killed
    I'll be more careful next time, thanks NCA xD

    sorry but this is wrong!
    What the hell, this Java applet kept telling me that phi(256) = 8 and phi(512) = 9 ! I'll do it myself next time.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Feb 2010
    From
    Santa Monica, California
    Posts
    7

    Thank you

    Quote Originally Posted by [B
    Tand, if 0 \leq j \leq k, then 2^j \leq 2^k < n and \gcd(2^j,n)=1. how many elements does the set \{2^j: \ 0 \leq j \leq k \} have?
    It will have K+1 elements that are relatively prime to n. Then n's euler function is at least K + 1. That's perfect. Thank you very much!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler phi-function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 15th 2010, 02:38 PM
  2. Euler's Phi Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 5th 2009, 03:52 AM
  3. Euler's Phi Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 26th 2009, 04:42 PM
  4. Euler's phi function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 16th 2008, 05:54 PM
  5. Euler's Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 27th 2008, 02:52 PM

Search Tags


/mathhelpforum @mathhelpforum