« Théorème de Proth » : différence entre les versions
Aide:crédit d'auteurs+réécriture |
m →Voir aussi : {{Palette|Classes de nombres premiers}} |
||
Ligne 29 : | Ligne 29 : | ||
*{{MathWorld|nom_url=ProthsTheorem|titre=Proth's Theorem}} |
*{{MathWorld|nom_url=ProthsTheorem|titre=Proth's Theorem}} |
||
{{Palette|Classes de nombres premiers}} |
|||
{{Portail|nombre}} |
{{Portail|nombre}} |
||
Version du 15 janvier 2016 à 22:24
En théorie des nombres, le théorème de Proth est un test de primalité spécifique aux nombres de Proth, c'est-à-dire aux entiers de la forme p = k2n + 1 avec 0 < k < 2n.
Ce théorème énonce que pour qu'un tel p soit premier, il suffit qu'il existe un entier a tel que :
Motivations
Pour tout nombre premier p > 2, il existe des entiers a satisfaisant cette congruence (exactement la moitié des entiers non divisibles par p, d'après le critère d'Euler). Mais pour un entier impair quelconque, cette condition nécessaire de primalité n'est pas suffisante : modulo 15 (pseudo-premier), 14(15–1)/2 est congru à (–1)7 = –1.
En 1878, le mathématicien François Proth découvrit qu'elle est suffisante pour les nombres qui portent aujourd'hui son nom.
Ce test est utilisé par le projet Seventeen or Bust pour tenter de démontrer la conjecture sur les nombres de Sierpiński.
Exemples numériques
Les quatre plus petits nombres de Proth sont 3, 5, 9 et 13.
Pour ceux d'entre eux qui sont premiers, les « témoins » a sont :
- pour p = 3 : a = 2 ;
- pour p = 5 : a = 2 et 3 ;
- pour p = 13 : a = 2, 5, 6, 7, 8 et 11.
Modulo 9 (non premier), les puissances quatrièmes sont congrues à 0, 1, –2 ou 4, donc jamais à –1.
Les nombres de Proth premiers sont 3, 5, 13, 17, 41, 97, etc. (suite A080076 de l'OEIS).
Voir aussi
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Proth's theorem » (voir la liste des auteurs) en 2006. Depuis, ces deux articles ont évolué indépendamment.
- (en) Eric W. Weisstein, « Proth's Theorem », sur MathWorld