Factor 43361 conociendo $\phi(43361)$

Question

Se da que el número $43361$ se puede escribir como producto de dos números primos distintos $p_{1}$ y $p_{2}$. Además, asumamos que hay $42900$ números que son menores que $43361$ y primos entre sí a él. Entonces encuentra $p_{1}+p_{2}$.

Una búsqueda simple en Google arrojó que $p_{1}$ y $p_{2}$ son $131$ y $331$. Pero ¿cuál sería la forma adecuada de encontrarlos?

Answer 1

Sea $n=43361$. Sabes que $n=p_1p_2$ es el producto de dos primos distintos y también que $\phi(n)=42900$, donde $\phi$ es la función totiente de Euler. Dado que $\phi$ es multiplicativa, se sigue que $$ 42900=\phi(n)=(p_1-1)(p_2-1)=n-(p_1+p_2)+1=43362-(p_1+p_2)$$ y así $$ p_1+p_2=43362-42900=462.$$

Answer 2

Como muestra la respuesta de carmichael561, no es necesario factorizar el número para resolver el problema original. Sin embargo, la factorización se puede hacer de la siguiente manera:

Se sabe que 43361 es el producto de dos números primos, y que hay 42900 números menores que 43361 que son co-primos a él. Es decir que $ \phi(43361) = 42900 $ donde $ \phi$ es la función totient de Euler.

Además, sabemos que $ \phi(p) = p-1 $ cuando $ p $ es un número primo, y que $\phi(n) = \phi(p_1)\phi(p_2) $ cuando $n$ es un producto de los dos primos $p_1$ y $p_2$. Utilizando esto, junto con la factorización de 42900, obtenemos $$ 43361 = p_1 p_2 $$ $$ (p_1-1)(p_2-1) = 42900 = 2 \cdot 2 \cdot 3 \cdot 5 \cdot 5 \cdot 11 \cdot 13 $$ Dado que 43361 termina en 1, tanto $p_1$ como $p_2$ deben terminar en 1, y por lo tanto tanto $p_1-1$ como $p_2-1$ deben ser múltiplos de 10. Entonces tenemos que $p_1 = q_1 \cdot 10 + 1$ y $p_2 = q_2 \cdot q_3 \cdot 10 + 1$ donde $q_1, q_2,$ y $q_3$ son los factores primos restantes 3, 11 y 13.

Dado que $ 11 \cdot 10 + 1 = 111$ no es primo, $q_1$ no puede ser 11. De manera similar, dado que $11 \cdot 13 \cdot 10 + 1 = 1431$ no es primo, $q_2$ y $q_3$ tampoco pueden ser 11 y 13, y entonces $q_1$ no puede ser 3. La única posibilidad es entonces que $q_1$ sea 13, y por lo tanto $$ 43361 = (13 \cdot 10 + 1)(3 \cdot 11 \cdot 10 + 1) = 131 \cdot 331$$

Answer 3

Aquí hay un método que usé, te ayuda si no conoces la cosa del indicador de Euler. Dado que 42900 números antes de 43361 son divisibles ni por p1 ni por p2, podemos decir que 462 (incluyendo 43361) números son divisibles por p1 o p2 (siendo 43361 una excepción divisible por ambos).

digamos que x números son divisibles por p1 y y números por p2.

luego, tomando múltiplos de p1,

                        *p1, 2p1, 3p1, .....43361 es la serie*    con un total de x 
                                                                    números en ella.

sabemos por progresión aritmética que, An= A+ (N-1)D

                                43361= p1+(x-1)p1

resolviendo, obtenemos x= 43361/p1

similarmente,

                     *p2, 2p2, 3p2, .....43361 es la serie*    con un total de y 
                                                                 números en ella.
                                43361= p2+(y-1)p2

resolviendo, obtenemos y= 43361/p2

dado que x+y= 462,

                             43361/p1 + 43361/p2 = 462

                              43361(p1+p2/p1.p2) = 462

                              43361(p1+p2/43361) = 462

Resolviendo, p1+p2= 462