Théorème de Proth

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 k2n + 1 avec k un naturel impair et k < 2n, s'il existe un entier a tel que :

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.

Exemples numériques[modifier | modifier le code]

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

P0 = 21 + 1 = 3
P1 = 22 + 1 = 5
P2 = 23 + 1 = 9
P3 = 3 × 22 + 1 = 13
P4 = 24 + 1 = 17
P5 = 3 × 23 + 1 = 25
P6 = 25 + 1 = 33

Exemples du théorème :

  • Pour p = 3, 21 + 1 = 3 ce qui est divisible par 3 ; donc 3 est premier.
  • Pour p = 5, 32 + 1 = 10 ce qui est divisible par 5 ; donc 5 est premier.
  • Pour p = 13, 56 + 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 a4 + 1 soit divisible par 9.

Histoire[modifier | modifier le code]

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

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

(en) Eric W. Weisstein, « Proth's Theorem », MathWorld