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 ≡ –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 ≡ –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).