Tomemos $\varphi(n)=180$ como ejemplo. Adoptaremos un enfoque sistemático, pasando por cada una de las posibilidades.
En primer lugar, escribimos $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ , donde $p_1,p_2,\cdots,p_k$ son primos distintos y $e_i\ge 1$ para todos $1\le i\le k$ . Entonces lo sabemos:
$$\varphi(n)=p_1^{e_1-1}(p_1-1)p_2^{e_2-1}(p_2-1)\cdots p_k^{e_k-1}(p_k-1)$$
Así que lo que tenemos que hacer, es encontrar primos tales que $p-1\mid 180$ . O, de forma equivalente (y más fácil), tenemos que comprobar para cada divisor $d$ de $180$ si $d+1$ es primo. Sólo los primos que encontremos entonces, pueden ser factores de $n$ . Veamos: los divisores de $180$ son (utilizando $180=2^2\cdot 3^2\cdot 5$ ):
$$\{1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180\}$$
Y así añadimos $1$ a cada uno de ellos, y comprueba si son primos o no. El conjunto que nos queda es (lo llamaremos $S$ ):
$$S:=\{2, 3, 5, 7, 11, 13, 19, 31, 37, 61, 181\}$$
Ahora digamos que tenemos un primo $p\in S$ , de tal manera que $p^2\mid n$ . Entonces, $p\mid 180$ Así que.., $p\in\{2,3,5\}$ . Esas son las únicas primas que $n$ puede tener más de una vez. Ahora tenga en cuenta que $\gcd(a,b)=1$ implica $\varphi(ab)=\varphi(a)\varphi(b)$ . ¡Ahora vamos a encontrar por fin algunas soluciones!
Dejemos que $n=181\cdot m$ . Entonces $\varphi(n)=180=180\varphi(m)$ Ahora tenemos que resolver $\varphi(m)=1$ . Vemos dos soluciones, $m=1$ y $m=2$ , dando lugar a soluciones, $\color{red}{n=181}$ y $\color{red}{n=362}$ .
Dejemos que $n=61\cdot m$ . Entonces $\varphi(n)=180=60\varphi(m)$ Ahora tenemos que resolver $\varphi(m)=3$ . Podemos hacer esto con el mismo método descrito anteriormente (el conjunto de divisores de $3$ , $\{1,3\}$ , añadir uno, comprobar si es primo, obtener $\{2\}$ y ver que $\varphi(2^{e_1})=3$ nunca sucede). No hay soluciones.
Dejemos que $n=37\cdot m$ . Entonces $\varphi(n)=180=36\varphi(m)$ Ahora tenemos que resolver $\varphi(m)=5$ . No hay soluciones.
Dejemos que $n=31\cdot m$ . Entonces $\varphi(n)=180=30\varphi(m)$ Ahora tenemos que resolver $\varphi(m)=6$ . Encontramos $m\in\{7,9,14,18\}$ , lo que da lugar a $\color{red}{n=217}$ , $\color{red}{n=279}$ , $\color{red}{n=434}$ y $\color{red}{n=558}$ .
Dejemos que $n=19\cdot m$ . Entonces $\varphi(n)=180=18\varphi(m)$ Ahora tenemos que resolver $\varphi(m)=10$ . Encontramos $m\in\{11,22\}$ , lo que da lugar a $\color{red}{n=209}$ y $\color{red}{n=418}$ .
Dejemos que $n=13\cdot m$ . Entonces $\varphi(n)=180=12\varphi(m)$ Ahora tenemos que resolver $\varphi(m)=15$ . No hay soluciones.
Dejemos que $n=11\cdot m$ . Entonces $\varphi(n)=180=10\varphi(m)$ Ahora tenemos que resolver $\varphi(m)=18$ . Encontramos $m\in\{19,27,38\}$ , lo que da lugar a $n=209$ , $\color{red}{n=297}$ y $n=418$ .
Dejemos que $n=7\cdot m$ . Entonces $\varphi(n)=180=6\varphi(m)$ Ahora tenemos que resolver $\varphi(m)=30$ . Encontramos $m\in\{31,62\}$ , lo que da lugar a $\color{red}{n=217}$ y $n=434$ .
Ahora hemos llegado a los factores que $n$ puede contener múltiples veces. Por suerte, ya hemos manejado todos los demás factores primos posibles, de modo que sabemos $2$ , $3$ y $5$ son los únicos primos que dividen a $n$ . Sin embargo, tenga en cuenta que si $5\not\mid n$ entonces $5\mid\varphi(n)$ nunca sucederá, ya que ni $2$ , $2-1$ , $3$ y $3-1$ contienen un factor $5$ . Así, $5\mid n$ (ya sabíamos que $n$ podría sea divisible por $5$ pero ahora lo sabemos necesita a). Lo mismo ocurre con $3$ . Por lo tanto, quedan dos casos; $2\mid n$ o $2\not\mid n$ . En el primer caso, escribe $n=2^a3^b5^c$ y utilizar la fórmula para ver
$$180=2^23^25=\varphi(2^a3^b5^c)=2^{a-1}(2-1)3^{b-1}(3-1)5^{c-1}(5-1)=2^{a+2}3^{b-1}5^{c-1}$$
pero entonces $a=0$ ; contradicción, asumimos $a\ge 1$ . Ahora el segundo caso, $2\not\mid n$ Escribimos $n=3^b5^c$ y utilizar la fórmula para ver
$$180=2^23^25=\varphi(3^b5^c)=3^{b-1}(3-1)5^{c-1}(5-1)=2^33^{b-1}5^{c-1}$$
y vemos que esto lleva a una contradicción (ya que el lado izquierdo no es divisible por $8$ pero el lado derecho sí).
Por lo tanto, hemos comprobado todas las posibilidades y hemos encontrado todas las soluciones ( $10$ total).
