En teoría de números, el teorema de Proth es una prueba de primalidad para los números de Proth .
El teorema de Proth dice:
Si p es un número Prota de la forma , donde k es impar y , entonces p es primo (llamado Prota primo ) si y solo si para algún no residuo cuadrático a se hace la comparación: |
(a) Sea p primo. Entonces, para cualquier no residuo cuadrático a : por el criterio de Euler .
(b) Sea para algún no residuo cuadrático a . Usamos el criterio de Pocklington , donde . Entonces es el único divisor primo . Comprobemos el cumplimiento de las condiciones del criterio:
Como se cumple la condición, n es primo. [una]
El teorema de Proth se puede utilizar para probar la primalidad de los números de Proth. El algoritmo de prueba probabilística basado en el teorema es el siguiente: Se selecciona aleatoriamente un número entero tal que y calcula . Los siguientes resultados son posibles:
El resultado (4) es la razón por la cual la prueba es probabilística. En el caso (1) , es un módulo cuadrático sin residuos . El procedimiento se repite hasta que se establece la simplicidad. Si es primo, entonces la prueba lo confirmará con una probabilidad en una iteración, ya que el número de módulos cuadráticos sin residuos es exactamente . [2]
Los primos Prot forman una secuencia:
3 , 5 , 13 , 17 , 41 , 97 , 113 , 193 , 241 , 257 , 353 , 449, 577, 641, 673, 769, 929, 1153… ( secuencia OEIS A080076 )En mayo de 2017, el proyecto Primegrid ha encontrado el primo más grande conocido de Proth, 10223 2 31172165 + 1 . Tiene 9383761 dígitos decimales y es el número primo no Mersenne más grande conocido . [3]
Lema. Deje para algunos primos l y . Sea la potencia de un número primo, donde . Si y , entonces n es primo .
Prueba. es un divisor , entonces . Si , entonces es una contradicción. Por lo tanto , y es simple.Teorema (teorema de Proth generalizado). Deje para algunos números primos y enteros . deja _ Si y para algún número entero , entonces es primo.
La demostración del teorema generalizado se puede encontrar en Sze [4] .
François Prot (1852-1879) publicó el teorema alrededor de 1878.