Results 1 to 4 of 4

Math Help - Euler Totient

  1. #1
    Member
    Joined
    May 2008
    Posts
    140

    Euler Totient

    For what integers does phi(n) | n and why?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Let p be a prime and m a positive integer, \phi(p^m)=p^{m-1}(p-1) .
    So you see that the only prime p such that \phi(p^m)|p^m is 2.

    Let n\geq 2 be an integer such that \phi(n)|n, and p_1^{\alpha_1}...p_k^{\alpha_k}=n its unique decomposition in a product of primes, with p_1\leq ...\leq p_n and \alpha_i\geq 1, i=1,...k. Then, for all i\in \{1,...,k\},\ p_i-1 has to divide n , and a consequence is p_1=2.

    \phi(p_1^{\alpha_1}...p_k^{\alpha_k})=\phi(2^{\alp  ha_1}...p_k^{\alpha_k})=\phi(2^{\alpha_1}) \phi(p_2^{\alpha_2}...p_k^{\alpha_k})=2^{\alpha_1-1}\phi(p_2^{\alpha_2}...p_k^{\alpha_k})

    so \forall l\in \mathbb{N}, 2^l | \phi(p_2^{\alpha_2}...p_k^{\alpha_k})\Rightarrow l\leq 1 , and since \forall i\in \{2,...,k\},\ p_i is odd, that means k\leq 2 .

    If k=1 , that's ok; if k=2 , ( p_2-1\geq 2 and 4 can't divide p_2-1 and p_2-1|2^{\alpha_1}p_2^{\alpha_2} )\Rightarrow p_2-1=2 \Rightarrow p_2=3


    As you may see, \forall k,l\in \mathbb{N},\ \phi(2^{k+1}3^l)=2^{k+1}3^{l-1}|2^{k+1}3^l .
    Furthermore, \phi(1)=1 .


    Conclusion: the integers n such that \phi(n)|n are the elements of \{1\}\cup \{2^{k+1}3^l;\ k,l\in\mathbb{N}\}\subset \mathbb{N}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    Posts
    140
    Thank you for this.

    I'm a little confused over your notation, since you appear to interchange the exponent k and l for your primes.

    I have managed to google an exam paper that suggests that the answer is n = 2^a*3^b for a, b in N.

    How does this work?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Hi. The exponent notations can be changed during the proof, they are unknowns, so there is no problem.
    But the integers 2^a3^b,\ a,b\in\mathbb{N} arn't the solution because \phi(2^03^k)=2.3^{k-1} doesn't divide 3^k (that's why the solution is a little bit more complicated)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler's Totient Function
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: July 12th 2010, 10:41 AM
  2. Euler's totient
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 30th 2010, 07:21 PM
  3. Euler totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 1st 2010, 10:33 AM
  4. Euler Totient
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 11th 2009, 05:38 PM
  5. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 12th 2009, 07:11 PM

Search Tags


/mathhelpforum @mathhelpforum