Structures algébriques, topologiques, et nombres premiers

La notion de nombre premier est liée à l'étude de la structure multiplicative de l'anneau des entiers relatifs. Le théorème fondamental de l'arithmétique, basé sur le Lemme d'Euclide, élucide cette structure en assurant que tout entier se factorise en un produit de nombres premiers, de manière unique à l'ordre des facteurs près. Ce théorème permet de déterminer des notions de pgcd, ppcm, et de nombres premiers entre eux, qui sont utiles pour la résolution de certaines équations diophantiennes, notamment la caractérisation des triplets pythagoriciens.

D'autres problèmes naturels sont envisagés, comme la détermination de la proportion d'entiers premiers à un entier fixé. L'introduction de structures algébriques plus avancées permet de résoudre ce problème rapidement dans le cadre de l'arithmétique modulaire. De nombreux théorèmes classiques de nature arithmétique peuvent être énoncés, comme le petit théorème de Fermat, ou le Théorème de Wilson ; ou des théorèmes de nature plus algébrique comme le théorème des restes chinois.

Le théorème des restes chinois est un premier résultat dans l'étude des groupes abéliens finis. Il est en fait suffisant pour décrire entièrement la structure de ces groupes, qui est donc en partie liée à la décomposition en produit de facteurs premiers de leurs cardinaux. Les choses sont plus compliquées pour les groupes non abéliens, cependant, l'étude se base à nouveau sur la décomposition en facteurs premiers de leurs cardinaux, à travers la théorie de Sylow.

Les nombres premiers interviennent aussi dans les structures topologiques. Le corps des nombres rationnels admet une structure topologique habituelle, qui donne par complétion le corps des nombres réels. Pour chaque nombre premier p, une autre structure topologique peut être construite, à partir de la norme suivante : si

x =

a –– b

est un nombre rationnel non nul sous forme irréductible et que p ^α et p ^β sont les plus grandes puissances de p divisant a et b, la norme p-adique de x est p ^{β -   α} . En complétant le corps des rationnels suivant cette norme, on obtient le corps des nombres p-adiques, introduit par Kurt Hensel au début du XX^e siècle. Le théorème d'Ostrowski assure que ces normes p-adiques et la norme habituelle sont les seules sur le corps des nombres rationnels, à équivalence près.

Nombres premiers particuliers

Nombres premiers et nombres de Fermat

Les nombres premiers de la forme :

F _n = 2 ²ⁿ  + 1

sont appelés les nombres premiers de Fermat. Pierre de Fermat avait conjecturé que tous ces nombres devaient être premiers. Cependant, les seuls nombres premiers de Fermat connus sont :

• F ₀ = 2 ¹ + 1 = 3
• F ₁ = 2 ² + 1 = 5
• F ₂ = 2 ⁴ + 1 = 17
• F ₃ = 2 ⁸ + 1 = 257
• F ₄ = 2 ¹⁶ + 1 = 65 537

Le nombre de Fermat F ₅ n’est pas premier : il est divisible par 641. Il s'agit du premier contre-exemple à cette conjecture de Fermat, découvert par Euler en 1732.

Le plus grand nombre premier connu et nombres premiers de Mersenne

Les nombres premiers de la forme 2^p-1, où p est lui-même un nombre premier, sont appelés nombres premiers de Mersenne. Il existe un test efficace pour déterminer si un nombre de cette forme est ou non premier : le test de primalité de Lucas-Lehmer. Les grands nombres premiers sont donc souvent cherchés sous cette forme, et le plus grand Nombre premier connu est 2^{32 582 657}-1, il comporte 9 808 358 chiffres en écriture décimale. Il s'agit du 44e nombre premier de Mersenne connu (M_{32 582 657}) et a été annoncé le 4 septembre 2006 grâce aux efforts d'une collaboration qui porte le nom de GIMPS.

L'Electronic Frontier Foundation offre un prix de calcul coopératif d'un montant de 100 000 USD pour la découverte d'un nombre premier d'au moins dix millions de chiffres décimaux, afin d'encourager les internautes à contribuer à la résolution de problèmes scientifiques par le Calcul distribué.

Grands nombres premiers illégaux

