¿Es el primer 2014411?

Question

Quiero averiguar si el número 2014411 es primo o no.

¿Qué tipo de matemática busca herramientas y estrategia tengo?

¿Tengo que empezar desde 1 y proceder a 2014410 mientras que encontré como un divisor o cualquier otra forma eficiente se encuentra?

Answer 1

No es primordial. Lo primero que probaría es a ver si es divisible por $3$, ya que un tercio de todos los números son (asterisco, asterisco). Obviamente no es divisible por $5$. ¡Tal vez es divisible por $7$ ding ding ding! $287773$.

Si no fuera, sólo iba por unos primos más antes de pedir a un ordenador.

Answer 2

Si usted no desea utilizar una calculadora o una computadora, usted tiene que confiar en el instinto. Supongo que a la derecha y usted puede descubrir rápidamente la descomposición en factores primos de un número dado. Adivina mal y usted podría ser obligado a renunciar y pedir a un equipo.

Tomemos por ejemplo el número de $2013461$. No es divisible por ninguno de los veinte primeros números primos, pero no es el primer sí. Podría ser el cuadrado de un primo? No es, en realidad, ya que $\sqrt{2013461} \approx$ $1418.96$.

Tratando cada primer hasta el $1409$ suena como que podría tomar un tiempo muy largo con la mano. Fermat se acercó con un método que podría ayudar en este caso. Intente $\sqrt{2013461 + y^2}$ $y = 1, 2, 3, \ldots$ hasta obtener un número entero (realmente ayude a memorizar los dos últimos dígitos de los primeros cien plazas, por ejemplo, 2013465 y 2013470 obviamente no cuadrados).

Y entonces nos encontramos con la $2013461 + 10^2 = 1419^2$, lo que, Fermat nos enseñó, significa $$2013461 = 1419^2 - 10^2 = (1419 - 10)(1419 + 10) = 1409 \times 1429.$$

Este método sería de poca ayuda con $2014411$ debido a que sus factores primos, $7$, $31$, $9283$ son mucho más lejos. En casos como este, es mejor ir con la división de juicios.

En el peor de los casos, el número a tener en cuenta es el cuadrado de un primo, por ejemplo, $2036329$. Pero dado que las plazas obtener más delgado a medida que los números se hacen más grandes, tienes más probabilidades de ejecutar en el mejor de los casos de prueba de la división: que un número compuesto tiene un montón de pequeños factores primos.

Otro método que puede que te interese, algo más sofisticada, pero que también tiene su mejor caso y en el peor de los casos, es de Pollard $p - 1$ método.

Answer 3

Para números pequeños como 2014411 (si es que cabe en un 10 dígitos de la calculadora, es un número pequeño) a veces lo mejor que puedes hacer es tratar de dividir por los números primos en orden, empezando con el más pequeño de los números primos.

Como usted ya sabe, 1 no es un número primo, y usted también, ya sé que es un divisor de todos los números enteros. Para dividir 2014411 por 1 no dice nada que no sepamos ya.

Este número, 2014411, que es decimal, a la derecha? Entonces usted también sabe que no es divisible por 2, ni es divisible por 5, con sólo mirar el dígito menos significativo.

Así que tal vez es divisible por 3.

Bueno, la divisibilidad por 3, se pueden sumar los dígitos: 2 + 0 + 1 + 4 + 4 + 1 + 1 = 13, y eso no es un múltiplo de 3, entonces 3 es descartado.

No sé de ninguna inteligente pruebas de divisibilidad por 7, por lo que acabo de ir adelante y poner a mi calculadora: 2014411 dividido por 7 es 287773, por lo que está hecho, el número es compuesto.

Si 2014411 fue en realidad el primer (que no es), ¿por qué tendría que ir todo el camino hasta 2014410? La mitad de los que se 1007205, e incluso que es ir demasiado lejos. El menor factor primo de un número compuesto no puede ser más de la mitad del número.

Answer 4

Como método de búsqueda básica, recorren todos los primos entre $2$y $\sqrt{2014411}$.

La razón que usted no necesita mirar más allá de $\sqrt{2014411}$ es que si $d$ es un divisor de su número, entonces el o $d$ o $2014411/d$ debe ser menor que $\sqrt{2014411}$.