Results 1 to 4 of 4

Thread: 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 $\displaystyle p$ be a prime and $\displaystyle m$ a positive integer, $\displaystyle \phi(p^m)=p^{m-1}(p-1)$ .
    So you see that the only prime $\displaystyle p$ such that $\displaystyle \phi(p^m)|p^m$ is $\displaystyle 2$.

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

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

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

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


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


    Conclusion: the integers $\displaystyle n$ such that $\displaystyle \phi(n)|n$ are the elements of $\displaystyle \{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 $\displaystyle 2^a3^b,\ a,b\in\mathbb{N}$ arn't the solution because $\displaystyle \phi(2^03^k)=2.3^{k-1}$ doesn't divide $\displaystyle 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: Jul 12th 2010, 09:41 AM
  2. Euler's totient
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jun 30th 2010, 06:21 PM
  3. Euler totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 1st 2010, 09:33 AM
  4. Euler Totient
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Oct 11th 2009, 04:38 PM
  5. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jul 12th 2009, 06:11 PM

Search Tags


/mathhelpforum @mathhelpforum