Quelques-uns des plus grands nombres premiers n'ayant pas de forme particulière (c'est-à-dire ne pouvant s'écrire à l'aide d'une formule simple comme les nombres premiers de Mersenne) ont été trouvés en prenant un morceau de données binaires pseudo-aléatoires, et en les convertissant en un nombre n, en multipliant par 256^k où k est un certain entier strictement positif, et en cherchant des nombres premiers éventuels dans l'intervalle .

Pour lancer un coup publicitaire contre l'acte de copyright Digital Millennium et les autres implémentations du traité de copyright WIPO, quelques personnes ont appliqué cette méthode à différentes formes variées du code DeCSS, en créant l'ensemble des nombres premiers illégaux. De tels nombres, lorsqu'ils sont convertis en binaire et exécutés dans un programme informatique, enfreignent la loi en vigueur dans une ou plusieurs juridictions des États-Unis d'Amérique.

Calcul des nombres premiers

Crible d'Eratosthène et algorithme par essais de division

Les premiers algorithmes pour décider si un nombre est premier consistent à essayer de le diviser par tous les nombres inférieurs à sa racine carrée : s'il est divisible par l'un d'entre eux, il est composé, et sinon, il est premier. Cependant, l'algorithme déduit de cette formulation peut être rendu plus efficace : il suggère beaucoup de divisions inutiles, par exemple, si un nombre n'est pas divisible par 2, il est inutile de tester s'il est divisible par 4. En fait, il suffit de tester sa divisibilité par tous les nombres premiers inférieurs à sa racine carrée.

Le crible d'Ératosthène est une méthode reposant sur cette idée ; il fournit en fait la liste de tous les nombres premiers inférieurs à une valeur fixée n :

• On forme la liste des entiers de 2 à n,
• On prend le premier nombre de cette liste (non encore barré), soit en premier lieu 2,
• On barre tous les entiers multiples du nombre retenu, en commençant par son carré (puisque 2*i, 3*i, ...(i-1)*i ont déjà été barrés en tant que multiples de 2,3,...)
• On répète cette dernière opération en considérant le prochain nombre non barré.
• Dès qu'on en est à chercher les multiples des nombres excédant la racine carrée de n, on termine l'algorithme.

Les nombres qui restent non barrés à la fin du processus sont les nombres premiers inférieurs à n. Cet algorithme est de complexité algorithmique exponentielle.

Le crible d'Ératosthène fournit donc plus d'information que la seule primalité de n. Si seule cette information est souhaitée, une variante parfois plus efficace consiste à ne tester la divisibilité de n que par des petits nombres premiers dans une liste fixée au préalable (par exemple 2, 3 et 5), puis par tous les nombres entiers inférieurs à la racine carrée de n qui ne sont divisibles par aucun des petits nombres premiers choisis ; cela amène à tester la divisibilité par des nombres non premiers (par exemple 49 si les petits premiers sont 2, 3 et 5 et que n excède 2500), mais un choix d'un nombre suffisant de petits nombres premiers doit permettre de contrôler le nombre de tests inutiles effectués.

Autres algorithmes

Une variante du crible d'Ératosthène est le Crible de Sundaram qui consiste à former les produits de nombres impairs. Les nombres qui ne sont pas atteints par cette méthode sont les nombres premiers impairs, c'est-à-dire tous les nombres premiers sauf 2. Par ailleurs, à partir du crible d'Ératosthène, la factorisation de l'entier n peut facilement être trouvée. D'autres méthodes plus générales concernant ce problème plus difficile que simplement déterminer la primalité sont aussi appelées méthodes de crible, la plus efficace étant actuellement le crible général des corps de nombres.

Les algorithmes présentés précédemment ont une complexité trop importante pour pouvoir être menés à terme, même avec les ordinateurs les plus puissants, quand n devient grand.

Une autre classe d'algorithme consiste à tester l'entier n pour une famille de propriétés vérifiées par les nombres premiers : si une propriété de cette famille n'est pas vérifiée pour n, alors il est composé ; en revanche, le fait qu'une des propriétés de la famille soit vérifiée pour n ne suffit pas à assurer la primalité. Toutefois, si cette famille est telle qu'un nombre composé ne vérifie pas au moins la moitié des propriétés en jeu, alors un nombre n qui vérifie k propriétés de la famille aura une probabilité supérieure à 1-2^-k d'être premier : il est déclaré probablement premier à partir d'une valeur de k à choisir par l'utilisateur ; un nombre déclaré probablement premier, mais qui n'est pas premier est appelé nombre pseudo-premier. Un test basé sur ce principe est appelé test probabiliste de primalité. De tels tests reposent souvent sur le petit théorème de Fermat, amenant au test de primalité de Fermat, et à ses raffinements : le test de primalité de Solovay-Strassen et celui de Miller-Rabin, qui sont des améliorations, car ils admettent moins de nombres pseudo-premiers.

