Teorema de Proth

En teoría de números , el teorema de Proth es una prueba de primalidad para los números de Proth .

Se afirma ^{[1] [2]} que si p es un número de Proth , de la forma k 2 ⁿ + 1 con k impar y k < 2 ⁿ , y si existe un entero a para el cual

${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}},}$

entonces p es primo . En este caso p se llama primo de Proth . Esta es una prueba práctica porque si p es primo, cualquier a elegido tiene alrededor de un 50 por ciento de posibilidades de funcionar, además, dado que el cálculo es mod p , solo se deben tomar en consideración valores de a menores que p .

En la práctica, sin embargo, un residuo cuadrático no determinado de p se encuentra mediante un algoritmo de Euclides modificado ^{[ cita requerida ]} y se toma como el valor de a , ya que si a es un residuo cuadrático no determinado módulo p entonces la inversa también es cierta y la prueba es concluyente. Para tal a el símbolo de Legendre es

${\displaystyle \left({\frac {a}{p}}\right)=-1.}$

Por lo tanto, a diferencia de 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. Tenga en cuenta que si se elige a como un residuo cuadrático no válido como se describió anteriormente, el tiempo de ejecución es constante, salvo el tiempo empleado en encontrar dicho residuo cuadrático no válido. Encontrar dicho valor es muy rápido en comparación con la prueba real.

Ejemplos numéricos

Algunos ejemplos del teorema incluyen:

• para p = 3 = 1(2 ¹ ) + 1, tenemos que 2 ^(3-1)/2 + 1 = 3 es divisible por 3, por lo tanto 3 es primo.
• para p = 5 = 1(2 ² ) + 1, tenemos que 3 ^(5-1)/2 + 1 = 10 es divisible por 5, por lo tanto 5 es primo.
• para p = 13 = 3(2 ² ) + 1, tenemos que 5 ^(13-1)/2 + 1 = 15626 es divisible por 13, por lo tanto 13 es primo.
• para p = 9, que no es primo, no existe a tal que a ^(9-1)/2 + 1 sea divisible por 9.

Los primeros primos de Proth son (secuencia A080076 en la OEIS ):

3, 5, 13, 17, 41, 97 , 113 , 193 , 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153….

El primo de Proth más grande conocido hasta 2016 ^[actualizar]es , y tiene 9.383.761 dígitos de longitud. ^[3] Fue encontrado por Peter Szabolcs en el proyecto de computación voluntaria PrimeGrid que lo anunció el 6 de noviembre de 2016. ^[4] Es el undécimo número primo más grande conocido hasta enero de 2024, fue el primo no Mersenne más grande conocido hasta ser superado en 2023, ^[5] y es el número de Colbert más grande . ^{[ cita requerida ]} El segundo primo de Proth más grande conocido es , encontrado por PrimeGrid . ^[6] ${\displaystyle 10223\cdot 2^{31172165}+1}$ ${\displaystyle 202705\cdot 2^{21320516}+1}$

Prueba

La prueba de este teorema utiliza el test de primalidad de Pocklington-Lehmer y se parece mucho a la prueba del test 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]}

Véase también

• Prueba de Pépin (el caso especial k  = 1, donde se elige a  = 3)
• Número de Sierpinski

Referencias

1. Paulo Ribenboim (1996). El nuevo libro de registros de números primos . Nueva York, NY: Springer. p. 52. ISBN 0-387-94457-5.
2. Hans Riesel (1994). Números primos y métodos informáticos para la factorización (2.ª edición). Boston, MA: Birkhauser. pág. 104. ISBN 3-7643-3743-5.
3. Chris Caldwell, Los veinte mejores: Proth, de The Prime Pages .
4. "¡Se descubrió el número Colbert récord mundial!"
5. Chris Caldwell, Los veinte primos más grandes conocidos, de The Prime Pages .
6. Caldwell, Chris K. "Los veinte primeros: los primos más grandes conocidos".
7. François Proth (1878). "Teoremas sobre los nombres premiers". Cuentas rendus de la Academia de Ciencias de París . 87 : 926.
8. Leonard Eugene Dickson (1966). Historia de la teoría de números . Vol. 1. Nueva York, NY: Chelsea. pág. 92.

Enlaces externos

• Weisstein, Eric W. "Teorema de Proth". MathWorld .