Demostrar que si $n>10$ entonces $\sum_{d\mid n}\phi(\phi(d))<\frac{3}5n$

Question

Demuestra que si $n>10$ entonces $$\sum_{d\mid n}\phi(\phi(d))<\frac{3}5n,$$ donde $\phi(n)$ es la función phi de Euler.

Answer 1

Comenzamos con la identidad: $$n=\sum_{d|n}\phi(d).$$ Para demostrarlo, simplemente note que el lado derecho es una función multiplicativa y por lo tanto es suficiente verificar la igualdad solo para potencias de primos.

Ahora, el punto clave es notar que si $d|n$ entonces $\phi(d)|\phi(n)$ y por lo tanto el lado izquierdo de nuestra desigualdad es la suma $\phi(m)$ donde $m$ recorre algunos divisores de $\phi(n).$ En otras palabras,

$$\sum_{d\mid n}\phi(\phi(d))=\sum_{m|\phi(n)}\phi(m)-S=\phi(n)-S,$$ donde $S$ es la suma de esos divisores de $\phi(n)$ que no son de la forma $\phi(d),$ $d|n.

Ahora, si $n=p_1^{\alpha_1}\cdotp_2^{\alpha_2}...\cdot p_k^{\alpha_k}$ entonces $\phi(n)=p_1^{\alpha_1}\cdotp_2^{\alpha_2}...\cdot p_k^{\alpha_k}(p_1-1)....(p_k-1)$ y esos divisores que provienen de $\phi(d)$ son todos de la forma $m=p_1^{\beta_1}\cdotp_2^{\beta_2}...\cdot p_k^{\beta_k}\prod_{i}(p_i-1).$ Así que si $n\ne 2^m$ entonces el divisor $D=\frac{p_1^{\alpha_1-1}\cdotp_2^{\alpha_2-1}...\cdot p_k^{\alpha_k-1}(p_1-1)....(p_k-1)}{2}$ está en $S$ y podemos estimar:

$$\phi(n)-S\le \phi(n)/2\le \frac{n}{2}\le \frac{3}{5}n.$$ Te queda verificar $n=2^m$ lo cual se puede hacer fácilmente directamente.