L'algorithme AKS mis au point en 2002 permet de déterminer si un nombre donné N est premier en utilisant un temps de calcul polynomial.

Les formules menant aux nombres premiers

De nombreuses formules ont été cherchées pour générer les nombres premiers. Le plus haut niveau d'exigence serait de trouver une formule qui à un entier n associe le n ^e nombre premier. De manière un peu plus souple, on peut se contenter d'exiger une fonction f qui à tout entier n associe un nombre premier et telle que chaque valeur prise ne le soit qu'une fois. Enfin, on souhaite que la fonction soit calculable en pratique. Par exemple, le théorème de Wilson assure :

Si p est un nombre premier alors (p-1)! ≡ -1 mod p

et la fonction :

f( n) = 2 +( {2( n!)} mod(n+1))

donne tous les nombres premiers, uniquement les nombres premiers, et seule la valeur 2 est prise plusieurs fois. Cependant, le calcul de la factorielle est rédhibitoire.

La recherche de telles fonctions a notamment été menée parmi les fonctions polynômes, menant au résultat négatif qu'un polynôme à coefficients complexes, même à plusieurs indéterminées, dont les valeurs aux entiers naturels ont pour valeur absolue des nombres premiers, est un polynôme constant. La recherche de polynômes vérifiant une propriété plus faible s'est développée à partir de la notion d'ensemble diophantien de nombres entiers ; de tels ensembles peuvent être caractérisés comme les ensembles de valeurs prises par un polynômes (à plusieurs variables) à coefficients entiers en les entiers strictement positifs. Un travail mené dans les années 1960 et 1970, notamment par Putnam, Matijasevic, Davis, Robinson, permet de montrer que l'ensemble des nombres premiers est diophantien, conduisant à l'existence de polynôme qui prennent aux valeurs entières positives des variables comme valeurs les nombres premiers. L'écriture de divers polynômes explicites a ensuite été possible, avec différents nombres de variables, et divers degrés. Notamment, le polynôme suivant, de degré 25 à 26 variables (de a à z), a été déterminé par Jones, Sato, Wada et Wiens en 1976 :

( 1

− ²

− ²

− ²

− ²

− ²

− ²

− ²

− ²

− ²

− ²

− ²

− ²

− ²

− ²

) . (k + 2)

La notion d'ensemble diophantien s'est plus généralement développée à partir des problèmes posés par le dixième problème de Hilbert sur les équations diophantiennes.

Répartition des nombres premiers

Infinité des nombres premiers

Euclide a démontré dans ses Éléments (proposition 20 du livre IX) que les nombres premiers sont en plus grande quantité que toute quantité proposée de nombres premiers. Autrement dit, il existe une infinité de nombres premiers. La démonstration d'Euclide repose sur la constatation qu'une famille finie p₁,...,p_n de nombres premiers étant donnée, tout nombre premier divisant le produit des éléments de cette famille augmenté de 1 est en dehors de cette famille (et un tel diviseur existe, ce qui est aussi prouvé par Euclide).

D'autres démonstrations de l'infinité des nombres premiers ont été données. La preuve d'Euler utilise le Produit eulérien:

∀ x ∈ ]1,+ ∞

