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

Printable View

- Jan 28th 2009, 03:32 AMCairoEuler Totient
For what integers does phi(n) | n and why?

- Jan 28th 2009, 02:25 PMclic-clac
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}$ - Jan 29th 2009, 08:08 AMCairo
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? - Jan 29th 2009, 09:46 PMclic-clac
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)