Teorema de Proth

La teorema de Proth és un test de primalidad per als números de Proth inventat per François Proth al voltant de 1878.

Esta teorema sosté que si p és un número de Proth, és dir de la forma k2ⁿ + 1 en k impar i k < 2ⁿ, llavors si per a algun número entero a:

$a^{(p-1)/2}\equiv -1modp$ (1)

llavors p és un número primo cridat cosí de Proth. Este test funciona en la pràctica perque si p és primer, el 50% dels valors de a complixen en la condició indicada dalt.

Si a és un número primo i p no és un residu quadràtic mòdul a llavors a tampoc és residu quadràtic mòdul p i es complix la condició de la teorema. En la pràctica s'usen diferents número primo menuts per a la variable a i es calcula el símbol de Jacobi fins que:

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

la qual cosa és molt més ràpit que l'exponenciación modular per a trobar el valor de a, ya que en este cas, després de calcular p mod a, es deuen realisar uns pocs càlculs usant números menors que a, mentres que en la fòrmula (1) es deuen realisar més de (ln p/ln 2) multiplicacions modular mòdul p, lo que és molt costós en temps de càlcul.

Eixemples numèrics

A continuació es mostren eixemples d'us de la teorema de Proth:

• per a p = 3, 2¹ + 1 = 3 és divisible per 3, per lo que 3 és primer.
• per a p = 5, 3² + 1 = 10 és divisible per 5, per lo que 5 és primer.
• per a p = 13, 5⁶ + 1 = 15626 és divisible per 13, per lo que 13 és primer.
• per a p = 9, que no és primer, no existix valor de a tal que a⁴ + 1 siga divisible per 9.

Els primers cosins de Proth són:

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

Esta és la seqüència A080076 d'OEIS.

A juliol de 2009, el major primer de Proth conegut és 19249 · 2^13018586 + 1, trobat pel proyecte Seventeen or Bust. Posseïx 3918990 dígits decimals i és el major primer conegut que no és de Mersenne.