¿Cómo se encuentran todos $n$ tal que $\phi(n)|n$

Question

Dónde $\phi(n)$ es la función phi de Euler, ¿cómo encontrar todas las $n$ tal que $\phi(n)|n$ ?

Answer 1

Observe que $\varphi(1) = \varphi(2) = 1$ Así que $\varphi(1) \mid 1$ y $\varphi(2) \mid 2$ .

Si $n > 2$ supongamos que la factorización en primos de $n$ es

$$n = p_1^{a_1} \ldots p_k^{a_k}$$

Entonces la fórmula de la función totiente da

$$\varphi(n) = (p_1 - 1)p_1^{a_1-1}\ldots (p_k - 1)p_k^{a_k-1}.$$

Desde $n>2$ siempre es un número par, por lo que $p_1=2$ debe aparecer como factor. A continuación observamos que $n$ no puede tener dos factores primos Impares. Si $a_2>0$ y $a_3>0$ entonces ambos $p_2-1$ y $p_3-1$ son pares, por lo que $2^{a_1+1}\mid \varphi(n)$ que es una contradicción.

Así que $n=2^{a_1}p^{a_2}$ para algún primo $p>2$ . Aquí $p-1\mid\varphi(n)\mid n$ Así que $p-1$ debe ser una potencia de dos, por ejemplo $p-1=2^\ell$ . Entonces $2^{a_1-1+\ell}\mid\varphi(n)$ por lo que debemos tener $\ell=1$ y $p=3$ .

Al final podemos comprobar que $n=1$ o $n=2^a3^b$ con $a>0$ , $b\ge0$ .

Answer 2

Enfoque de fuerza cuasi bruta con Maple :

with(numtheory):
for n from 1 to 100 do
if n mod phi(n) = 0 then
print(n);
end if;
end do;