Euler Totient

**Cairo** · January 28th 2009, 03:32 AM

For what integers does phi(n) | n and why?

**clic-clac** · January 28th 2009, 02:25 PM

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}$

**Cairo** · January 29th 2009, 08:08 AM

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?

**clic-clac** · January 29th 2009, 09:46 PM

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)

Thread: Euler Totient

LinkBack

Thread Tools

Display

Euler Totient

Similar Math Help Forum Discussions

Euler's Totient Function

Euler's totient

Euler totient function

Euler Totient

Euler's totient function

Search Tags