Sobre factorización y enteros dado el valor de su Euler ' función φ.

Question

En una prueba de ingreso para la admisión en un curso de licenciatura en matemáticas de la siguiente pregunta.

Considerar el número de $110179$ este número se puede expresar como un producto de dos números primos $p$$q$, también El número de enteros menos de lo que es y relativamente primos son de $109480$. Encontrar el valor de $p+q$ y también mencionan que los valores de $p$ $q$ en su respuesta.

Lo que yo sabía- sabía que el número de enteros menos de $n$ y relativamente primer a es $\phi(n)$ llamado de Euler totient función y el hecho de que es multiplicativa.

Lo que quiero saber- ¿Cómo es esto $ \phi(n)$ tiene nada que ver con el factoring $n$?. Y también por supuesto la solución del problema el uso de las matemáticas.(Escribí un trozo de código para averiguar los factores, pero por supuesto sin $\phi(110179))$.

Answer 1

$\Phi(n)$ está relacionado con los factores primos de a $n$ debido a (ejercicio: probar esto) $$\Phi(n) = n(1 - 1/p_1)(1 - 1/p_2)\dotsm (1 - 1/p_k)$$ donde $n = p_1^{a_1}p_2^{a_2}\dotsm p_k^{a_k}$. Incluso si no son recíprocos de los números primos, el producto funciona a ser un número entero.

Ya que usted sabe que $n = 110179 = pq$, usted también sabe que $\Phi(110179) = 110179(1 - 1/p)(1 - 1/q)$ y esto se da a la ser $109480$. Simplificando un poco, hemos $$\frac{109480}{110179} = 1 - \frac{1}{p} - \frac{1}{q} + \frac{1}{pq} \\ \implica 109480 - 110179 = 1 - (p + q) \\ \implica que p + q = 700$$

Ahora que usted tiene la suma y el producto de $p$$q$, trabajando fuera de los valores es capaz de resolver una simple ecuación cuadrática, dando a $p = 239$$q = 461$.