Results 1 to 5 of 5

Thread: Eulers totient function

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    97
    How can I show that


    $\displaystyle

    \phi(n) \geq \sqrt{n/2}.
    $

    Write
    $\displaystyle

    n= {p_1}^n_1...{p_r}^n_r.
    $
    Then

    $\displaystyle

    \frac {\phi({p_1}^n_1)}{\sqrt {n}} = \frac{(p_1-1)p^{n_1-1}}{p_1^{n_1/2}}
    $

    then what?
    Last edited by mr fantastic; Jan 15th 2009 at 06:51 PM. Reason: Merged posts
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    First we must have $\displaystyle n\geq{2}$ for the ineuqality to hold

    You'll need these 2 inequalities (by $\displaystyle p$ I mean prime):

    $\displaystyle
    \left\{ \begin{gathered}
    \phi \left( {2^k } \right) = 2^{k - 1} \geqslant \sqrt {\tfrac{{2^k }}
    {2}} = 2^{\tfrac{{k - 1}}
    {2}} \hfill \\
    \phi \left( {p^k } \right) = p^{k - 1} \cdot \left( {p - 1} \right) \geqslant \sqrt {p^k }{\text{ if }}p > 2 \hfill \\
    \end{gathered} \right.
    $ for $\displaystyle k\geq{1}$

    For the second:

    $\displaystyle
    p - \sqrt p + \tfrac{1}
    {4} = \left( {\sqrt{p} - \tfrac{1}
    {2}} \right)^2 \geqslant \left( {\sqrt{3} - \tfrac{1}
    {2}} \right)^2 \geqslant \tfrac{5}
    {4}\therefore p - 1 \geqslant \sqrt p \geqslant p^{1 - \tfrac{k}
    {2}}
    $ $\displaystyle
    \Rightarrow p - 1 \geqslant p^{1 - \tfrac{k}
    {2}} $

    Now your inequality follows easily from the fact that $\displaystyle \phi$ is multiplicative.

    In fact, you can see from the inequalities above -check the equality conditions- that your inequality is strict for all $\displaystyle n>2$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2008
    Posts
    97
    Thank you very much for the very clear and detailed answer.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2008
    Posts
    97
    Dont you think that there is something wrong with it because if we say
    n=2^r_0*p_1^r_1*...*p_m^r_m,

    then dont you think that we missing odd numbers?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by peteryellow View Post
    Dont you think that there is something wrong with it because if we say
    n=2^r_0*p_1^r_1*...*p_m^r_m,

    then dont you think that we missing odd numbers?
    If you followed what I said you'd get $\displaystyle \phi(n)>\sqrt{n}$ for $\displaystyle n$ odd (n greater than 1). Which is in fact stronger because $\displaystyle \sqrt{n}>\sqrt{\tfrac{n}{2}}$

    You take from above the factors that you need.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Oct 2nd 2011, 09:10 AM
  2. Eulers Totient
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: Oct 1st 2011, 08:56 AM
  3. Totient Function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Mar 28th 2011, 07:28 PM
  4. Euler totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 1st 2010, 09:33 AM
  5. Eulers totient function
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Jan 14th 2009, 07:10 PM

Search Tags


/mathhelpforum @mathhelpforum