Théorème de Proth

Un article de Wikipédia, l'encyclopédie libre.

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 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.

Sommaire

[modifier] Exemples numériques

Les sept premiers nombres de Proth correspondent à la séquence 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.

[modifier] Histoire

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

[modifier] Voir aussi

[modifier] Liens externes