Results 1 to 10 of 10

Math Help - Can any one please help with this Euler's function question ?

  1. #1
    Newbie
    Joined
    Aug 2010
    Posts
    13

    Can any one please help with this Euler's function question ?



    Determine all integers n for which Euler's function (phi) = n/2?

    Can anyone please help me, I'm really not sure what to do?!

    Thank you

    xx
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jan 2009
    Posts
    715
    We have this famous result  \phi(n) = n \prod \left( 1 - \frac{1}{p_i } \right) where  p_i | n .


    Then we are going to show   \prod \left( 1 - \frac{1}{p_i } \right)  = \frac{1}{2} . The key to the problem is using inequality :


    We know the smallest prime is  2 , thus  p_i \geq 2 or  \frac{1}{p_i} \leq \frac{1}{2}


     1 - \frac{1}{p^i} \geq 1- \frac{1}{2} = \frac{1}{2}


    Therefore ,  \frac{1}{2} =  \prod \left( 1 - \frac{1}{p_i } \right)  \geq \frac{1}{2^n} where  n denotes the number of primes involving in the product , since  n \geq 1 , we must have  n=2 and the only one prime  p_1  is  2 . We find that 2 is the only prime divisor of n so it is a power of  2 namely  2^k .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2010
    Posts
    19
    Hi,
    if you don't know the formula used by simplependulum, you can also write n=2^m*q, with q=2k+1, and use \phi (m)* \phi(n) =\phi (mn) when GCD(m,n)=1
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Aug 2010
    Posts
    13
    Quote Originally Posted by thorin View Post
    Hi,
    if you don't know the formula used by simplependulum, you can also write n=2^m*q, with q=2k+1, and use \phi (m)* \phi(n) =\phi (mn) when GCD(m,n)=1
    Hello thorin, thank you very much for your help, I wondered if you could please solve the question using the method you suggested too please as I'm not sure how to do it?

    Also, (sorry to ask soo much) but I am also trying to solve..

    Determine all integers n for which Euler's (phi) function = n/6

    and I cannot do it, can you please explain ho to do this too?

    THANK YOU SO MUCH!!!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2010
    Posts
    13
    Quote Originally Posted by simplependulum View Post
    We have this famous result  \phi(n) = n \prod \left( 1 - \frac{1}{p_i } \right) where  p_i | n .


    Then we are going to show   \prod \left( 1 - \frac{1}{p_i } \right)  = \frac{1}{2} . The key to the problem is using inequality :


    We know the smallest prime is  2 , thus  p_i \geq 2 or  \frac{1}{p_i} \leq \frac{1}{2}


     1 - \frac{1}{p^i} \geq 1- \frac{1}{2} = \frac{1}{2}


    Therefore ,  \frac{1}{2} =  \prod \left( 1 - \frac{1}{p_i } \right)  \geq \frac{1}{2^n} where  n denotes the number of primes involving in the product , since  n \geq 1 , we must have  n=2 and the only one prime  p_1  is  2 . We find that 2 is the only prime divisor of n so it is a power of  2 namely  2^k .
    Hi Simplependulum, Thank you so much for your help!! Can you also please explain the solution to...

    Determine all integers n for which Euler's (phi) function = n/6

    ..to me as I am finding it difficult?

    THANK YOU!!!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by HorseStar2 View Post
    Determine all integers n for which Euler's (phi) function = n/6
    I believe we can prove there are no such integers.

    Suppose we write n as its prime decomposition n=p_1^{\alpha_1}\cdots p_r^{\alpha_r} where as usual p_1 < \dots < p_r. Consider the product x=\prod \left( 1 - \frac{1}{p_i } \right) which must equal \frac{1}{6} to satisfy the given condition. When x is written as a fraction in lowest terms, the denominator must be divisible by p_r. (Details left for you to fill in.) So n cannot be divisible by a prime greater than 3. There are a trivially small number of cases to test to complete an exhaustive search.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Aug 2010
    Posts
    13
    Quote Originally Posted by undefined View Post
    I believe we can prove there are no such integers.

    Suppose we write n as its prime decomposition n=p_1^{\alpha_1}\cdots p_r^{\alpha_r} where as usual p_1 < \dots < p_r. Consider the product x=\prod \left( 1 - \frac{1}{p_i } \right) which must equal \frac{1}{6} to satisfy the given condition. When x is written as a fraction in lowest terms, the denominator must be divisible by p_r. (Details left for you to fill in.) So n cannot be divisible by a prime greater than 3. There are a trivially small number of cases to test to complete an exhaustive search.
    Hello undefined, thank you for replying. I wondered if you could submit the full answer plwwwease?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by HorseStar2 View Post
    Hello undefined, thank you for replying. I wondered if you could submit the full answer plwwwease?
    But which part are you having trouble with?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Aug 2010
    Posts
    13
    Quote Originally Posted by undefined View Post
    But which part are you having trouble with?
    Ohh the bit which says..Details left for you to fill in....I'm really sorry to ask... I just really need it spelt out for me..

    Thank you
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by HorseStar2 View Post
    Ohh the bit which says..Details left for you to fill in....I'm really sorry to ask... I just really need it spelt out for me..

    Thank you
    Rewrite 1-\frac{1}{p_i} as a single fraction.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler's phi-function.
    Posted in the Math Challenge Problems Forum
    Replies: 5
    Last Post: October 5th 2010, 11:37 AM
  2. Euler Totient Function Question
    Posted in the Number Theory Forum
    Replies: 12
    Last Post: June 3rd 2010, 03:52 PM
  3. A question about Euler's phi function
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 6th 2009, 05:28 AM
  4. euler phi function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 11th 2008, 09:05 PM
  5. Euler's phi function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 29th 2008, 05:07 AM

Search Tags


/mathhelpforum @mathhelpforum