Results 1 to 9 of 9

Thread: Euler Phi function problem.

  1. #1
    Led
    Led is offline
    Newbie
    Joined
    Dec 2009
    Posts
    3

    Euler Phi function problem.

    The problem is:

    $\displaystyle m=2\prod p_{i}^{e_i}$ for i=1...k
    where $\displaystyle k \geq 1$,$\displaystyle p_1,p_2,...p_k$ are odd primes in increasing order, and $\displaystyle e_1,...e_k$ are positive integers.

    We're told that $\displaystyle m=\phi(n)$ for some odd, composite n.

    Express the value of n in terms of $\displaystyle p_1,p_2,...p_k$ and $\displaystyle e_1,...e_k$.

    I know since n is composite $\displaystyle \phi(n)$ is not equal to (n-1), but I'm not sure what to do elsewhere.
    Last edited by Led; Dec 22nd 2009 at 03:45 AM. Reason: Major typo in problem
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    6
    As in ...

    Euler's totient function - Wikipedia, the free encyclopedia

    ... if...

    $\displaystyle m= p_{1}^{e_{1}}\dots p_{k}^{e_{k}}$ (1)

    ... where the $\displaystyle p_{i}$ are distinct primes, then...

    $\displaystyle \varphi(m)= (p_{1}-1)\cdot p_{1}^{e_{1}-1}\dots (p_{k}-1)\cdot p_{k}^{e_{k}-1}$ (2)



    Merry Christmas from Italy

    $\displaystyle \chi$ $\displaystyle \sigma$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Led
    Led is offline
    Newbie
    Joined
    Dec 2009
    Posts
    3
    Sorry, I made a big mistake in the problem. I know that for $\displaystyle \phi(m)$, but we're supposed to express $\displaystyle \phi(n)$.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    6
    I apologize because I didn't undestand exactly Your question ...

    For the fundamental theorem of arithmetic any m can be expressed as...

    $\displaystyle m= \prod_{i} p_{i}^{e_{i}}$ (1)

    ... so that any m doesn't have 'special properties'. If I understand correctly Your problem is, given m, to find the value of n for which is...

    $\displaystyle \varphi (n) = n \cdot \prod_{p|n} (1-\frac{1}{p}) = m$ (2)

    In general the equation (2), that supplies the 'inverse' of $\displaystyle \varphi (*)$, doesn't have a single solution and can be solved by 'systematic search'...



    Merry Christmas from Italy

    $\displaystyle \chi$ $\displaystyle \sigma$
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Led
    Led is offline
    Newbie
    Joined
    Dec 2009
    Posts
    3
    Thanks all your help...but I found another mistake i made. DOH!

    it's supposed to be $\displaystyle m=2\prod p_{i}^{e_i}$.

    Sorry for all the mistakes but I appreciate your help so far.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    6
    Now the trace is evident! ...

    If m and n are coprime, then is $\displaystyle \varphi(m\cdot n)=\varphi(m) \cdot \varphi (n)$ and because $\displaystyle \forall n >2$ $\displaystyle \varphi(n)$ is even , the only possibility if...

    $\displaystyle m= 2\cdot \prod_{i} p_{i}^{e_{i}}$ (1)

    ... with $\displaystyle \forall i$ $\displaystyle p_{i}$ an odd prime number is that $\displaystyle m+1$ is prime. In such a case the equation $\displaystyle \varphi(n)=m$ has the two solutions $\displaystyle n=m+1$ and $\displaystyle n=2\cdot (m+1)$ ...



    Merry Christmas from Italy

    $\displaystyle \chi$ $\displaystyle \sigma$
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Dec 2009
    Posts
    2

    More justification?

    Hi,

    I am interested in this problem as well. I'm not quite following your argument for why n = (m+1) and n = 2*(m+1) must be solutions to this problem. Could you provide more detail?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    6
    In the table reported in ...

    Euler's totient function - Wikipedia, the free encyclopedia

    ... You can verify that $\displaystyle \forall n>2$ $\displaystyle \varphi (n)$ is an even number and the only n for which $\displaystyle 4$ doesn't devide $\displaystyle \varphi (n)$ are $\displaystyle n=p$ and $\displaystyle n=2\cdot p$ , being p a prime number grater than 2. That is consequence of the basic property that if m and n are coprime, then $\displaystyle \varphi(m\cdot n)= \varphi(m)\cdot \varphi (n)$...



    Merry Christmas from Italy

    $\displaystyle \chi$ $\displaystyle \sigma$
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Dec 2009
    Posts
    2

    Thanks

    Ah yes, I see that now, thank you. However, in the problem it is stated that n is odd and composite. This means that neither of those solutions are valid for n, since p is prime and 2*p is even.

    I believe I figured it out: n must only have 1 odd factor otherwise 2^k, where k is the number of odd factors of n, would have to divide m. Since m only has one factor of 2, then k=1. Since phi(n)=m, that odd prime must be 3, otherwise an additional factor of 2 would appear from phi(q^c)=q^c*(1-1/q), where n = q^c.

    Therefore n = p^(e+1) = 3^(e+1), where p and e are the prime factor and power of m.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler Phi Function Problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 11th 2010, 06:23 PM
  2. Euler's phi-function.
    Posted in the Math Challenge Problems Forum
    Replies: 5
    Last Post: Oct 5th 2010, 10:37 AM
  3. Euler path and Euler circuit problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 19th 2010, 08:18 PM
  4. Euler phi-Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 11th 2009, 06:11 PM
  5. euler phi function and others
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Aug 4th 2008, 05:43 PM

Search Tags


/mathhelpforum @mathhelpforum