Théorème de Proth

En mathématiques, le théorème de Proth en théorie des nombres est un test de primalité pour les nombres de Proth.

Ce théorème énonce que si p est un nombtre de Proth, donc de la forme k2ⁿ + 1 avec k un naturel et k < 2ⁿ, alors s'il existe un entier a tel que :

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

alors p est premier.

Ce test est pratique car si p est premier, un a choisi a environ 50% de chances de prouver la primalité de p. De plus il est remarquablement utile pour démontrer la conjecture de Sierpinski.

Les sept premiers nombres de Prots correspondent à suite A080075 de l'OEIS:

P₀ = 2¹ + 1 = 3

P₁ = 2² + 1 = 5

P₂ = 2³ + 1 = 9

P₃ = 3 × 2² + 1 = 13

P₄ = 2⁴ + 1 = 17

P₅ = 3 × 2³ + 1 = 25

P₆ = 2⁵ + 1 = 33

Exemples du théorème :

• Pour p = 3, 2¹ + 1 = 3 ce qui est divisible par 3 ; donc 3 est premier.
• Pour p = 5, 3² + 1 = 10 ce qui est divisible par 5 ; donc 5 est premier.
• Pour p = 13, 5⁶ + 1 = 15626 ce qui est divisible par 13 ; donc 13 est premier..
• Pour p = 9, qui n'est pas premier, il n'existe pas de a tel que a⁴ + 1 soit divisible par 9.

• Le mathématicien François Proth (1852 - 1879) découvrit le théorème en 1878.

• Nombre de Sierpinski
• Seventeen or Bust

• Mathworld