En teoría de números , el teorema de Proth es una prueba de primalidad para los números de Proth .
Establece [1] [2] que si p es un número de Proth , de la forma k 2 n + 1 con k impar y k <2 n , y si existe un número entero a para el cual
entonces p es primo . En este caso, p se denomina primo de Proth . Se trata de una prueba práctica, porque si p es primo, cualquier elegido una tiene una probabilidad del 50 por ciento de trabajo.
Si a es un módulo p cuadrático no residual, entonces lo contrario también es cierto y la prueba es concluyente. Tal a se puede encontrar iterando a sobre pequeños números primos y calculando el símbolo de Jacobi hasta que:
Por lo tanto, en contraste con muchas pruebas de primalidad de Monte Carlo (algoritmos aleatorios que pueden devolver un falso positivo ), el algoritmo de prueba de primalidad basado en el teorema de Proth es un algoritmo de Las Vegas , que siempre devuelve la respuesta correcta pero con un tiempo de ejecución que varía aleatoriamente.
Ejemplos numéricos
Ejemplos del teorema incluyen:
- para p = 3 = 1 (2 1 ) + 1, tenemos que 2 (3-1) / 2 + 1 = 3 es divisible por 3, entonces 3 es primo.
- para p = 5 = 1 (2 2 ) + 1, tenemos que 3 (5-1) / 2 + 1 = 10 es divisible entre 5, entonces 5 es primo.
- para p = 13 = 3 (2 2 ) + 1, tenemos que 5 (13-1) / 2 + 1 = 15626 es divisible por 13, entonces 13 es primo.
- para p = 9, que no es primo, no existe un tal que a (9-1) / 2 + 1 sea divisible por 9.
Los primeros primos de Proth son (secuencia A080076 en la OEIS ):
El Proth prime más grande conocido a partir de 2016[actualizar] es y tiene 9.383.761 dígitos. [3] Fue encontrado por Peter Szabolcs en el proyecto de computación distribuida PrimeGrid que lo anunció el 6 de noviembre de 2016. [4] También es el número principal no Mersenne más grande conocido y el número Colbert más grande. [5] El segundo primo Proth más grande conocido es, encontrado por Diecisiete o Busto . [6]
Prueba
La demostración de este teorema utiliza la prueba de primalidad de Pocklington-Lehmer y se parece mucho a la prueba de la prueba de Pépin . La prueba se puede encontrar en la página 52 del libro de Ribenboim en las referencias.
Historia
François Proth (1852-1879) publicó el teorema en 1878. [7] [8]
Ver también
- Prueba de Pépin (el caso especial k = 1, donde se elige a = 3)
- Número de Sierpinski
Referencias
- ^ Paulo Ribenboim (1996). El nuevo libro de registros de números primos . Nueva York, NY: Springer. pag. 52 . ISBN 0-387-94457-5.
- ^ Hans Riesel (1994). Números primos y métodos informáticos para la factorización (2 ed.). Boston, MA: Birkhauser. pag. 104 . ISBN 3-7643-3743-5.
- ↑ Chris Caldwell, The Top Twenty: Proth , de The Prime Pages .
- ^ "¡Descubierto el número de Colbert récord mundial!" .
- ^ Chris Caldwell, Los veinte primeros: Primes más grandes conocidos , de Prime Pages .
- ^ Caldwell, Chris K. "Los veinte primeros: mayores premios conocidos" .
- ^ François Proth (1878). "Theoremes sur les nombres premiers". Comptes rendus de l'Académie des Sciences de Paris . 87 : 926.
- ^ Leonard Eugene Dickson (1966). Historia de la Teoría de los Números . 1 . Nueva York, NY: Chelsea. pag. 92.
enlaces externos
- Weisstein, Eric W. "Teorema de Proth" . MathWorld .