Results 1 to 9 of 9

Math Help - Euler Phi function problem.

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

    Euler Phi function problem.

    The problem is:

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

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

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

    I know since n is composite \phi(n) is not equal to (n-1), but I'm not sure what to do elsewhere.
    Last edited by Led; December 22nd 2009 at 04: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
    5
    As in ...

    Euler's totient function - Wikipedia, the free encyclopedia

    ... if...

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

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

    \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

    \chi \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 \phi(m), but we're supposed to express \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
    5
    I apologize because I didn't undestand exactly Your question ...

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

    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...

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

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



    Merry Christmas from Italy

    \chi \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 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
    5
    Now the trace is evident! ...

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

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

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



    Merry Christmas from Italy

    \chi \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
    5
    In the table reported in ...

    Euler's totient function - Wikipedia, the free encyclopedia

    ... You can verify that \forall n>2 \varphi (n) is an even number and the only n for which 4 doesn't devide \varphi (n) are n=p and 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 \varphi(m\cdot n)= \varphi(m)\cdot \varphi (n)...



    Merry Christmas from Italy

    \chi \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: November 11th 2010, 07:23 PM
  2. Euler's phi-function.
    Posted in the Math Challenge Problems Forum
    Replies: 5
    Last Post: October 5th 2010, 11:37 AM
  3. Euler path and Euler circuit problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 19th 2010, 09:18 PM
  4. Euler phi-Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 11th 2009, 07:11 PM
  5. euler phi function and others
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 4th 2008, 06:43 PM

Search Tags


/mathhelpforum @mathhelpforum