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 ≡ –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)7 = –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].
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 FermatF20 (en 1987) et F24 (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 4e, 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).
↑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 (1re é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.
↑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, (lire en ligne), p. 70-71.
