Théorème de Proth

En théorie des nombres, le théorème de Proth est le test de primalité suivant[1]^,[2]^,[3], spécifique aux nombres de Proth, c'est-à-dire aux entiers naturels de la forme $p$ = k2ⁿ + 1 avec 0 < k < 2ⁿ :

Pour qu'un nombre de Proth $p$ soit premier, (il faut et) il suffit qu'il existe un entier $a$ tel que $a (p -1)/2 \equiv -1 (mod p)$

ou, de façon équivalente mais un peu[4] plus fidèle[5] :

Soient $p$ un nombre de Proth et $a$ un entier dont le symbole de Jacobi ( $a / p$ ) est égal à –1[6]. Alors, $p$ est premier si (et seulement si) $a (p -1)/2 \equiv -1 (mod p)$ [7]^,[8].

Motivations

Pour tout nombre premier $p > 2$ , il existe des entiers $a$ satisfaisant cette congruence : ce sont exactement les $a$ tels que ( $a / p$ ) = –1, soit 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 : pour $a = -1$ , $a$ ^(15–1)/2 = (–1)⁷ = –1 = ( $a / 15$ ), mais 15 est seulement semi-premier.

En 1878, François Proth[9] découvrit qu'elle est suffisante pour les nombres qui portent aujourd'hui son nom[5].

Ce test est utilisé entre autres[10] par le projet Seventeen or Bust pour tenter de démontrer la conjecture sur les nombres de Sierpiński.

Il permet de démontrer que certains nombres sont composés, sans toutefois en fournir une factorisation : on sait par exemple, grâce au test de Pépin (le cas particulier k = 1, n = une puissance de 2, a = 3), que les nombres de Fermat F₂₀ (en 1987) et F₂₄ (en 1999) ne sont pas premiers, mais on n'en connaît toujours aucun diviseur non trivial.

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 (en) » a de p sont (mod p) :

pour p = 3 : a = –1 ;
pour p = 5 : a = ±2 ;
pour p = 13 : a = ±2, ±5 et ±6.

Modulo 9 (non premier), –1 n'est pas une puissance 4^e, puisqu'il n'est même pas un carré modulo 3.

Les nombres de Proth premiers sont 3, 5, 13, 17, 41, 97, etc. (suite A080076 de l'OEIS).

Notes et références

(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) H. Riesel, Prime Numbers and Computer Methods for Factorization, Springer, 2013 (lire en ligne), p. 109-110
(en) Benjamin Fine et Gerhard Rosenberger, Number Theory: An Introduction via the Distribution of Primes, Springer, 2007 (lire en ligne), p. 231-232.
(en) Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, 3^e éd. (lire en ligne), p. 52.
Křížek, Luca et Somer 2001 et Caldwell optimisent l'énoncé original de Proth 1878, en remplaçant sa condition « $a$ non résidu de $p$ » par leur condition plus restrictive sur le symbole de Jacobi. (en) G. H. Hardy et E. M. Wright, An Introduction to the Theory of Numbers (1^re éd. 1938) [détail des éditions], Theorem 102, p. 99 sur Google Livres, supposent de plus que $a$ est un nombre premier impair, la condition « ( $a / p$ ) = –1 » étant alors équivalente (d'après la loi de réciprocité quadratique) à : « $p$ n'est pas un carré mod $a$ » dès que n ≥ 2 donc dès que $p > 3$ .
E. Proth, « Théorèmes sur les nombres premiers », Comptes rendus hebdomadaires des séances de l'Académie des sciences, Paris, t. 87,‎ 1878, p. 926 (lire en ligne).
Il existe de tels $a$ si et seulement si $p$ n'est pas un carré parfait.
(en) Michal Křížek, Florian Luca (en) et Lawrence Somer, 17 Lectures on Fermat Numbers: From Number Theory to Geometry, Springer, 2001 (lire en ligne), p. 70-71.
(en) Chris Caldwell, « Proth prime », sur Prime Pages' Glossary.
Un fermier de Vaux-devant-Damloup, mathématicien autodidacte (1852-1879) : (en) David Wells, Prime Numbers: The Most Mysterious Figures in Math, John Wiley & Sons, 2011 (lire en ligne), p. 189. Mathdoc répertorie 4 articles de lui. Voir aussi : Conjecture de Gilbreath.
(en) Chris Caldwell, « Yves Gallot's Proth.exe: an implementation of Proth's Theorem for Windows », sur Prime Pages.

Voir aussi

Articles connexes

Test de primalité de Lucas-Lehmer-Riesel (en)
Théorème de Pocklington : une généralisation du théorème de Proth

Lien externe

(en) Eric W. Weisstein, « Proth Prime », sur MathWorld

Arithmétique et théorie des nombres

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] (en) H. Riesel, Prime Numbers and Computer Methods for Factorization, Springer, 2013 (lire en ligne), p. 109-110

[2] (en) Benjamin Fine et Gerhard Rosenberger, Number Theory: An Introduction via the Distribution of Primes, Springer, 2007 (lire en ligne), p. 231-232.

[3] (en) Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, 3^e éd. (lire en ligne), p. 52.

[4] Křížek, Luca et Somer 2001 et Caldwell optimisent l'énoncé original de Proth 1878, en remplaçant sa condition « $a$ non résidu de $p$ » par leur condition plus restrictive sur le symbole de Jacobi. (en) G. H. Hardy et E. M. Wright, An Introduction to the Theory of Numbers (1^re éd. 1938) [détail des éditions], Theorem 102, p. 99 sur Google Livres, supposent de plus que $a$ est un nombre premier impair, la condition « ( $a / p$ ) = –1 » étant alors équivalente (d'après la loi de réciprocité quadratique) à : « $p$ n'est pas un carré mod $a$ » dès que n ≥ 2 donc dès que $p > 3$ .

[Proth-5] E. Proth, « Théorèmes sur les nombres premiers », Comptes rendus hebdomadaires des séances de l'Académie des sciences, Paris, t. 87,‎ 1878, p. 926 (lire en ligne).

[6] Il existe de tels $a$ si et seulement si $p$ n'est pas un carré parfait.

[7] (en) Michal Křížek, Florian Luca (en) et Lawrence Somer, 17 Lectures on Fermat Numbers: From Number Theory to Geometry, Springer, 2001 (lire en ligne), p. 70-71.

[8] (en) Chris Caldwell, « Proth prime », sur Prime Pages' Glossary.

[9] Un fermier de Vaux-devant-Damloup, mathématicien autodidacte (1852-1879) : (en) David Wells, Prime Numbers: The Most Mysterious Figures in Math, John Wiley & Sons, 2011 (lire en ligne), p. 189. Mathdoc répertorie 4 articles de lui. Voir aussi : Conjecture de Gilbreath.

[10] (en) Chris Caldwell, « Yves Gallot's Proth.exe: an implementation of Proth's Theorem for Windows », sur Prime Pages.