Encontrar todos los valores de n, tal que $ \varphi (n) = 12 $

Question

No me he roto esta muy lejos. He llegado a la conclusión de que existen infinitos valores de n, donde existe 12 coprimes a n. Desde que existen infinitos números primos y los números primos son coprimes a cualquier número menor que la primera, puedo llegar a esa conclusión. Puede alguien me paran y me dicen donde voy mal o cómo acercarse a este.

He usado el teorema:

$ \varphi (n) = ((1-\frac{1}{p_{1}})...(1-\frac{1}{p_{k}})) $

Pero para calcular estos valores no se necesita escribir un programa para ejecutar las ranuras en todos estos primos?

Answer 1

La elaboración de James47 la respuesta que él pidió: Escribir $n = q_1 \cdots q_k$ $q_i = p_i^{n_i}$ $p_i$ distintas. Entonces $$\phi(n) = \phi(q_1) \cdots \phi(q_k) = p_1^{n_i - 1} \cdots p_k^{n_k - 1}(p_1 - 1) \cdots (p_k - 1) = 12.$$ Es sólo cuestión de la inclusión de la $(q_1, \dots, q_k)$ satisfacer la ecuación anterior. En particular, cada una de las $p_i^{n_i - 1}$ $p_i - 1$ debe dividir $12$, lo que limita las posibilidades a$q_i = 2, 2^2, 2^3, 3, 3^2, 5, 7,$$13$. Eso debería ser suficiente fuerza bruta el resultado.

Answer 2

Su conclusión es equivocada. Por ahora, olvídate de la fórmula que involucra recíprocos.

Si $p$ es primo, entonces $\phi(p) = p - 1$. Dado $k > 1$,$\phi(p^k) = p^{k - 1}(p - 1)$. Además, esta función es multiplicativo, lo que significa que $\phi(pq) = \phi(p) \phi(q)$ si $\gcd(p, q) = 1$. Además, sólo hay dos excepciones a $\phi(m) > \sqrt{m}$.

Así, para encontrar todas las soluciones para $\phi(n) = 12$ usted necesita para averiguar el finito conjunto de maneras de expresar $12$ como un producto de números $1$ menos que un primer y/o los poderes de un primer times $1$ menos que el primer.

• $12$ es uno menos que el primer, $13$.
• $12 = 2 \times 6$, e $21 = 3 \times 7$.
• $12 = 1 \times 12$. Esto puede parecer obvio, y sin sentido, hasta que nos fijamos en $26 = 2 \times 13$
• $28 = 2^2 \times 7$ corresponde a $12 = 2 \times 6$ porque $\varphi(4) = 2$
• $36 = 2^2 \times 3^2$ corresponde también a $12 = 2 \times 6$ porque $\varphi(9) = 6$
• $42 = 2 \times 3 \times 7$ corresponde también a $12 = 2 \times 6$

y usted no necesita mirar oh cielos, no tengo tiempo para terminar esta respuesta alguien me hace el favor?

EDIT: Robert Sopa aquí. He completado la tabla que explica la correspondencia entre los valores de $n$ tal que $\varphi(n) = 12$ y productos que dan 12. La verdad, no sé donde Jim se va a ir con esas cosas sobre $\varphi(n) > \sqrt{n}$ (a pesar de que sé que los dos excepciones: 2 y 6).

Answer 3

Primero de todo, tenga cuidado, usted se olvidó de un término en la expresión de $\varphi{(n)} = n \left(1-\dfrac{1}{p_{1}}\right)...\left(1-\dfrac{1}{p_{k}}\right)$ : hay un $n$.

Desarrollando la primera fórmula, si $n = p_1^{\alpha_1}...p_n^{\alpha_n}$, $\varphi{(n)} = p_1^{\alpha_1-1}(p_1-1)...p_n^{\alpha_n-1}(p_n-1).$

Si $\varphi{(n)} = 12 = 2*2*3$, sólo tenemos que encontrar todas las posibilidades para el$p_i$$\alpha_i$.

Si $3$ está sola, es una $p_i^{\alpha_i-1}$ plazo (de lo contrario sería una $(p_i-1)$ plazo, y $p_i$$4$, que no es primo). Va, inevitablemente, con un $(p_i-1)$ plazo de $2$.

Sólo tenemos un $2$ a la izquierda. Por lo tanto el único posible rival para él es un $(2*1)$ desde un $(1*2)$ implicaría otro $p_i = 3$. Este rendimientos $n = 36$ y es la única posibilidad con la $3$ no están emparejados.

$3$ puede ser emparejado con un $2$ para formar un $6$. Esta $6$ es, obviamente, una $(p_i-1)$ plazo, por lo $p_i$$7$, con multiplicidad $1$ porque $7$ no está en nuestra lista de factores. La última $2$ puede existir en la forma $(2*1)$ o $(1*2)$. Este rendimientos $n = 28$ $21$ respectivamente. No olvidemos la posible $(1*1)$ que puede suceder en el segundo caso desde $2$ no es un factor determinante en este caso. Esto nos da $n=42$.

Finalmente, puede existir un solitario $3*2*2$ plazo. Una vez más desde $12$ no es primo, es un $(p_i-1)$ plazo, con $p_i$ $13$ con multiplicidad $1$. Pero esto no ha terminado todavía. Incluso si no tenemos los factores de la izquierda, podemos tener un $(1*1)$ plazo, como antes. Si es que hay, a continuación,$n = 26$. De lo contrario, $n=13$.

La lista definitiva es : $13, 21, 26, 28, 36, 42$.