Results 1 to 6 of 6

Thread: 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,410
    Thanks
    1
    For some power of a prime, $\displaystyle \varphi \left(p^n\right) = p^{n-1}(p-1)$.

    And since $\displaystyle \varphi$ is a multiplicative function, let $\displaystyle m = p_{1}^{e_{1}}p_{2}^{e_{2}}\hdots p_{k}^{e_{k}}$ be the prime-power decomposition of $\displaystyle m$. Then: $\displaystyle \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 $\displaystyle \varphi (24)$, we would have: $\displaystyle \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, $\displaystyle \phi\left(p^n\right)=p^{n-1}(p-1)$, and $\displaystyle \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 $\displaystyle 2^5\cdot5$. Note that the above tells us that $\displaystyle \phi\left(2^n\right)=2^{n-1}$. Thus, we need to find prime p and integer n≥1 such that $\displaystyle \phi\left(p^n\right)=p^{n-1}(p-1)$ is equal to five times a power of two (less than $\displaystyle 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 $\displaystyle \phi(25)=\phi\left(5^2\right)=5^{2-1}(5-1)=20$
    and 160=8*20, and $\displaystyle \phi(16)=\phi\left(2^4\right)=2^{4-1}=8$.
    Thus 25*16=400 is one number n such that $\displaystyle \phi(n)=160$.
    For the second, p=11, we have $\displaystyle \phi(11)=\phi\left(11^1\right)=11^{1-1}(11-1)=10$
    and 160=16*10, and $\displaystyle \phi(32)=\phi\left(2^5\right)=2^{5-1}=16$.
    Thus 11*32=352 is the second number n such that $\displaystyle \phi(n)=160$.
    The third case, p=41, gives $\displaystyle \phi(41)=\phi\left(41^1\right)=41^{1-1}(41-1)=40$; here 160=4*40, and $\displaystyle \phi(8)=\phi\left(2^3\right)=2^{3-1}=4$.
    Thus 41*8=328 is the third number n such that $\displaystyle \phi(n)=160$.

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

    --Kevin C.
    Last edited by TwistedOne151; Sep 27th 2008 at 11:42 PM. 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
    10
    Quote Originally Posted by TwistedOne151 View Post
    As o_O noted, $\displaystyle \phi\left(p^n\right)=p^{n-1}(p-1)$, and $\displaystyle \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 $\displaystyle 2^5\cdot5$. Note that the above tells us that $\displaystyle \phi\left(2^n\right)=2^{n-1}$. Thus, we need to find prime p and integer n≥1 such that $\displaystyle \phi\left(p^n\right)=p^{n-1}(p-1)$ is equal to five times a power of two (less than $\displaystyle 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 $\displaystyle \phi(25)=\phi\left(5^2\right)=5^{2-1}(5-1)=40$ 5×4=20, not 40 !
    and 160=4*40, and $\displaystyle \phi(8)=\phi\left(2^3\right)=2^{3-1}=4$.
    Thus 25*8=200 is one number n such that $\displaystyle \phi(n)=160$.
    So if we write $\displaystyle 160=2^3\times20$ and use the fact that $\displaystyle 2^3=\phi(2^4)$ then we get 25×16=400 as the first solution.

    But there is another possibility here. Notice that $\displaystyle \phi(3)=3^0(3-1)=2$. So we could write $\displaystyle 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 $\displaystyle \phi(11)=\phi\left(11^1\right)=11^{1-1}(11-1)=10$
    and 160=16*10, and $\displaystyle \phi(32)=\phi\left(2^5\right)=2^{5-1}=16$.
    Thus 11*32=352 is the second number n such that $\displaystyle \phi(n)=160$.
    Here again, you get more than one solution. Starting from 160=16×10 and using $\displaystyle 10=\phi(11)$, we need to find all the numbers n for which $\displaystyle \phi(n)=16$:

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

    Quote Originally Posted by TwistedOne151 View Post
    The third case, p=41, gives $\displaystyle \phi(41)=\phi\left(41^1\right)=41^{1-1}(41-1)=40$; again, 60=4*40, and $\displaystyle \phi(8)=\phi\left(2^3\right)=2^{3-1}=4$.
    Thus 41*8=328 is the third number n such that $\displaystyle \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: Jul 6th 2010, 04:09 PM
  2. Euler path and Euler circuit problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 19th 2010, 08:18 PM
  3. Replies: 0
    Last Post: Feb 20th 2010, 08:26 AM
  4. Replies: 0
    Last Post: Sep 17th 2009, 06:44 PM
  5. euler phi-function
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Mar 29th 2009, 07:42 PM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum