title: Teorema de Proth
text: # 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.
  
  # Teorema de Proth
  ## 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.