Teorema de Proth
# Teorema de Proth

El teorema de Proth es un test de primalidad para los números de Proth inventado por François Proth alrededor de 1878.

Este teorema sostiene que si p es un número de Proth, es decir de la forma $k2^n$ + 1 con k impar y k < $2^n,$ entonces si para algún número entero a:

    $a^{(p-1)/2}\equiv -1\mod {p}\,\!$ (1)

entonces p es un número primo llamado primo de Proth. Este test funciona en la práctica porque si p es primo, el 50% de los valores de a cumplen con la condición indicada arriba.

Si a es un número primo y p no es un residuo cuadrático módulo a entonces a tampoco es residuo cuadrático módulo p y se cumple la condición del teorema. En la práctica se usan diferentes números primos pequeños para la variable a y se calcula el símbolo de Jacobi hasta que:

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

lo cual es mucho más rápido que la exponenciación modular para hallar el valor de a, ya que en este caso, luego de calcular p mod a, se deben realizar unos pocos cálculos usando números menores que a, mientras que con la fórmula (1) se deben realizar más de (ln p/ln 2) multiplicaciones modulares módulo p, lo que es muy costoso en tiempo de cálculo.

## Ejemplos numéricos

A continuación se muestran ejemplos de uso del teorema de Proth:

* para p = 3, $2^1$ + 1 = 3 es divisible por 3, por lo que 3 es primo.
* para p = 5, $3^2$ + 1 = 10 es divisible por 5, por lo que 5 es primo.
* para p = 13, $5^6$ + 1 = 15626 es divisible por 13, por lo que 13 es primo.
* para p = 9, que no es primo, no existe valor de a tal que $a^4$ + 1 sea divisible por 9.

Los primeros primos de Proth son:

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

Esta es la secuencia A080076 de OEIS.

A julio de 2009, el mayor primo de Proth conocido es 19249 · $2^{13018586}$ + 1, hallado por el proyecto Seventeen or Bust. Posee 3918990 dígitos decimales y es el mayor primo conocido que no es de Mersenne.

