En théorie des nombres, le théorème de Proth est le test de primalité suivant.., spécifique aux nombres de Proth, c'est-à-dire aux entiers naturels de la forme = k2n + 1 avec 0 < k < 2n :
ou, de façon équivalente mais un peu et optimisent l'énoncé original de , en remplaçant sa condition par leur condition plus restrictive sur le symbole de Jacobi. , Theorem 102, , supposent de plus que est un nombre premier impair, la condition « () = –1 » étant alors équivalente (d'après la loi de réciprocité quadratique) à : « n'est pas un carré mod » dès que n ≥ 2 donc dès que . plus fidèle. :
Motivations Pour tout nombre premier , il existe des entiers satisfaisant cette congruence : ce sont exactement les tels que () = –1, soit la moitié des entiers non divisibles par , 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 , = (–1) = –1 = (), mais 15 est seulement semi-premier.
En 1878, François ProthUn fermier de Vaux-devant-Damloup, mathématicien autodidacte (1852-1879) : .
Mathdoc répertorie 4 articles de lui.
Voir aussi : Conjecture de Gilbreath. découvrit qu'elle est suffisante pour les nombres qui portent aujourd'hui son nom.
Ce test est utilisé entre autres. par le projet 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 « » 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 , puisqu'il n'est même pas un carré modulo 3.
Les nombres de Proth premiers sont 3, 5, 13, 17, 41, 97 ().
Notes et références en 2006. Depuis, ces deux articles ont évolué indépendamment.
Voir aussi Articles connexes
Théorème de Pocklington : une généralisation du théorème de Proth
Lien externe
Proth Proth
de:Prothsche Primzahl nl:Prothgetal