Results 1 to 5 of 5

Math Help - Eulers totient function

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


    <br /> <br />
\phi(n) \geq \sqrt{n/2}.<br />

    Write
    <br /> <br />
n= {p_1}^n_1...{p_r}^n_r.<br />
    Then

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

    then what?
    Last edited by mr fantastic; January 15th 2009 at 07: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 n\geq{2} for the ineuqality to hold

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

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

    For the second:

    <br />
p - \sqrt p  + \tfrac{1}<br />
{4} = \left( {\sqrt{p} - \tfrac{1}<br />
{2}} \right)^2  \geqslant \left( {\sqrt{3} - \tfrac{1}<br />
{2}} \right)^2  \geqslant \tfrac{5}<br />
{4}\therefore p - 1 \geqslant \sqrt p  \geqslant p^{1 - \tfrac{k}<br />
{2}} <br />
 <br />
 \Rightarrow  p - 1 \geqslant p^{1 - \tfrac{k}<br />
{2}}

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

    In fact, you can see from the inequalities above -check the equality conditions- that your inequality is strict for all 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 \phi(n)>\sqrt{n} for n odd (n greater than 1). Which is in fact stronger because \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: October 2nd 2011, 10:10 AM
  2. Eulers Totient
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: October 1st 2011, 09:56 AM
  3. Totient Function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 28th 2011, 08:28 PM
  4. Euler totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 1st 2010, 10:33 AM
  5. Eulers totient function
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: January 14th 2009, 08:10 PM

Search Tags


/mathhelpforum @mathhelpforum