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 pour un nombre de Proth p, donc de la forme k2ⁿ + 1 avec k un naturel et k < 2ⁿ, 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 Proth 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

Modèle:Mathématiques