Results 1 to 6 of 6

Math Help - Euler Phi Help

  1. #1
    Newbie
    Joined
    Sep 2008
    Posts
    7

    Euler Phi Help

    Hi everyone,

    I need to find all integers n such that Phi(n) = 160 and as an extension, make a list of all primes that might possibly divide x if Phi(x) = 1000. I'm a bit lost on this and was wondering if anyone could give me a useful start? Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    For some power of a prime, \varphi \left(p^n\right) = p^{n-1}(p-1).

    And since \varphi is a multiplicative function, let m = p_{1}^{e_{1}}p_{2}^{e_{2}}\hdots p_{k}^{e_{k}} be the prime-power decomposition of m. Then: \varphi (m) = \varphi \left(p_{1}^{e_{1}}\right)\varphi\left(p_{2}^{e_{2  }}\right)\hdots \varphi\left(p_{k}^{e_{k}}\right)

    So if I were to find \varphi (24), we would have: \varphi (24) = \varphi (2^{3} \cdot 3) = \varphi(2^3) \cdot \varphi (3) = 2^{2} (1) \ \cdot \ 3^{0} (2) = 8
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2008
    Posts
    7
    Right. I understand how to evaluate Phi(n), but I'm concerned with finding an n such that Phi(n) is equal to a given number.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Dec 2007
    From
    Anchorage, AK
    Posts
    276
    As o_O noted, \phi\left(p^n\right)=p^{n-1}(p-1), and \phi\left(p_{1}^{e_1}p_{2}^{e_2}\cdots p_{k}^{e_k}\right)=\phi\left(p_{1}^{e_1}\right)\ph  i\left(p_{2}^{e_2}\right)\cdots\phi\left(p_{k}^{e_  k}\right).

    The prime factorization of 160 is 2^5\cdot5. Note that the above tells us that \phi\left(2^n\right)=2^{n-1}. Thus, we need to find prime p and integer n≥1 such that \phi\left(p^n\right)=p^{n-1}(p-1) is equal to five times a power of two (less than 2^5=32). This needs either p=5 or p-1 is 5 times a power of 2.
    This leaves us with p=5, p=11, or p=41.
    The first has \phi(25)=\phi\left(5^2\right)=5^{2-1}(5-1)=20
    and 160=8*20, and \phi(16)=\phi\left(2^4\right)=2^{4-1}=8.
    Thus 25*16=400 is one number n such that \phi(n)=160.
    For the second, p=11, we have \phi(11)=\phi\left(11^1\right)=11^{1-1}(11-1)=10
    and 160=16*10, and \phi(32)=\phi\left(2^5\right)=2^{5-1}=16.
    Thus 11*32=352 is the second number n such that \phi(n)=160.
    The third case, p=41, gives \phi(41)=\phi\left(41^1\right)=41^{1-1}(41-1)=40; here 160=4*40, and \phi(8)=\phi\left(2^3\right)=2^{3-1}=4.
    Thus 41*8=328 is the third number n such that \phi(n)=160.

    Working similarly, you can find the primes that might divide x if \phi(x)=1000=2^3\cdot5^3.

    --Kevin C.
    Last edited by TwistedOne151; September 28th 2008 at 12:42 AM. Reason: Error in multiplication
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by TwistedOne151 View Post
    As o_O noted, \phi\left(p^n\right)=p^{n-1}(p-1), and \phi\left(p_{1}^{e_1}p_{2}^{e_2}\cdots p_{k}^{e_k}\right)=\phi\left(p_{1}^{e_1}\right)\ph  i\left(p_{2}^{e_2}\right)\cdots\phi\left(p_{k}^{e_  k}\right).

    The prime factorization of 160 is 2^5\cdot5. Note that the above tells us that \phi\left(2^n\right)=2^{n-1}. Thus, we need to find prime p and integer n≥1 such that \phi\left(p^n\right)=p^{n-1}(p-1) is equal to five times a power of two (less than 2^5=32). This needs either p=5 or p-1 is 5 times a power of 2.
    This leaves us with p=5, p=11, or p=41.
    The first has \phi(25)=\phi\left(5^2\right)=5^{2-1}(5-1)=40 5×4=20, not 40 !
    and 160=4*40, and \phi(8)=\phi\left(2^3\right)=2^{3-1}=4.
    Thus 25*8=200 is one number n such that \phi(n)=160.
    So if we write 160=2^3\times20 and use the fact that 2^3=\phi(2^4) then we get 25×16=400 as the first solution.

    But there is another possibility here. Notice that \phi(3)=3^0(3-1)=2. So we could write 160= 20\times2\times2^2 = \phi(5^2)\phi(3)\phi(8) = \phi(600).

    Quote Originally Posted by TwistedOne151 View Post
    For the second, p=11, we have \phi(11)=\phi\left(11^1\right)=11^{1-1}(11-1)=10
    and 160=16*10, and \phi(32)=\phi\left(2^5\right)=2^{5-1}=16.
    Thus 11*32=352 is the second number n such that \phi(n)=160.
    Here again, you get more than one solution. Starting from 160=16×10 and using 10=\phi(11), we need to find all the numbers n for which \phi(n)=16:

    16=2^4=\phi(2^5) is one possibility. But so are
    16=2\times2^3=\phi(3)\phi(2^4),
    16=4\times2^2=\phi(5)\phi(2^3),
    16=2\times4\times2=\phi(3)\phi(5)\phi(2^2), and finally
    16=\phi(17).

    Quote Originally Posted by TwistedOne151 View Post
    The third case, p=41, gives \phi(41)=\phi\left(41^1\right)=41^{1-1}(41-1)=40; again, 60=4*40, and \phi(8)=\phi\left(2^3\right)=2^{3-1}=4.
    Thus 41*8=328 is the third number n such that \phi(n)=160.
    Yet again, there are other possibilities...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Sep 2008
    Posts
    7
    Thank you everyone; I understand it much better now.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler phi
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: July 6th 2010, 05:09 PM
  2. Euler path and Euler circuit problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 19th 2010, 09:18 PM
  3. Replies: 0
    Last Post: February 20th 2010, 09:26 AM
  4. Replies: 0
    Last Post: September 17th 2009, 07:44 PM
  5. euler phi-function
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 29th 2009, 08:42 PM

Search Tags


/mathhelpforum @mathhelpforum