Results 1 to 2 of 2

Math Help - Euler Phi Function Problem

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    54

    Euler Phi Function Problem

    Suppose that n is a positive integer with E(n) = 8 .. E denotes Euler Phi Function

    Show that if p is an odd prime divisor of n, then p=3 or 5


    and hence find all possible values for n?


    To be honest, I did this more intuitively, then systematically.. I arrive at the solution fo 15. Which makes sense, since p|15 .... and give me E(15) = 8

    How would I approach this question in a more formal fashion ?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by ikurwae89 View Post
    Suppose that n is a positive integer with E(n) = 8 .. E denotes Euler Phi Function

    Show that if p is an odd prime divisor of n, then p=3 or 5


    and hence find all possible values for n?


    To be honest, I did this more intuitively, then systematically.. I arrive at the solution fo 15. Which makes sense, since p|15 .... and give me E(15) = 8

    How would I approach this question in a more formal fashion ?

    Thanks

    1) if n=p^k\,,\,p a prime, then \phi(n)=\phi(p^k)=p^{k-1}(p-1)=8\Longleftrightarrow p = 2\,,\,k=4 , but then

    n has no odd prime divisors, thus

    2) If n=p_1^{a_1}\cdot\ldots\cdot p_m^{a_m}\,,\,a_i\in \mathbb{N}\,,\,p_i primes, at least one of which is odd, then \phi(n)=n\displaystyle{\prod\limits^m_{k=1}\left(1-\frac{1}{p_k}\right)}.

    Continue from here, perhaps using induction on the number of different prime divisors of p...

    Tonio
    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 path and Euler circuit problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 19th 2010, 09:18 PM
  3. Euler Phi function problem.
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: December 22nd 2009, 11:10 AM
  4. Again, phi euler function
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: January 22nd 2009, 12:35 PM
  5. Help with euler-phi function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 1st 2007, 07:42 PM

Search Tags


/mathhelpforum @mathhelpforum