La solución de $\phi(n)=84$

Question

Ok, realmente necesito algo de ayuda para entender esto porque mi cerebro no está funcionando en el momento o me estoy rompiendo en matemáticas y tengo una llamativa la sospecha de que uno de esos es más probable.

De todos modos, aquí está mi proceso. WolframAlpha me dice que hay 12 entero de soluciones, que son todos los $^+_-n$ así que vamos a decir que hay 6 de ellos. Son como sigue: $129, 147, 172, 196, 258, 294$

Ok, así que aquí está cómo he tratado de resolverlo. $n$ se parece a esto ${\prod_{i=1}^kp_i^{\alpha_i}}$. Y $\phi(n)=n\prod_{p\vert n}(1-\frac{1}{p})$. Así que conecte $n$ y obtener una ecuación como esta:

$\prod_{i=1}^k p_i^{\alpha_i-1}(p_i-1)=84$

Ahora, la solución para $n$ DEBE ser equivalente a la solución de $p_i, \alpha_i$, ¿verdad?

Entonces, empecé a ir a través de las posibles valores de $k$ y estoy interesado en el caso de $k=2$.

Esto significa que $n$ tiene dos factores primos, por lo que se ve como $p_1^{\alpha_1}p_2^{\alpha_2}$, y la ecuación es:

$p_1^{\alpha_1-1}(p_1-1)p_2^{\alpha_2-1}(p_2-1)=84$

Ok. Aquí está mi problema. Factoring $84$, obtenemos $2\times2\times3\times7$

Para intentar ver un patrón. La primera solución que se me ocurrió es $p_1=7, \alpha_1=2, p_2=2, \alpha_2=2$. Luego he seguido la misma lógica que me llevó a la solución, pero no encuentro ninguna más, así que a la conclusión de que las soluciones deben ser como los valores más altos de $k$. Pero luego me factorizada $172$ y vio que también había sólo dos números primos. También se ajusta el patrón. Así que me di cuenta de que podía obtener en el producto como resultado de $p^0$ y siguiendo ese patrón, rellenando el resto de los factores, me encontré con la $129$ solución.

Sin más, el siguiente debe ser de al $k=3$. NOPE. $147$ también factores en sólo 2 de los números primos. Así que ahora estoy realmente en una señorita. Es allí una manera más eficaz para iterar sobre todos los de estas combinaciones?

Answer 1

Mirar a las 7. Dos posibilidades:

• $7|(p-1)$ $p|n$: por lo tanto $p = 14k+1 \in \{ 29, 43\}$ (los otros son demasiado grandes).
• Si $p=29$, $\phi(n) = 28\times 3 = (29-1)(3)$. 3 tiene que haber algo de $(p-1)p^{a-1}$ pero $p=4$ no es primo.
• Si $p=43$, usted tiene la solución a $\phi(n) = 42\times 2\implies n = 43\times 3$ o $n = 43\times 2^2$.
• De lo contrario,: $7|n$. $\phi(n) = 6\times 7\times 2\implies n= 7^2\times 3$ o $n= 7^2\times 2^2$.

Yo he usado ese $\phi(n) = 2\implies n\in\{3,4\}$.

Answer 2

  84         129 = 3 * 43
  84         147 = 3 * 7^2
  84         172 = 2^2 * 43
  84         196 = 2^2 * 7^2
  84         258 = 2 * 3 * 43
  84         294 = 2 * 3 * 7^2

Veo, usted tuvo.

Supongo que lo que me gustaría destacar es este: $\phi$ es multiplicativo. Por lo que es determinado por su comportamiento en el primer poderes. Siguiente, $\phi (p^k)$ es siempre divisible por $p-1.$, por tanto, estamos obligados a tener el $(p-1) | 84,$ tan fuera de la lista de números con $\phi(n) | 84,$

   1           2 = 2
   2           3 = 3
   2           4 = 2^2
   4           5 = 5
   2           6 = 2 * 3
   6           7 = 7
   4           8 = 2^3
   6           9 = 3^2
   4          10 = 2 * 5
   4          12 = 2^2 * 3
  12          13 = 13
   6          14 = 2 * 7
   6          18 = 2 * 3^2
  12          21 = 3 * 7
  12          26 = 2 * 13
  12          28 = 2^2 * 7
  28          29 = 29
  12          36 = 2^2 * 3^2
  12          42 = 2 * 3 * 7
  42          43 = 43
  42          49 = 7^2
  28          58 = 2 * 29
  42          86 = 2 * 43
  42          98 = 2 * 7^2
  84         129 = 3 * 43
  84         147 = 3 * 7^2
  84         172 = 2^2 * 43
  84         196 = 2^2 * 7^2
  84         258 = 2 * 3 * 43
  84         294 = 2 * 3 * 7^2

los números primos permitidos son 2,3,5,7,13,29,43, supongo que eso es todo. Algunos evidentes primer poderes que deben ser consideradas como alternativas a sólo primos. Oh, 13 no acostumbrarse, porque entonces usted necesita $\phi(something) = 21,$ $\phi$ nunca es impar a menos que sea exactamente $1.$, 9 no acostumbrarse, creo que no hay ningún número con $\phi = 14,$ no recuerdo por qué, pero la gente pregunta que aquí bastante a menudo, así que usted puede encontrar una respuesta en el MSE.. El poco acerca de extraño es bastante fácil, si hay cualquier extraño principal factor de $p,$ $(p-1)$ es incluso. Así que todo lo que queda es la de los poderes de $2.$