Cette section est vide, pas assez détaillée ou incomplète. Votre aide est la bienvenue ! Dans un anneau on appelle Idéal premier tout sous-anneau absorbant pour la multiplication. On observe un équivalent du théorème fondamental de l'arithmétique (l'existence de décomposition en produit de nombres premiers), voir Théorème des restes chinois. Article détaillé : . Exemples Dans le cas de l'anneau Z on retrouve que chaque sous-anneau engendré par un nombre premier est un idéal premier et réciproquement. Dans le cas de l'anneau Q les idéaux premiers correspondent aux polynômes premiers. Questions ouvertes Il y a beaucoup de questions ouvertes sur les nombres premiers. Par exemple : La conjecture de Goldbach : tout nombre pair strictement supérieur à 2, peut-il s'écrire comme somme de deux nombres premiers ? conjecture des nombres premiers jumeaux : un couple de nombres premiers jumeaux est une paire de nombres premiers dont la différence est égale à 2, comme 11 et 13. Existe-t-il une infinité de jumeaux premiers ? Toute Suite de Fibonacci contient-elle une infinité de nombres premiers ? Existe-t-il une infinité de nombres premiers de Fermat ? Y a-t-il une infinité de nombres premiers de la forme n² + 1 ? Y a-t-il une infinité de nombres premiers factoriels ? Y a-t-il une infinité de nombres premiers primoriels ? Soit la suite, dite d'Euclide-Mullin, de premier terme u1=2 et telle que le terme un soit le plus petit nombre premier diviseur du produit des termes ui, pour i<n, augmenté de 1. Tous les nombres premiers apparaissent-ils dans cette suite ? C'est une conjecture de Daniel Shanks. == Citations == *« Un nombre premier est un nombre qui ne se casse pas quand on le laisse tomber par terre. » Paul Erdős *« Les mathématiciens ont tâché jusqu'ici en vain de découvrir quelque ordre dans la progression des nombres premiers, et l'on a lieu de croire que c'est un mystère auquel l'esprit humain ne saura jamais pénétrer. Pour s'en convaincre, on n'a qu'à jeter les yeux sur les tables des nombres premiers que quelques-uns se sont donné la peine de continuer au-delà de cent mille et l'on s'apercevra d'abord qu'il n'y règne aucun ordre ni règle. » Euler. Références Notes .. Bibliographie (en) Henri Cohen, A course in computational algebraic number theory Référence moderne sur les méthodes effectives en théorie des nombres. Jean-Paul Delahaye, Merveilleux nombres premiers, Éditions Belin - Pour la Science, 2000 - ISBN 2701150175 William John Ellison, en collaboration avec Michel Mendès France, Les nombres premiers Livre très clair, comme introduction à la théorie analytique des nombres. (en) Fernando Gouvêa, p-adic Numbers : An Introduction Introduction aux nombres p-adiques à la portée d'un large public, tournée vers des objectifs analytiques. (en) G. H. Hardy et E. M. Wright An Introduction to the Theory of Numbers Un grand classique d'introduction à la théorie des nombres, qui couvre les sujets de base (congruences), introduit les méthodes algébriques par l'exemple (entiers de Gauss, de Kronecker), et donne une démonstration du théorème des nombres premiers. Paulo Ribenboim, The new book of big prime number records, Springer, 1996, ISBN 0387944575 Gérald Tenenbaum et Michel Mendès-France, Les Nombres Premiers, Que sais-je, PUF, 2000, ISBN 2130483992 Voir aussi Notion de Nombre Ensembles usuels Extensions ℕ ensemble des entiers naturels ℤ groupe des entiers relatifs D ensemble des décimaux ℚ corps des rationnels ℝ corps des réels ℂ corps des complexes ℍ algèbre des quaternions O algèbre des octonions S algèbre des sédénions autres hypercomplexes ℚp corps des p-adiques hyperréels et superréels ordinaux et cardinaux surréels et pseudoréels scriptstyleN ⊂ Z ⊂ D ⊂ Q ⊂ R ⊂ C Propriétés particulières pair ou impair • premier ou composé • carré • parfait positif ou négatif • dyadique • irrationnel algébrique ou transcendant • imaginaire pur Nombre de Liouville • normal • univers constructible • calculable • transfini • Infiniment petit Exemples d'importance historique π : √2 : φ : 0 : i : e : ℵ0 : constante d'Archimède racine carrée de deux Nombre d'or Zéro Unité imaginaire constante de Neper Aleph-zéro (≈ 3,141592654…) (≈ 1,414213562…) (≈ 1,618033989…) de carré valant −1 (≈ 2,718281828…) premier cardinal infini autres constantes mathématiques Notions connexes Chiffre • Numération • fraction • opération • calcul • Algèbre Arithmétique • Suite d'entiers • ∞ Infini • Chiffre significatif Théorème des nombres premiers Liens externes (en) Page d'Andrew Granville. La partie « Expository lectures » a été en particulier utilisée. (en) [#] Page des nombres premiers sur l'encyclopédie électronique des suites entières. (fr) Une grande liste des nombres premiers (jusqu'à 1 000 000 000)