Formules pour les nombres premiers - Définition

Introduction

En mathématiques, la recherche de formules exactes donnant tous les nombres premiers (ou même donnant uniquement des nombres premiers) s'est généralement avérée vaine, ce qui a amené à se contenter de formules approchées. Cette page recense les différents résultats obtenus.

Formules exactes simples

Le rêve d'une formule exacte et simple donnant le n-ème nombre premier p_n, ou le nombre de nombres premiers , π(n), s'est très tôt heurté à l'extrême irrégularité de leur répartition, ce qui a amené à se contenter d'objectifs moins ambitieux. Mais même la recherche de formules ne donnant que des nombres premiers s'avère assez décevante ; ainsi, il est facile de montrer qu'il n'existe aucune fonction polynôme non constante P(n) qui ne prendrait que des valeurs premières pour tous les entiers n, ou même pour presque tous les n ; en fait, on ignore même s'il existe un polynôme de degré > 1 qui prenne une infinité de valeurs premières.

C'est ce qui explique l'intérêt de la remarque d'Euler : le polynôme quadratique est premier pour tous les nombres entiers positifs inférieurs à 40 (bien sûr, si n est un multiple de 41, P(n) sera lui aussi un multiple de 41, et donc non premier). D'ailleurs, 41 est le plus grand entier A pour lequel le polynôme n² + n + A est premier pour tous les n inférieurs à A − 1 ; c'est un résultat difficile utilisant la théorie du corps de classes, et qui n'a été démontré qu'en 1967.

D'autres formules utilisant des fonctions plus générales, telle celle de Mersenne, avaient été envisagées, la plus célèbre étant celle conjecturée par Fermat : est premier pour tout n. Hélas, si ces nombres (appelés désormais nombres de Fermat) sont bien premiers pour , Euler découvrit que le sixième, F₅, est divisible par 641, ruinant la conjecture ; actuellement, on pense au contraire que F_n est toujours composé dès que n > 4, et, dans le même genre, on ne connait que la formule théorique de Mills pour ne donner que des nombres premiers... si ce n'est que, justement, elle est purement théorique, comme on le verra dans la dernière section.

Des formules exactes... mais sans intérêt pratique

Malgré les remarques précédentes, il est cependant possible d'obtenir des formules exactes d'apparence simple. Ainsi, le théorème de Wilson permet facilement de montrer que la fonction produit tous les nombres premiers, et seulement eux, quand n parcourt tous les entiers positifs : f(n) = 2 si n + 1 est composé, et f(n) = n + 1 si n + 1 est premier. Le recours à la fonction mod n'est pas gênant, car on sait la calculer rapidement ; en revanche, la factorielle de n prend rapidement des valeurs bien trop grandes pour être utilisables en pratique ; de plus, cette fonction ne donne pas réellement π(n), mais teste seulement si n est premier ou non, et comme elle demande environ n opérations élémentaires pour être calculée, elle est à cette fin beaucoup plus inefficace que la simple méthode de division par tous les entiers , elle-même bien moins rapide que les meilleurs tests de primalité actuellement connus.

D'autres formules donnant directement p_n ou π(n) peuvent été construites à partir de f ; ainsi, on a, en utilisant la fonction partie entière :

;

mais ces formules sont, bien évidemment, encore moins utilisables que celle donnant f.

Une autre approche, plus prometteuse et n'utilisant pas le théorème de Wilson, consiste essentiellement à "simuler" le crible d'Ératosthène, ou les formules qu'on peut en déduire, comme la formule d'inclusion-exclusion de Legendre ; c'est le terrain de prédilection de nombreux amateurs, ainsi, les formules suivantes ont été déterminées en 2000 par un enseignant espagnol, S.M.Ruiz  :

et

on remarquera le nombre important de sommations dans ces formules, qui fait qu'elles seraient, elles aussi, peu utilisables en pratique ; de bien meilleures méthodes de calcul exact de π(n) et p_n, qu'on trouvera détaillées dans l'article consacré à ces fonctions, restent d'ailleurs relativement inefficaces.

Compte tenu des remarques de la première section, l'existence de polynômes à plusieurs variables ne prenant que des valeurs premières paraissait peu vraisemblable, aussi les travaux de Matiyasevich (en 1970), montrant que toute relation diophantienne pouvait être "codée" par un tel polynôme, provoquèrent une véritable surprise. Il est même possible de donner des exemples explicites de ce résultat ; ainsi, le monstrueux polynôme suivant (comportant 26 variables, et de degré 25):

(k+2)[1 – (wz+h+j–q)² – [(gk+2g+k+1)(h+j) + h – z]²– (2n+p+q+z–e)² – [16(k+1)³(k+2)(n+1)² + 1 – f²]²– [e³(e+2)(a+1)² + 1 – o²]² – [(a²–1)y² + 1 –x²]²– [16r²y⁴(a²–1) + 1 – u²]²

– [((a+u²(u²–a))²–1)(n+4dy)² + 1 – (x+cu)²]² –[n+l+v–y]²– [(a²–1)l² + 1 – m²]² – [ai+k+1–l–i]² – [p + l(a–n–1) + b(2an+2a–n²–2n–2) – m]² – [q+ y(a–p–1) + s(2ap + 2a – p² – 2p – 2) – x]²

– [z + pl(a–p) + t(2ap – p² – 1) – pm]²]

a, pour ensemble de valeurs positives, exactement l'ensemble des nombres premiers. Mais on peut commencer à se demander s'il s'agit bien encore là de "formules" ; dans un ordre d'idées assez proche, Conway a défini une généralisation du problème de Syracuse, qui le transforme en un langage de programmation, FRACTRAN ; le texte suivant :

correspond, pour ce langage, à un programme qui produit, dans l'ordre, la suite des nombres premiers, ce qui peut être considéré comme une formule au moins aussi élégante que celles qui précédent.

Enfin, Mills a montré qu'il existe des nombres réels M tels que pour tout entier n, la partie entière de soit un nombre premier. Le plus petit M ayant cette propriété, la constante de Mills, est d'ailleurs connu avec une bonne précision ... qui s'avèrerait tout aussi illusoire pour calculer réellement de grands nombres premiers, ne serait-ce que parce que la taille de devient rapidement bien supérieure à tout ce qu'un ordinateur peut contenir (pour stocker p(25), on a déjà besoin d'un téraoctet).