Nombre premier (Prime number)

Un nombre premier (ou premier) est un nombre naturel supérieur à 1 qui n'est pas un produit de deux nombres naturels plus petits. Un nombre naturel supérieur à 1 qui est…

Un nombre premier, également appelé premier, est défini comme un nombre naturel supérieur à 1 qui ne peut pas être exprimé comme le produit de deux nombres naturels plus petits. À l’inverse, tout nombre naturel supérieur à 1 qui n’est pas premier est désigné nombre composé. Par exemple, le nombre 5 est premier car ses seules décompositions multiplicatives, 1 × 5 ou 5 × 1, incluent nécessairement 5 lui-même. En revanche, 4 est classé comme composite, car il peut être formé par le produit (2 × 2) où les deux facteurs sont inférieurs à 4. Les nombres premiers occupent une position fondamentale dans la théorie des nombres en raison du théorème fondamental de l'arithmétique, qui stipule que tout nombre naturel supérieur à 1 est soit un nombre premier lui-même, soit possède une factorisation unique en un produit de nombres premiers, quel que soit l'ordre des facteurs.

Un nombre premier (ou un premier) est un nombre naturel supérieur à 1 qui n'est pas un produit de deux nombres naturels plus petits. Un nombre naturel supérieur à 1 qui n’est pas premier est appelé nombre composé. Par exemple, 5 est premier car les seules façons de l'écrire sous forme de produit, 1 × 5 ou 5 × 1, impliquent 5 lui-même. Cependant, 4 est composite car il s'agit d'un produit (2 × 2) dans lequel les deux nombres sont inférieurs à 4. Les nombres premiers sont centraux dans la théorie des nombres en raison du théorème fondamental de l'arithmétique : tout nombre naturel supérieur à 1 est soit un nombre premier lui-même, soit peut être factorisé comme un produit de nombres premiers unique jusqu'à leur ordre.

La caractéristique d'être premier est appelée primalité. Une technique simple, quoique inefficace, pour vérifier la primalité d'un nombre donné ⁠ $n$ ⁠ est une division de première instance, ce qui implique de vérifier si ⁠ $n$ ⁠ est divisible par n'importe quel nombre entier de 2 à ⁠ ${\sqrt {n}}$ ⁠. Il existe des algorithmes plus rapides, comme le test de primalité de Miller-Rabin, qui offre de la rapidité au prix d'une probabilité d'erreur mineure, et le test de primalité AKS, qui garantit un résultat correct en temps polynomial mais est généralement trop lent pour des applications pratiques. Des méthodes spécialisées et exceptionnellement rapides sont applicables aux nombres avec des structures particulières, illustrées par les nombres de Mersenne. En octobre 2024, le plus grand nombre premier identifié est un nombre premier de Mersenne, possédant 41 024 320 chiffres décimaux.

L'infinitude des nombres premiers a été établie par Euclide environ 300 avant JC. Il n’existe actuellement aucune formule simple permettant de distinguer les nombres premiers des nombres composés. Néanmoins, la distribution à grande échelle des nombres premiers parmi les nombres naturels peut être modélisée efficacement statistiquement. La réalisation phare dans ce domaine est le théorème des nombres premiers, prouvé à la fin du 19e siècle, qui postule que la probabilité qu'un grand entier choisi au hasard soit premier est approximativement inversement proportionnelle à son nombre de chiffres, ou de manière équivalente, à son logarithme.

De nombreuses questions de longue date concernant les nombres premiers restent en suspens. Parmi celles-ci figurent la conjecture de Goldbach, qui propose que tout entier pair dépassant 2 peut être représenté comme la somme de deux nombres premiers, et la conjecture des jumeaux premiers, qui postule l'existence d'une infinité de paires premières différant par deux. Ces recherches ont stimulé l'évolution de divers sous-domaines au sein de la théorie des nombres, mettant l'accent sur les propriétés analytiques ou algébriques des nombres. Les nombres premiers font partie intégrante de divers protocoles informatiques, y compris la cryptographie à clé publique, qui exploite le défi informatique lié à la prise en compte de grands entiers dans leurs composants premiers. En algèbre abstraite, les concepts analogues aux nombres premiers, présentant un comportement généralisé de type premier, englobent les éléments premiers et les idéaux premiers.

Définition et exemples illustratifs

Un nombre naturel (par exemple, 1, 2, 3, 4, 5, 6) est désigné comme un nombre premier (ou simplement un premier) s'il dépasse 1 et ne peut pas être exprimé comme le produit de deux nombres naturels, tous deux plus petits que lui. Les nombres naturels supérieurs à 1 qui ne satisfont pas à ce critère sont appelés nombres composés. Alternativement, un nombre ⁠ $n$ ⁠ est premier si ⁠ $n$ ⁠ les éléments discrets ne peuvent pas être divisés en groupes plus petits et de taille égale contenant plus d'un élément, ou si ⁠ $n$ ⁠ ne peuvent pas être disposés dans une grille rectangulaire dont les dimensions sont supérieures à un point en largeur et en hauteur. Par exemple, dans la séquence de nombres de 1 à 6, 2, 3 et 5 sont identifiés comme des nombres premiers car ils ne sont pas divisibles de manière égale par d'autres nombres entiers (c'est-à-dire sans reste). Le nombre 1 n'est pas considéré comme premier, car il est explicitement exclu par la définition. 4 = 2 × 2 et 6 = 2 × 3 sont des exemples de nombres composés.

Les diviseurs d'un nombre naturel ⁠ $n$ ⁠ sont définis comme les nombres naturels qui divisent ⁠ $n$ ⁠ sans reste. Chaque nombre naturel possède au moins deux diviseurs : 1 et le nombre lui-même. Un nombre n'est pas premier s'il a un diviseur autre que 1 et lui-même. Par conséquent, les nombres premiers sont définis de manière équivalente comme des entiers possédant précisément deux diviseurs positifs. Ces deux diviseurs sont 1 et le nombre lui-même. Puisque 1 n’a qu’un seul diviseur (lui-même), il est exclu de l’ensemble des nombres premiers selon cette définition. Alternativement, un nombre ⁠ $n$ ⁠ est considéré comme premier s'il dépasse un et n'est pas divisible sans reste par un entier de la séquence $2,3,\dots ,n-1$ 61§ , §64 $65§, \dots, n - §78$ 79§ {\displaystyle 2,3,\dots ,n-1} .

Les 25 nombres premiers initiaux, englobant tous les nombres premiers inférieurs à 100, sont répertoriés comme suit :

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 (séquence OEIS A000040).

Un nombre pair ⁠ $n$ ⁠ dépassant 2 ne peut pas être premier, car il peut invariablement être exprimé sous la forme du produit ⁠ $2\times n/2$ 26§ × n / §3637§ {\displaystyle 2\times n/2} ⁠. Par conséquent, tous les nombres premiers sauf 2 sont impairs et sont appelés premiers impairs. De plus, dans le système décimal standard, les nombres premiers supérieurs à 5 se terminent systématiquement par les chiffres 1, 3, 7 ou 9. Les nombres se terminant par d'autres chiffres sont composites : ceux se terminant par 0, 2, 4, 6 ou 8 sont pairs, tandis que ceux se terminant par 0 ou 5 sont divisibles par 5.

L'ensemble collectif de tous les nombres premiers est classiquement représenté par la notation ${\displaystyle \mathbf {P} >$ (un P majuscule en gras) ou $\mathbb {P}$ (un P majuscule gras au tableau).

Historique

Datant d'environ 1550 avant JC, le papyrus mathématique Rhind contient des extensions de fractions égyptiennes qui font la différence entre les nombres premiers et les nombres composés. Néanmoins, la première documentation existante concernant l'étude systématique des nombres premiers provient des mathématiciens grecs anciens, qui les désignaient comme prōtos arithmòs (πρῶτος ἀριθμὸς). L'ouvrage fondateur d'Euclide, Éléments (vers 300 avant JC), fournit la preuve de l'infinitude des nombres premiers, établit le théorème fondamental de l'arithmétique et décrit une méthode pour construire des nombres parfaits à partir des nombres premiers de Mersenne. Le tamis d'Ératosthène, une autre innovation grecque importante, reste une méthode contemporaine pour générer des listes de premiers.

Vers 1000 après JC, le mathématicien islamique Ibn al-Haytham (Alhazen) a découvert le théorème de Wilson, qui caractérise les nombres premiers comme étant des nombres entiers ⁠ $n$

En 1640, Pierre de Fermat articula le Petit Théorème de Fermat, une proposition qu'il présenta sans preuve formelle, qui fut ensuite étayée par Leibniz et Euler. Fermat a également mené des recherches sur la primalité des nombres de Fermat, exprimés par ⁠ $2^{2^{n}}+1$ 9§ §1213§ n + §2324§ {\displaystyle 2^{2^{n}}+1} ⁠. Parallèlement, Marin Mersenne entreprend des recherches sur les nombres premiers de Mersenne, qui sont des nombres premiers caractérisés par la forme $2^{p}-1$ 42§ p − §5152§ {\displaystyle 2^{p}-1} , où ⁠ $p$ ⁠ est lui-même un nombre premier. Dans une correspondance de 1742 avec Euler, Christian Goldbach a proposé la conjecture de Goldbach, postulant que tout nombre entier pair peut être exprimé comme la somme de deux nombres premiers. Euler a ensuite démontré la validité de la conjecture d'Alhazen (actuellement reconnue sous le nom de théorème d'Euclide-Euler), établissant que tous les nombres, même parfaits, peuvent être dérivés des nombres premiers de Mersenne. De plus, Euler a intégré les méthodes analytiques dans ce domaine à travers ses démonstrations de la nature infinie des nombres premiers et de la divergence de la série comprenant les réciproques des nombres premiers, représentée par {1}{7}}+{\tfrac {1}{11}}+\cdots }" xmlns="w3.org/1998/Math/MathML"> §8990§ §9192§ + §101102§ §103 $2^{2^{n}}+1$ + §113114§ §115116§ + §125126§ §127128§ + §137138§ §139140§ + ⋯ {\displaystyle {\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{5}}+{\tfrac {1}{7}}+{\tfrac {1}{11}}+\cdots } ⁠.Au début du 19e siècle, Legendre et Gauss ont indépendamment émis l'hypothèse que ⁠ $x$ ⁠ se rapproche de l'infini, le nombre de nombres premiers est inférieur ou égal à ⁠ $x$ ⁠ est asymptotiquement équivalent à ⁠ $x/\log x$ ⁠, avec $\log x$ désignant le logarithme népérien de ⁠ $x$ ⁠. Le postulat de Bertrand, une implication moins stricte de cette forte densité observée de nombres premiers, affirme que pour tout entier $n>1$ 273§ {\displaystyle n>1} , un nombre premier existe strictement entre ⁠ $n$ ⁠ et ⁠ $2n$ 308§ n {\displaystyle 2n} ⁠, une proposition rigoureusement établie en 1852 par Pafnuty Chebyshev. La publication de Bernhard Riemann de 1859 concernant la fonction zêta présentait un cadre conceptuel pour étayer la conjecture avancée par Legendre et Gauss. Alors que l'hypothèse de Riemann, intimement liée, continue de défier toute preuve, le cadre fondateur de Riemann a finalement été formalisé en 1896 par Hadamard et de la Vallée Poussin, aboutissant à ce qui est maintenant reconnu comme le théorème des nombres premiers. Une autre réalisation mathématique importante du XIXe siècle fut le théorème de Dirichlet sur les progressions arithmétiques, qui démontra que des progressions arithmétiques spécifiques englobent une quantité infinie de nombres premiers.

De nombreux mathématiciens ont développé des tests de primalité pour les nombres dépassant les limites pratiques de la division par essai. Les tests de primalité spécialisés, applicables aux nombres de formes particulières, comprennent le test de Pépin pour les nombres de Fermat (1877), le théorème de Proth (vers 1878), le test de primalité de Lucas-Lehmer (créé en 1856) et le test de primalité généralisé de Lucas.

Depuis 1951, les plus grands nombres premiers connus ont été identifiés grâce à l'application de ces tests sur des ordinateurs. La recherche continue de nombres premiers de plus en plus grands a suscité un intérêt plus large au-delà des mathématiques académiques, notamment grâce à des initiatives telles que le Great Internet Mersenne Prime Search et d'autres projets informatiques distribués. La perception selon laquelle les nombres premiers avaient une utilité limitée au-delà des mathématiques pures a été fondamentalement modifiée dans les années 1970 avec l'avènement de la cryptographie à clé publique et du système de cryptographie RSA, tous deux fondamentalement basés sur des nombres premiers.

L'importance pratique croissante des tests de primalité et de la factorisation informatisés a nécessité le développement de méthodes avancées pour traiter un grand nombre de formes arbitraires. Parallèlement, la théorie mathématique des nombres premiers a progressé de manière significative avec le théorème de Green-Tao (2004), démontrant l'existence de progressions arithmétiques arbitrairement longues de nombres premiers, et la preuve de Yitang Zhang en 2013, établissant l'existence d'une infinité d'écarts premiers de grandeur limitée.

La Primalité de l'Un

Dans l'Antiquité, la plupart des premiers mathématiciens grecs ne classifiaient pas 1 comme un nombre, excluant toute considération de sa primalité. Une minorité d'érudits des traditions grecque et romaine plus tardive, comme Nicomaque, Iamblique, Boèce et Cassiodore, ont en outre classé les nombres premiers comme un sous-ensemble de nombres impairs, excluant par conséquent ⁠ $§7$ 8§ {\displaystyle 2} ⁠ de la primalité. À l'inverse, Euclide et la plupart des autres mathématiciens grecs reconnaissaient la ⁠ $§25$ 26§ {\displaystyle 2} ⁠ comme nombre premier. Les mathématiciens islamiques médiévaux ont généralement adopté la perspective grecque, ne considérant pas 1 comme un nombre. Au Moyen Âge et à la Renaissance, les mathématiciens ont commencé à reconnaître 1 comme nombre et, au XVIIe siècle, certains l'ont même classé comme premier. Au milieu du XVIIIe siècle, Christian Goldbach en a inclus 1 dans sa liste de nombres premiers lors d'une correspondance avec Leonhard Euler ; cependant, Euler lui-même ne considérait pas 1 comme premier. De nombreux mathématiciens du XIXe siècle ont continué à considérer 1 nombre premier, Derrick Norman Lehmer l'ayant notamment inclus dans sa liste des nombres premiers inférieurs à dix millions publiée en 1914. Des listes de nombres premiers contenant 1 étaient encore publiées jusqu'en 1956. Néanmoins, au début du 20e siècle, un consensus a émergé parmi les mathématiciens selon lequel 1 ne devrait pas être classé comme premier, mais plutôt désigné comme une catégorie unique, une "unité".

Classer 1 comme nombre premier nécessiterait une reformulation fastidieuse de nombreuses déclarations mathématiques concernant les nombres premiers. Par exemple, le théorème fondamental de l’arithmétique nécessiterait une reformulation pour spécifier les factorisations en nombres premiers supérieurs à 1, car autrement chaque nombre posséderait plusieurs factorisations incorporant une quantité arbitraire de 1. De même, le tamis d'Ératosthène fonctionnerait mal si 1 était traité comme un nombre premier, car il éliminerait par erreur tous les multiples de 1 (c'est-à-dire tous les autres nombres entiers), ne produisant que le nombre 1 lui-même. Par ailleurs, plusieurs propriétés techniques caractéristiques des nombres premiers ne s'appliquent pas à 1 ; par exemple, les formules de la fonction totale d'Euler et de la fonction somme des diviseurs diffèrent pour les nombres premiers par rapport à 1.

Propriétés élémentaires

Factorisation unique

La représentation d'un entier comme produit de nombres premiers est appelée sa factorisation première. Par exemple :

{\displaystyle {\begin{aligned}50&=2\times 5\times 5\\&=2\times 5^{2}.\end{aligned}}>

Les composants individuels d'un produit sont appelés facteurs premiers. Un facteur premier particulier peut apparaître plusieurs fois ; par exemple, dans cette illustration, le facteur premier $5.$ est présent deux fois. Lorsqu'un nombre premier revient, l'exponentiation offre une méthode pour consolider ces instances répétées : par exemple, dans la représentation alternative du produit mentionnée précédemment, $5^{2}$ 29§ {\displaystyle 5^{2}} signifie le carré, ou la puissance seconde, de ⁠ ${\displaystyle 5>$ ⁠.

Le rôle central des nombres premiers dans la théorie des nombres et dans les mathématiques plus larges provient du théorème fondamental de arithmétique. Ce théorème postule que tout entier supérieur à un peut être exprimé comme un produit comprenant un ou plusieurs nombres premiers. De plus, cette factorisation est déterminée de manière unique, ce qui signifie que deux factorisations premières d'un nombre identique contiendront invariablement la même multiplicité de chaque nombre premier, malgré les variations potentielles de leur séquence. Par conséquent, malgré l’existence de divers algorithmes de factorisation d’entiers, toutes les méthodes sont garanties de donner un résultat identique. Ainsi, les nombres premiers sont conceptualisés comme les « éléments de base » fondamentaux du système des nombres naturels.

Plusieurs démonstrations du caractère unique des factorisations premières s'appuient sur le lemme d'Euclide, qui stipule : Si ⁠ $p$ ⁠ est un nombre premier et ⁠ $p$ ⁠ divise le produit $ab$ d'entiers ⁠ ${\displaystyle a>$ ⁠ et ${\displaystyle b,>$ , puis ⁠ $p$ ⁠ doit diviser ⁠ ${\displaystyle a>$ ⁠ ou ⁠ $p$ ⁠ doit diviser ⁠ $b$ ⁠ (ou les deux). Inversement, si un nombre ⁠ $p$ ⁠ possède la caractéristique que sa division d'un produit entraîne invariablement la division d'au moins un facteur de ce produit, alors ⁠ $p$ ⁠ est nécessairement premier.

Infinitude

L'existence d'un nombre infini de nombres premiers est un concept fondamental de la théorie des nombres. Cela implique que la séquence

2,3,5,7,11,13,...

des nombres premiers est sans fin. Cette affirmation fondamentale est connue sous le nom de Théorème d'Euclide, du nom de l'ancien mathématicien grec Euclide, à qui l'on attribue la première preuve connue. De nombreuses preuves ultérieures de l'infinitude des nombres premiers ont été développées, notamment une preuve analytique d'Euler, la preuve de Goldbach dérivée des nombres de Fermat, la preuve de Furstenberg employant la topologie générale et la démonstration raffinée de Kummer.

La preuve d'Euclide démontre que toute énumération finie de nombres premiers est intrinsèquement incomplète. Le principe de base consiste à multiplier tous les nombres premiers dans une liste spécifiée et à ajouter ensuite $1.$ . Pour une liste comprenant les nombres premiers $p_{1},p_{2},\ldots ,p_{n},$ 27§ , p §36 $1.$ , … , p n , {\displaystyle p_{1},p_{2},\ldots,p_{n},} , cette opération donne le nombre

N=1+p_{1}\cdot p_{2}\cdots p_{n}.

11§ + p §1819§ ⋅ p §29

N=1+p_{1}\cdot p_{2}\cdots p_{n}.

⋯ p n . {\displaystyle N=1+p_{1}\cdot p_{2}\cdots p_{n}.}

Selon le théorème fondamental de l'arithmétique, ⁠ $N$ ⁠ possède une factorisation première unique, exprimée par

N=p'_{1}\cdot p'_{2}\cdots p'_{m}

15§ ′ ⋅ p §27

N=p'_{1}\cdot p'_{2}\cdots p'_{m}

′ ⋯ p m ′ {\displaystyle N=p'_{1}\cdot p'_{2}\cdots p'_{m}}

où ⁠ $N$ ⁠ possède un ou plusieurs facteurs premiers. Tandis que ⁠ $N$ ⁠ est parfaitement divisible par chacun de ces facteurs nouvellement identifiés, il donne un reste de un lorsqu'il est divisé par n'importe quel nombre premier de la liste initiale. Par conséquent, aucun des facteurs premiers de ⁠ $N$ ⁠ peuvent être membres de la liste finie d'origine. Cette déduction logique confirme qu'aucune liste finie ne peut englober tous les nombres premiers, établissant ainsi leur quantité infinie.

Les nombres dérivés en ajoutant un au produit des nombres premiers initiaux sont désignés comme nombres d'Euclide. Les cinq premiers de ces nombres sont premiers, tandis que le sixième,

1+{\big (}2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big )}=30031=59\cdot 509,

7§ + ( §16

1+{\big (}2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big )}=30031=59\cdot 509,

{\displaystyle 1+{\big (}2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big )}=30031=59\cdot 509,}

est un nombre composé.

Formules pour nombres premiers

Aucune formule efficace pour générer des nombres premiers n'a été découverte. Par exemple, aucun polynôme non constant, même impliquant plusieurs variables, ne produit exclusivement des valeurs premières. Néanmoins, il existe diverses expressions qui codent tous les nombres premiers ou ne produisent que des nombres premiers. Une de ces formules, dérivée du théorème de Wilson, génère le nombre 2 plusieurs fois tout en produisant tous les autres nombres premiers précisément une fois. De plus, un ensemble spécifique d'équations diophantiennes, comprenant neuf variables et un seul paramètre, possède la caractéristique selon laquelle le paramètre est premier si et seulement si le système d'équations correspondant a une solution dans l'ensemble des nombres naturels. Cette propriété permet la dérivation d'une formule singulière dont les sorties positives sont exclusivement des nombres premiers.

D'autres exemples de formules capables de générer des nombres premiers sont fournis par le théorème de Mills et un théorème attribué à Wright. Ces théorèmes postulent l'existence de constantes réelles $A>1$ 11§ {\displaystyle A>1} et $\mu$ , respectivement, tel que

\left\lfloor A^{3^{n}}\right\rfloor {\text{ et }}\left\lfloor 2^{\cdots ^{2^{2^{\mu }}}}\right\rfloor

Ces expressions donnent des nombres premiers pour n'importe quel nombre naturel ⁠ $n$ ⁠ dans la formule initiale et pour tout nombre spécifié d'exposants dans la formule suivante. La notation $\lfloor {}\cdot {}\rfloor$ désigne la fonction floor, qui renvoie le plus grand entier inférieur ou égal à l'argument. Néanmoins, ces formules manquent d'utilité pratique pour la génération de nombres premiers, comme les valeurs de ⁠ $A$ ⁠ ou $\mu .$ doit d'abord être calculé à l'aide de nombres premiers préexistants.

Questions non résolues

De nombreuses conjectures concernant les nombres premiers ont été proposées. Malgré leurs formulations souvent élémentaires, nombre de ces conjectures ont résisté à la preuve pendant des décennies ; par exemple, les quatre problèmes posés par Landau en 1912 restent non résolus. Un exemple frappant est la conjecture de Goldbach, qui postule que tout entier pair ⁠ $n$ ⁠ dépassant ⁠ $§25$ 26§ {\displaystyle 2} ⁠ peut être exprimé comme la somme de deux nombres premiers. En 2014, cette conjecture avait été vérifiée informatiquement pour tous les entiers jusqu'à $n=4\cdot 10^{18}.$ 56§ . {\displaystyle n=4\cdot 10^{18}.} Bien que la conjecture de Goldbach reste non prouvée, des déclarations connexes plus faibles ont été établies ; par exemple, le théorème de Vinogradov démontre que tout entier impair suffisamment grand peut être représenté comme la somme de trois nombres premiers. De plus, le théorème de Chen affirme que tout nombre pair suffisamment grand peut être exprimé comme la somme d'un nombre premier et d'un semi-premier, qui est défini comme le produit de deux nombres premiers. De plus, tout nombre entier supérieur à 10 peut être décomposé en la somme de six nombres premiers. Le domaine de la théorie des nombres dédié à l'étude de ces types de questions est connu sous le nom de théorie additive des nombres.

Une catégorie distincte de recherches mathématiques concerne les écarts premiers, qui sont définis comme les différences observées entre les nombres premiers successifs. L'existence d'écarts premiers d'ampleur arbitraire est démontrable en observant que la séquence $n!+2,n!+3,\dots ,n!+n$ comprend $n-1$ 59§ {\displaystyle n-1} nombres composés pour tout nombre naturel ${\displaystyle n.>$ Néanmoins, des écarts premiers importants se manifestent beaucoup plus tôt que ne le suggère cette construction théorique. Par exemple, l'écart premier initial de longueur 8 est situé entre les nombres premiers 89 et 97, une valeur nettement inférieure à ${\displaystyle 8!=40320.>$ La conjecture des jumeaux premiers postule l'existence d'un nombre infini de jumeaux premiers, qui sont des paires de nombres premiers différant de 2. Plus largement, la conjecture de Polignac affirme que pour tout entier positif ${\displaystyle k,>$ , il existe une infinité de paires de nombres premiers consécutifs dont la différence est ${\displaystyle 2k.>$ Plusieurs conjectures, dont celles d'Andrica, Brocard, Legendre et Oppermann, proposent que les écarts premiers maximum soient compris entre 1 et ⁠ $n$ ⁠ ne doit pas dépasser environ ${\sqrt {n}},$ , une conséquence connue pour dériver de l'hypothèse de Riemann.En revanche, la conjecture de Cramér, beaucoup plus stricte, postule que la plus grande taille d'écart est ⁠ $O((\log n)^{2})$ ⁠. Le concept d'écarts premiers peut être étendu aux premiers ⁠ $k$ ⁠-tuples, qui représentent des modèles de différences entre plus de deux nombres premiers. La première conjecture de Hardy-Littlewood aborde leur infinitude et leur densité, une proposition soutenue par l'observation heuristique selon laquelle les nombres premiers présentent un comportement analogue à une séquence aléatoire de nombres, avec une densité déterminée par le théorème des nombres premiers.

Propriétés analytiques

La théorie analytique des nombres étudie la théorie des nombres en utilisant le cadre des fonctions continues, des limites, des séries infinies et des concepts mathématiques associés relatifs à l'infini et aux infinitésimaux.

Ce domaine d'étude est né de Leonhard Euler, dont la première contribution significative a été la résolution du problème de Bâle. Ce problème cherchait la valeur de la série infinie $1+{\tfrac {1}{4}}+{\tfrac {1}{9}}+{\tfrac {1}{16}}+\dots ,$ 7§ + §1314§ §1516§ + §2526§ §2728§ + §3738§ §3940§ + … , {\displaystyle 1+{\tfrac {1}{4}}+{\tfrac {1}{9}}+{\tfrac {1}{16}}+\dots ,} , qui est désormais identifiée comme la valeur $\zeta (2)$ de la fonction zêta de Riemann. Cette fonction présente une relation étroite avec les nombres premiers et est au cœur de l'hypothèse de Riemann, l'un des problèmes mathématiques non résolus les plus profonds. Euler a démontré que ⁠ $\zeta (2)=\pi ^{2}/6$ ⁠. L'inverse de cette valeur, ⁠ $6/\pi ^{2}$ ⁠, représente la probabilité limite que deux entiers choisis au hasard dans une plage substantielle soient relativement premiers, ce qui signifie qu'ils ne partagent aucun facteur commun.

La distribution macroscopique des nombres premiers, y compris la quantité de nombres premiers en dessous d'un grand seuil spécifié, est caractérisée par le théorème des nombres premiers. Cependant, une formule efficace pour déterminer le ⁠ $n$ ⁠-ème premier reste inconnu. Le théorème de Dirichlet sur les progressions arithmétiques, dans sa formulation fondamentale, postule que les polynômes linéaires

p(n)=a+bn

où des entiers ⁠ $a$ ⁠ et ⁠ $b$ ⁠ sont relativement premiers, donnent un nombre infini de valeurs premières. Des versions plus avancées du théorème affirment que la somme des réciproques de ces valeurs premières diverge et que des polynômes linéaires distincts partageant le même paramètre displaystyle="true" scriptlevel="0"> b {\displaystyle b} ⁠ présentent des proportions à peu près équivalentes de nombres premiers. Bien que des conjectures concernant les proportions de nombres premiers générés par des polynômes de degré supérieur aient été proposées, celles-ci restent non prouvées. De plus, on ne sait actuellement pas si un polynôme quadratique peut produire des nombres premiers une infinité de fois lorsqu'il est évalué avec des entrées entières.

Démonstration analytique du théorème d'Euclide

La preuve d'Euler, établissant l'infinitude des nombres premiers, implique un examen des sommes de leurs réciproques.

{\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots +{\frac {1}{p}}.

9§ §10

{\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots +{\frac {1}{p}}.

+ §1819§ §2021§ + §2829§ §3031§ + §3839§ §4041§ + ⋯ + §5354§ p . {\displaystyle {\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots +{\frac {1}{p}}.}

Euler a démontré cela pour tout nombre réel arbitraire ⁠ $x$ ⁠, un premier ⁠ $p$ ⁠ existe de telle sorte que cette somme dépasse ⁠ $x$ ⁠. Cette découverte établit l'infinitude des nombres premiers, car un ensemble fini de nombres premiers impliquerait que la somme atteint un maximum fini au plus grand nombre premier, plutôt que de dépasser continuellement chaque ⁠ $x$ ⁠. Le deuxième théorème de Mertens fournit une description plus précise du taux de croissance de cette somme. En revanche, la somme

{\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}

9§ §1112§ §14

{\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}

+ §2425§ §27

{\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}

+ §4041§ §4344§ §46

{\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}

+ ⋯ + §6162§ n §67

{\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}

{\displaystyle {\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}}

ne diverge pas à l'infini comme ⁠ $n$ ⁠ se rapproche de l'infini. Ce phénomène est détaillé dans le problème de Bâle. Par conséquent, les nombres premiers présentent une fréquence d’apparition plus élevée que les carrés des nombres naturels, bien que les deux ensembles soient infinis. Le théorème de Brun postule en outre que la somme des réciproques des jumeaux premiers,

\left({{\frac {1}{3}}+{\frac {1}{5}}}\right)+\left({{\frac {1}{5}}+{\frac {1}{7}}}\right)+\left({{\frac {1}{11}}+{\frac {1}{13}}}\right)+\cdots ,

13§ §1415§ + §2223§ §2425§ ) + ( §4041§ §4243§ + §5051§ §5253§ ) + ( §6869§ §7071§ + §7879§ §8081§ ) + ⋯ , {\displaystyle \left({{\frac {1}{3}}+{\frac {1}{5}}}\right)+\left({{\frac {1}{5}}+{\frac {1}{7}}}\right)+\left({{\frac {1}{11}}+{\frac {1}{13}}}\right)+\cdots ,>

est fini. Le théorème de Brun établit que la méthode d'Euler ne peut pas être appliquée pour résoudre la conjecture des jumeaux premiers, qui postule l'existence d'un nombre infini de jumeaux premiers.

L'énumération des nombres premiers jusqu'à une limite spécifiée

La fonction de comptage des nombres premiers, notée ${\displaystyle \pi (n)>$ , quantifie le nombre de nombres premiers qui ne dépassent pas ⁠ $n$ ⁠. Par exemple, ⁠ $\pi (11)=5$ ⁠, reflétant la présence de cinq nombres premiers inférieurs ou égaux à 11. Des algorithmes comme l'algorithme de Meissel-Lehmer permettent le calcul précis de ${\displaystyle \pi (n)>$ avec une plus grande efficacité que l'énumération de chaque nombre premier jusqu'à ⁠ $n$ ⁠. Le théorème des nombres premiers affirme que ${\displaystyle \pi (n)>$ présente un comportement asymptotique équivalent à ⁠ $n/\log n$ ⁠, une relation formellement exprimée comme :

\pi (n)\sim {\frac {n}{\log n}},

Cela signifie que le rapport de ${\displaystyle \pi (n)>$ vers la fraction de droite converge vers 1 lorsque ⁠ $n$ ⁠ tend vers l'infini. Par conséquent, la probabilité qu'un entier sélectionné au hasard soit inférieur à ⁠ $n$ ⁠ est premier est approximativement inversement proportionnel au nombre de chiffres dans ⁠ $n$ ⁠. De plus, ce théorème indique que la ⁠ $n$ ⁠le nombre premier évolue proportionnellement avec $n\log n$ , ce qui implique que la grandeur moyenne d'un écart premier est proportionnelle à ⁠ $\log n$ ⁠. Une estimation plus précise pour ${\displaystyle \pi (n)>$ est fourni par l'intégrale logarithmique de décalage.

\pi (n)\sim \operatorname {Li} (n)=\int _{2}^{n}{\frac {dt}{\log t}}.

Progressions arithmétiques

Une progression arithmétique constitue une série finie ou infinie de nombres où la différence entre termes successifs reste constante. Cette différence constante est appelée module de progression. Par exemple,

3,12,21,30,39,...,

Cette séquence représente une progression arithmétique infinie avec un module de 9. Dans une progression arithmétique, tous les termes donnent un reste identique lors de la division par le module ; dans ce cas précis, le reste est 3. Puisque le module (9) et le reste (3) sont divisibles par 3, chaque élément de cette séquence est également un multiple de 3. Par conséquent, cette progression ne comprend qu'un seul nombre premier, qui est 3. Plus largement, une progression infinie de la forme

a,a+q,a+2q,a+3q,\dots

Une progression arithmétique peut contenir plus d'un nombre premier exclusivement lorsque son reste ⁠ ${\displaystyle a>$ ⁠ et module ⁠ $q$ ⁠ sont premier. Si ces valeurs sont premières entre elles, le théorème de Dirichlet sur les progressions arithmétiques garantit l'existence d'un nombre infini de nombres premiers au sein de cette progression.

Le théorème de Green-Tao démontre l'existence de progressions arithmétiques finies de longueur arbitraire composées entièrement de nombres premiers.

Valeurs premières générées par les polynômes quadratiques

Euler a observé que la fonction mathématique

n^{2}-n+41

Cette fonction génère des nombres premiers pour ⁠ $1\leq n\leq 40$ 8§≤n≤40{\displaystyle 1\leq n\leq 40}⁠, mais des nombres composites émergent dans ses résultats ultérieurs. L'enquête sur cette observation a contribué au développement d'une théorie algébrique profonde des nombres concernant les nombres de Heegner et le problème des nombres de classe. La conjecture de Hardy – Littlewood F postule la densité des nombres premiers parmi les sorties de polynômes quadratiques à coefficients entiers, exprimée par l'intégrale logarithmique et les propres coefficients du polynôme. À ce jour, il n'a été démontré qu'aucun polynôme quadratique puisse produire une séquence infinie de valeurs premières.

La spirale d'Ulam organise les nombres naturels dans une grille bidimensionnelle, formant des carrés concentriques qui tournent en spirale vers l'extérieur à partir de l'origine, avec des nombres premiers clairement marqués. Une inspection visuelle révèle que les nombres premiers ont tendance à s'agréger le long de diagonales spécifiques plutôt que d'autres, ce qui implique que certains polynômes quadratiques génèrent des valeurs premières avec une plus grande fréquence.

La fonction Zeta et l'hypothèse de Riemann

L'hypothèse de Riemann, formulée en 1859 et reconnue comme l'un des problèmes du Prix du Millénaire, représente une énigme mathématique importante non résolue. Il cherche à déterminer les emplacements précis des zéros de la fonction zêta de Riemann, notés $\zeta (s)$ . Cette fonction fonctionne comme une fonction analytique sur les nombres complexes. Pour les nombres complexes ⁠ $s$ ⁠ possédant une partie réelle dépassant un, elle peut être exprimée de manière équivalente à la fois comme une sommation infinie sur tous les nombres entiers et un produit infini sur les nombres premiers.

\zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p{\text{ prime}}}{\frac {1}{1-p^{-s}}}.

27§∞§3638§ns=∏p prime§6467§§6870§−p−s.{\displaystyle \zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p{\text{ prime}}}{\frac {1}{1-p^{-s}}}.}

La découverte par Euler de cette égalité somme-produit est connue sous le nom de produit d'Euler. Dérivé du théorème fondamental de l'arithmétique, le produit d'Euler élucide la relation profonde entre la fonction zêta et les nombres premiers. Ce principe fournit également une preuve alternative de l'infinitude des nombres premiers : en supposant un nombre fini de nombres premiers, l'égalité du produit somme serait valable à ⁠ $s=1$ 12§ {\displaystyle s=1} ⁠. Cependant, à ce stade, la somme (la série harmonique ⁠ $1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\dots$ 30§ + §3637§ §3839§ + §4849§ §50 $s=1$ + … {\displaystyle 1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\dots } ⁠) divergerait, alors que le produit resterait fini, conduisant à une contradiction logique.

L'hypothèse de Riemann postule que tous les zéros de la fonction zêta sont soit des entiers pairs négatifs, soit des nombres complexes possédant une partie réelle de 1/2. La démonstration initiale du théorème des nombres premiers reposait sur une version plus faible de cette hypothèse, à savoir qu'il n'existe pas de zéros avec une partie réelle de 1 ; cependant, des preuves ultérieures, plus élémentaires, ont émergé depuis. La formule explicite de Riemann permet d'articuler la fonction de comptage des premiers comme une somme, où chaque terme constitutif provient d'un zéro de la fonction zêta. La composante principale de cette sommation est l'intégrale logarithmique, les termes résiduels induisant des oscillations autour de cette composante principale. Par conséquent, ces zéros régissent la régularité de la distribution des nombres premiers. Si l'hypothèse de Riemann s'avérait correcte, ces fluctuations seraient minimes et la distribution asymptotique des nombres premiers, telle qu'établie par le théorème des nombres premiers, s'étendrait à des intervalles significativement plus courts (approximativement la racine carrée de ⁠ $x$ ⁠ pour les intervalles proches de ⁠ ${\displaystyle x>$ ⁠).

Algèbre abstraite

Arithmétique modulaire et champs finis

Du point de vue de l'algèbre abstraite, la capacité de division implique que l'arithmétique modulaire à module premier constitue un corps, ou plus précisément, un corps fini. En revanche, d'autres modules établissent uniquement un anneau, pas un champ.

L'arithmétique modulaire fournit un cadre pour articuler divers théorèmes concernant les nombres premiers. Par exemple, le petit théorème de Fermat affirme que si $a\not \equiv 0$ 11§ {\displaystyle a\not \equiv 0} (mod ⁠ $p$ ⁠), puis $a^{p-1}\equiv 1$ 54§ ≡ §6061§ {\displaystyle a^{p-1}\equiv 1} (mod ⁠ $p$ ⁠). Agrégation de ce résultat sur toutes les valeurs possibles de ⁠ $a$ ⁠ donne l'équation suivante :

\sum _{a=1}^{p-1}a^{p-1}\equiv (p-1)\cdot 1\equiv -1{\pmod {p}},

16§ p − §2425§ a p − §3738§ ≡ ( p − §5152§ ) ⋅ §5859§ ≡ − §6667§ ( mod p ) , {\displaystyle \sum _{a=1}^{p-1}a^{p-1}\equiv (p-1)\cdot 1\equiv -1{\pmod {p}},}

Cette équation est vraie exclusivement lorsque ⁠ $p$ ⁠ est un nombre premier. La conjecture de Giuga postule que cette équation sert également de condition suffisante pour ⁠ $p$ ⁠ pour être premier. De plus, le théorème de Wilson établit qu'un entier $p>1$ 47§ {\displaystyle p>1} est premier si et seulement si sa factorielle, $(p-1)!$ 70§ ) ! {\displaystyle (p-1)!> , est conforme à $-1$ 93§ {\displaystyle -1} modulo ⁠ $p$ ⁠.Cette condition ne peut pas être satisfaite pour un nombre composé ⁠ $n=r\cdot s$ ⁠, car au moins un de ses facteurs divise les deux n et ⁠ $(n-1)!$ 164§ ) ! {\displaystyle (n-1)!} ⁠, rendant la congruence $(n-1)!\equiv -1{\pmod {n}}$ 192§ ) ! ≡ − §203204§ ( mod n ) {\displaystyle (n-1)!\equiv -1{\pmod {n}}> impossible.

pNombres-adiques

Le ⁠ $p$ ⁠-ordre adique, noté ${\displaystyle \nu _{p}(n)>$ pour un entier ⁠ $n$ ⁠, quantifie l'exposant de ⁠ $p$ ⁠ dans la factorisation première de ⁠ $n$ ⁠.

Le cadre conceptuel englobant l'ordre, la valeur absolue et leurs champs complets dérivés peut être étendu aux champs numériques algébriques. Cette généralisation implique des évaluations, qui sont des mappages spécifiques du groupe multiplicatif d'un champ à un groupe additif totalement ordonné (également appelé ordres) ; les valeurs absolues, définies comme des mappages multiplicatifs du champ aux nombres réels (également appelés normes) ; et les lieux, qui représentent des extensions pour compléter des champs où le champ d'origine forme un sous-ensemble dense (également appelés complétions). Par exemple, l’extension des nombres rationnels aux nombres réels illustre un endroit où la distance entre les nombres est déterminée par la valeur absolue standard de leur différence. Bien que le logarithme de la valeur absolue puisse servir de mappage correspondant à un groupe additif, il ne satisfait pas pleinement aux critères d'une évaluation. Le théorème d'Ostrowski affirme que, sous une relation d'équivalence naturelle, les nombres réels et ⁠ $p$ ⁠-les nombres adiques, ainsi que leurs ordres et valeurs absolues associés, constituent les seules évaluations, valeurs absolues et places définies sur les nombres rationnels. Le principe local-global facilite la résolution de problèmes spécifiques concernant les nombres rationnels en synthétisant des solutions dérivées de chacune de leurs places respectives, soulignant ainsi le rôle fondamental des nombres premiers dans la théorie des nombres.

Éléments premiers dans un anneau

Un anneau commutatif constitue une structure algébrique caractérisée par des opérations définies d'addition, de soustraction et de multiplication. L'ensemble des nombres entiers forme un anneau, et le concept de nombres premiers au sein des entiers a été étendu aux anneaux généraux à travers deux classifications distinctes : les éléments premiers et les éléments irréductibles. Un élément ⁠ $p$ ⁠ dans un anneau ⁠ $R$ ⁠ est désigné comme premier s'il est différent de zéro, n'a pas d'inverse multiplicatif (c'est-à-dire qu'il ne s'agit pas d'une unité) et satisfait à la condition que chaque fois que ⁠ $p$ ⁠ divise le produit $xy$ de deux éléments de ⁠ $R$ ⁠, il doit également diviser au moins un des ⁠ $x$ ⁠ ou ⁠ $y$ ⁠. A l’inverse, un élément est réputé irréductible s’il n’est ni une unité ni exprimable comme le produit de deux autres éléments non unitaires. Au sein de l'anneau des entiers, les éléments premiers et irréductibles constituent un ensemble identique.

\{\dots ,-11,-7,-5,-3,-2,2,3,5,7,11,\dots \}\,.

Dans un anneau arbitraire, tout élément premier est nécessairement irréductible. Cependant, l'inverse de cette affirmation n'est pas universellement vraie, même si elle s'applique spécifiquement aux domaines de factorisation uniques.

Le théorème fondamental de l'arithmétique est intrinsèquement valable dans des domaines de factorisation uniques. Un exemple notable d'un tel domaine est celui des entiers gaussiens, notés ⁠ $\mathbb {Z} [i]$ ⁠. Cet anneau comprend des nombres complexes structurés comme $a+bi$ , où ⁠ ${\displaystyle i>$ ⁠ représente l'unité imaginaire, et ⁠ $a$ ⁠ et ⁠ $b$ ⁠ sont des nombres entiers. Les éléments premiers de ce domaine sont appelés nombres premiers gaussiens. Il est important de noter que tous les entiers premiers dans l’ensemble des entiers ne conservent pas leur primalité au sein des entiers gaussiens. Par exemple, l'entier 2 peut être exprimé comme le produit de deux nombres premiers gaussiens : $1+i$ 109§ + i {\displaystyle 1+i} et ⁠ $1-i$ 130§ − i {\displaystyle 1-i> ⁠. Les nombres premiers rationnels (c'est-à-dire les nombres premiers dans l'ensemble des nombres entiers) qui sont congrus à 3 modulo 4 sont classés comme des nombres premiers gaussiens, alors que ceux qui sont congrus à 1 modulo 4 ne le sont pas. Cette distinction découle du théorème de Fermat sur les sommes de deux carrés, qui postule qu'un nombre premier impair p {\displaystyle p} ⁠ peut être exprimé comme la somme de deux carrés, spécifiquement ⁠ $p=x^{2}+y^{2}$ 179§ + y §188189§ {\displaystyle p=x^{2}+y^{2}} ⁠.Par conséquent, il est factorisable comme ⁠ ${\displaystyle p=(x+iy)(x-iy)>$ ⁠, précisément quand ⁠ $p$ ⁠ est congru à 1 modulo 4.

Idéaux premiers

Tous les anneaux ne constituent pas un domaine de factorisation unique. Par exemple, l'anneau de nombres $a+b{\sqrt {-5}}$ (où ⁠ ${\displaystyle a>$ ⁠ et ⁠ $b$ ⁠ sont des entiers) ne présente pas de factorisation unique. Ceci est démontré par le nombre $21$ , qui possède deux factorisations distinctes : ⁠ $21=3\cdot 7=(1+2{\sqrt {-5}})(1-2{\sqrt {-5}})$ 104§ + §107 $a+b{\sqrt {-5}}$ 123§ − §127 $a+b{\sqrt {-5}}$ {\displaystyle 21=3\cdot 7=(1+2{\sqrt {-5}})(1-2{\sqrt {-5}})} ⁠. Dans ce cas, aucun des quatre facteurs ne peut être réduit davantage, ce qui exclut une factorisation unique. Pour étendre la factorisation unique à une classe plus large d'anneaux, le concept de nombre est remplacé par celui d'idéal, qui est défini comme un sous-ensemble d'éléments d'un anneau fermé par addition (contenant toutes les sommes de paires de ses éléments) et par multiplication par n'importe quel élément de l'anneau.

Le spectre d'un anneau définit un espace géométrique où ses points correspondent aux idéaux premiers de cet anneau. Ce concept s'avère également bénéfique en géométrie arithmétique, où de nombreux principes sont partagés entre la géométrie et la théorie des nombres. Par exemple, la factorisation ou la ramification des idéaux premiers lors de leur extension à un domaine plus vaste, un défi fondamental dans la théorie algébrique des nombres, présente des parallèles avec la ramification géométrique. De tels concepts peuvent même être utiles dans des recherches purement théoriques sur les nombres axées exclusivement sur les nombres entiers. Par exemple, l'application d'idéaux premiers dans l'anneau d'entiers de champs de nombres quadratiques facilite la preuve de la réciprocité quadratique, un théorème traitant de l'existence de racines carrées de nombres premiers entiers modulo. Les efforts initiaux pour établir le dernier théorème de Fermat ont incité Kummer à introduire des nombres premiers réguliers, qui sont des nombres premiers entiers associés à la décomposition de la factorisation unique en nombres entiers cyclotomiques. Le théorème de densité de Chebotarev aborde l'enquête sur le nombre de nombres premiers entiers qui prennent en compte plusieurs idéaux premiers dans un champ de nombres algébriques ; lorsqu'il est appliqué aux entiers cyclotomiques, ce théorème englobe le théorème de Dirichlet sur les nombres premiers dans les progressions arithmétiques comme exemple spécifique.

Théorie des groupes

Dans la théorie des groupes finis, les théorèmes de Sylow établissent que si une puissance d'un nombre premier, spécifiquement $p^{n}$ , divise l'ordre d'un groupe, alors le groupe possède nécessairement un sous-groupe d'ordre ⁠ $p^{n}$ ⁠. De plus, le théorème de Lagrange dicte que tout groupe ayant un ordre premier est cyclique, tandis que le théorème de Burnside affirme que tout groupe dont l'ordre est divisible par précisément deux nombres premiers peut être résolu.

Méthodes informatiques

Historiquement, la théorie des nombres, et en particulier l'étude des nombres premiers, était largement considérée comme l'exemple par excellence des mathématiques pures, ne possédant aucune application pratique au-delà de l'utilisation de dents d'engrenage à nombre premier pour assurer une répartition uniforme de l'usure. Notamment, des théoriciens des nombres comme le mathématicien britannique G. H. Hardy étaient fiers de mener des recherches dénuées de toute pertinence militaire.

Cette perception de la pureté inhérente à la théorie des nombres a été fondamentalement modifiée dans les années 1970 avec la révélation publique que les nombres premiers pouvaient constituer la base fondamentale du développement d'algorithmes de cryptographie à clé publique. Ces applications pratiques ont stimulé des recherches approfondies sur les algorithmes de calcul impliquant des nombres premiers, en se concentrant particulièrement sur les tests de primalité, des méthodes conçues pour vérifier si un nombre donné est premier. La procédure de test de primalité la plus rudimentaire, la division d'essai, s'avère inefficace pour les grands nombres en raison de sa lenteur de calcul. Même si une catégorie de tests de primalité contemporains convient aux nombres arbitraires, il existe des tests plus efficaces sur le plan informatique pour les nombres présentant des caractéristiques spécifiques. La majorité des tests de primalité indiquent simplement si leur argument d'entrée est premier ou composite. Les algorithmes qui fournissent en outre un facteur premier (ou tous les facteurs premiers) des entrées composites sont appelés algorithmes de factorisation. De plus, les nombres premiers trouvent une utilité en informatique pour des applications telles que les sommes de contrôle, les tables de hachage et les générateurs de nombres pseudo-aléatoires.

Division de première instance

L'approche fondamentale pour vérifier la primalité d'un entier spécifié ⁠ $n$ ⁠ est connu sous le nom de division de première instance. Cette procédure implique de diviser ⁠ $n$ ⁠ par chaque entier allant de 2 jusqu'à sa racine carrée, ⁠ $n$ ⁠. Si l'un de ces entiers divise ⁠ $n$ ⁠ sans reste, puis ⁠ $n$ ⁠ est classé comme composite ; sinon, il est considéré comme premier. Il n'est pas nécessaire d'examiner les entiers dépassant la racine carrée, étant donné que si ⁠ $n=a\cdot b$ ⁠, au moins un des facteurs, ⁠ $a$ ⁠ ou ⁠ $b$ ⁠, doit être inférieur ou égal à la racine carrée de ⁠ $n$ ⁠. Une optimisation supplémentaire consiste à limiter les diviseurs de cette plage aux nombres premiers exclusivement. Par exemple, pour déterminer la primalité de 37, cette technique consiste à le diviser par les nombres premiers compris entre 2 et ⁠ ${\sqrt {37}}$ 183§ {\displaystyle {\sqrt {37}}} ⁠, en particulier 2, 3 et 5. Puisque chaque division donne un reste non nul, 37 est confirmé comme nombre premier.

Bien que conceptuellement simple, cette méthode devient irréalisable pour évaluer la primalité d'entiers substantiels, car le nombre de tests requis augmente de façon exponentielle avec le nombre de chiffres de l'entier. Néanmoins, la division par essais conserve son utilité, souvent utilisée avec une limite de diviseur inférieure à la racine carrée, pour identifier rapidement les nombres composés possédant des facteurs mineurs, avant l'application d'algorithmes plus sophistiqués aux entiers qui passent avec succès cette sélection initiale.

Méthodes de tamisage

Avant l'avènement des ordinateurs, des tableaux mathématiques énumérant les nombres premiers ou leurs factorisations jusqu'à un seuil spécifié étaient régulièrement publiés. L'algorithme reconnu le plus ancien pour compiler une liste de nombres premiers est appelé le Tamis d'Ératosthène. Une variante optimisée de cette méthode a été développée. Une technique de tamisage distincte, offrant une efficacité asymptotique supérieure pour ce problème particulier, est le tamis d'Atkin. Dans des contextes mathématiques avancés, la théorie du tamis étend des méthodologies analogues pour résoudre un spectre plus large de problèmes.

Distinction entre les tests de primalité et la preuve de primalité

Les tests de primalité modernes, en particulier ceux conçus pour la vitesse, utilisent souvent des algorithmes probabilistes (Monte Carlo) pour déterminer si un nombre arbitraire ⁠ $n$ ⁠ est premier. Ces méthodes comportent intrinsèquement une probabilité mineure et aléatoire de produire un résultat erroné. À titre d'illustration, le test de primalité de Solovay-Strassen, lorsqu'il est appliqué à un nombre ⁠ $p$ ⁠, implique la sélection d'un entier aléatoire ⁠ ${\displaystyle a>$ ⁠ de la plage [2, $p-2$ 66§ {\displaystyle p-2} ]. Il utilise ensuite l'exponentiation modulaire pour vérifier si $a^{(p-1)/2}\pm 1$ 93§ ) / §100101§ ± §107108§ {\displaystyle a^{(p-1)/2}\pm 1} est divisible par ⁠ $p$ ⁠. Un résultat positif indique une primalité, tandis qu'un résultat négatif suggère une composition. Devrait ⁠ $p$ ⁠ soit véritablement premier, le test renverra invariablement une affirmation positive. Cependant, si ⁠ $p$ ⁠ est composite, la probabilité d'un faux positif (répondre oui) est d'au plus 1/2, tandis que la probabilité de l'identifier correctement comme composite (répondre non) est d'au moins 1/2.Lorsque ce test est effectué de manière itérative ⁠ $n$ ⁠ fois sur le même nombre, la probabilité qu'un nombre composé réussisse systématiquement toutes les itérations est limitée par ⁠ $1/2^{n}$ 197§ / §203204§ n {\displaystyle 1/2^{n}> ⁠. Cette diminution exponentielle de la probabilité renforce considérablement la certitude qu'un nombre ayant réussi des tests répétés est effectivement premier, même si elle ne fournit pas une certitude absolue. A l’inverse, tout échec unique au test établit définitivement le nombre comme composite. Un nombre composé qui réussit par erreur un tel test de primalité est appelé pseudopremier.

En revanche, certains algorithmes alternatifs offrent une garantie d'exactitude absolue dans leurs déterminations : les nombres premiers sont infailliblement identifiés comme premiers, et les nombres composés sont systématiquement reconnus comme composés. La division de première instance illustre une telle méthode. Les algorithmes qui produisent des résultats vérifiables et corrects englobent à la fois des approches déterministes (non randomisées), comme le test de primalité AKS, et des algorithmes randomisés de Las Vegas. Dans ce dernier cas, les sélections aléatoires effectuées lors de l'exécution ne compromettent pas la précision du résultat final, comme observé dans des implémentations spécifiques de preuve de primalité sur courbe elliptique. Lors de la détermination de la primalité d'un nombre, la méthode de la courbe elliptique génère un certificat de primalité, qui peut être rapidement validé. Bien que le test de primalité de la courbe elliptique soit empiriquement la plus efficace parmi les méthodes garanties correctes, son analyse d'exécution repose sur un raisonnement heuristique plutôt que sur des preuves mathématiques formelles. À l’inverse, le test de primalité AKS possède une complexité temporelle mathématiquement établie, mais il présente des performances pratiques plus lentes que la preuve de primalité par courbe elliptique. Ces techniques facilitent la génération de grands nombres premiers aléatoires en produisant et en testant de manière itérative des nombres entiers aléatoires jusqu'à ce qu'un nombre premier soit identifié. Dans ce processus, un test probabiliste initial plus rapide peut filtrer efficacement la majorité des nombres composés, réservant les algorithmes les plus intensifs en termes de calcul et dont la correction est garantie pour la vérification finale des candidats restants.

Le tableau suivant énumère plusieurs de ces tests. Leur durée opérationnelle est exprimée par rapport à ⁠ $n$ ⁠, qui représente l'entier examiné, et pour les algorithmes probabilistes, la quantité ⁠ $k$ ⁠, désignant le nombre d'itérations effectuées. De plus, $\varepsilon$ signifie une valeur positive arbitrairement petite, et "log" fait référence au logarithme avec une base non spécifiée. La notation grand O implique que chaque limite temporelle nécessite une multiplication par un facteur constant pour la convertir d'unités sans dimension en unités temporelles ; ce facteur dépend des spécificités de l'implémentation, telles que le matériel informatique utilisé, mais reste indépendant des paramètres d'entrée ⁠ $n$ ⁠ et ⁠ $k$ ⁠.

Algorithmes spécialisés et plus grands nombres premiers identifiés

Au-delà des tests généraux de primalité applicables à tout nombre naturel, certains nombres possédant une structure spécifique peuvent subir une évaluation de primalité avec une plus grande efficacité. Par exemple, le test de primalité de Lucas-Lehmer peut déterminer de manière déterministe la primalité d'un nombre de Mersenne (défini comme un moins qu'une puissance de deux) dans le délai de calcul équivalent à une seule itération du test de Miller-Rabin. Par conséquent, depuis 1992 (jusqu'en octobre 2024), le plus grand nombre premier connu a toujours été un nombre premier de Mersenne. Une conjecture dominante postule l'existence d'un nombre infini de nombres premiers de Mersenne.

Le tableau suivant présente les plus grands nombres premiers identifiés dans différentes classifications. Plusieurs de ces nombres premiers ont été découverts grâce à des initiatives de calcul distribué. En 2009, le projet Great Internet Mersenne Prime Search a reçu un prix de 100 000 $ US pour avoir été le premier à identifier un nombre premier comprenant au moins 10 millions de chiffres. L'Electronic Frontier Foundation offre en outre des incitations de 150 000 $ et 250 000 $ pour la découverte de nombres premiers comportant respectivement un minimum de 100 millions et 1 milliard de chiffres.

Factorisation entière

Pour un entier composite donné ⁠ $n$ ⁠, le processus d'identification d'un ou de tous ses facteurs premiers est appelé factorisation de ⁠ $n$ ⁠. Cette opération présente un défi considérablement plus grand que le test de primalité ; malgré l'existence de nombreux algorithmes de factorisation, ils affichent généralement des performances plus lentes par rapport aux méthodologies de test de primalité les plus efficaces. Des techniques telles que la division par essais et l'algorithme rho de Pollard sont applicables pour découvrir de très petits facteurs de ⁠ $n$ ⁠, tandis que la factorisation de courbe elliptique s'avère efficace lorsque ⁠ $n$ ⁠ possède des facteurs d'ampleur modérée. Les méthodes à usage général adaptées à des nombres arbitrairement grands, quelle que soit la taille de leurs facteurs, comprennent le tamis quadratique et le tamis général du champ numérique. De manière analogue aux tests de primalité, certains algorithmes de factorisation sont conçus pour des entrées avec des structures spécifiques, telles que le tamis de champ numérique spécial. En décembre 2019, le plus grand nombre pris en compte avec succès par un algorithme à usage général était RSA-240, qui se compose de 240 chiffres décimaux (795 bits) et représente le produit de deux nombres premiers substantiels.

L'algorithme de Shor offre la possibilité de factoriser n'importe quel entier dans un nombre polynomial d'étapes lorsqu'il est exécuté sur un ordinateur quantique. Néanmoins, les limitations technologiques contemporaines limitent l’application de cet algorithme à de très petits nombres. En octobre 2012, l'entier maximum factorisé avec succès par un ordinateur quantique employant l'algorithme de Shor était de 21.

Applications informatiques supplémentaires

De nombreux algorithmes cryptographiques à clé publique, notamment RSA et l'échange de clés Diffie-Hellman, s'appuient fondamentalement sur de grands nombres premiers, le nombre premier de 2 048 bits étant une norme répandue. Le paradigme de sécurité de RSA repose sur l'asymétrie informatique entre la multiplication de deux grands nombres premiers, ⁠ $x$ ⁠ et ⁠ $y$ ⁠, et factoriser leur produit, $xy$ , pour récupérer les nombres premiers d'origine ⁠ $x$ ⁠ et ⁠ $y$ ⁠ (qui sont supposés être premiers entre eux). À l'inverse, l'échange de clés Diffie-Hellman exploite l'existence d'algorithmes efficaces pour l'exponentiation modulaire (en particulier le calcul ⁠ $a^{b}{\bmod {c}}$ ⁠), contrastant avec la difficulté de calcul perçue de son inverse, le problème du logarithme discret.

Les nombres premiers trouvent une application étendue dans la conception de tables de hachage. Par exemple, le schéma de hachage universel fondamental proposé par Carter et Wegman utilisait des fonctions linéaires aléatoires calculées modulo de grands nombres premiers pour générer des fonctions de hachage. Par la suite, Carter et Wegman ont étendu cette méthodologie pour atteindre ⁠ $k$ ⁠-hachage indépendant grâce à l'utilisation de polynômes de degré supérieur, fonctionnant également modulo de grands nombres premiers. Au-delà de leur rôle dans la construction des fonctions de hachage, les nombres premiers sont également essentiels pour déterminer la taille des tables de hachage dans les schémas de sondage quadratique, garantissant ainsi que la séquence de sondage parcourt efficacement la table entière.

Les propriétés mathématiques des nombres premiers sous-tendent plusieurs algorithmes de somme de contrôle. Par exemple, les sommes de contrôle incorporées dans les numéros ISBN (International Standard Book Numbers) sont dérivées en calculant le reste du nombre lorsqu'il est divisé par 11, qui est un nombre premier. La primalité de 11 permet à cette méthode d'identifier efficacement à la fois les erreurs sur un seul chiffre et les transpositions de chiffres adjacents. De plus, l'algorithme de somme de contrôle Adler-32 utilise l'arithmétique modulo 65521, qui représente le plus grand nombre premier inférieur à ⁠ $2^{16}$ 9§ 16 {\displaystyle 2^{16}} ⁠. De plus, les nombres premiers font partie intégrante de divers générateurs de nombres pseudo-aléatoires, tels que les générateurs congruentiels linéaires et le Mersenne Twister.

Autres applications

Bien qu'ils soient essentiels à la théorie des nombres, les nombres premiers possèdent également des applications significatives dans divers domaines mathématiques, notamment l'algèbre abstraite et la géométrie élémentaire. Par exemple, il existe des configurations dans lesquelles un nombre premier de points peuvent être disposés sur une grille bidimensionnelle de telle sorte qu'aucun point ne soit colinéaire, ou bien, de telle sorte que tout triangle formé par trois de ces points renferme une zone substantielle. Une autre illustration est le critère d'Eisenstein, qui fournit un test d'irréductibilité polynomiale en examinant la divisibilité de ses coefficients par un nombre premier et son carré.

La nature fondamentale des nombres premiers a conduit à leur généralisation dans diverses disciplines mathématiques. Généralement, le terme « premier » désigne la minimalité ou l'indécomposabilité dans un contexte mathématique spécifique. Par exemple, le corps premier associé à un corps donné représente son sous-champ minimal englobant à la fois 0 et 1. Ce corps premier est soit le corps des nombres rationnels, soit un corps fini caractérisé par un nombre premier d'éléments, ce qui explique sa nomenclature. De plus, le terme « premier » implique souvent un sens secondaire : la capacité pour tout objet d'être décomposé de manière unique en ses constituants premiers fondamentaux. Dans la théorie des nœuds, par exemple, un nœud premier est défini comme un nœud indécomposable, ce qui signifie qu'il ne peut pas être exprimé comme la somme connectée de deux nœuds non triviaux. Chaque nœud possède une représentation unique en tant que somme connectée de nœuds premiers. La décomposition première des variétés 3 constitue une autre illustration de ce principe.

Au-delà de leurs applications en mathématiques et en informatique, les nombres premiers présentent des liens potentiels avec la mécanique quantique et ont été utilisés métaphoriquement dans des contextes artistiques et littéraires. De plus, ils ont trouvé leur utilité en biologie évolutive pour élucider les cycles de vie des cigales.

Polygones constructibles et partitions de polygones

Les nombres premiers de Fermat sont définis comme des nombres premiers conformes à la structure :

F_{k}=2^{2^{k}}+1,

33§ , {\displaystyle F_{k}=2^{2^{k}}+1,}

où ⁠ $k$ ⁠ désigne un entier non négatif. Ces nombres sont nommés en l'honneur de Pierre de Fermat, qui a émis l'hypothèse que tous les nombres de cette forme sont premiers. Alors que les cinq nombres de Fermat initiaux (3, 5, 17, 257 et 65 537) sont premiers, $F_{5}$ est composite, une caractéristique partagée par tous les autres nombres de Fermat vérifiés jusqu'en 2017. Un ⁠ $n$ ⁠-gon peut être construit en utilisant uniquement une règle et un compas si et seulement si ses facteurs premiers impairs (s'il en existe) sont des nombres premiers de Fermat distincts. De même, un ⁠ $n$ ⁠-gon peut être construit à l'aide d'une règle, d'un compas et d'un trisecteur d'angle si et seulement si les facteurs premiers de ⁠ $n$ ⁠ se composent d'un nombre quelconque de facteurs de 2 ou 3, combinés avec un ensemble (potentiellement vide) de nombres premiers de Pierpont distincts, qui sont des nombres premiers de la forme ⁠ $2^{a}3^{b}+1$ 121§ un §128 $129§ b$ + §137138§ {\displaystyle 2^{a}3^{b}+1} ⁠.

Tout polygone convexe peut être divisé en ⁠ $n$ ⁠ polygones convexes plus petits, chacun possédant une superficie égale et un périmètre égal, à condition que ⁠ $n$ ⁠ est une puissance d'un nombre premier ; cependant, cette propriété reste non confirmée pour les autres valeurs de ⁠ $n$ ⁠.

Mécanique quantique

Depuis les années 1970, à partir des recherches menées par Hugh Montgomery et Freeman Dyson, les mathématiciens et les physiciens ont établi une corrélation entre les zéros de la fonction zêta de Riemann et les niveaux d'énergie observés dans les systèmes quantiques. De plus, les nombres premiers revêtent une importance considérable dans la science de l'information quantique, en raison de leur rôle dans des constructions mathématiques telles que des bases mutuellement impartiales et des mesures symétriques informationnellement complètes à valeur d'opérateur positif.

Biologie

Le genre de cigales, Magicicada, utilise une stratégie évolutive qui intègre les nombres premiers. Ces insectes passent la majeure partie de leur existence sous forme de larves souterraines, pour ensuite se nymphoser et sortir de leur terrier après précisément 7, 13 ou 17 ans. Après leur émergence, ils s'envolent, se reproduisent et périssent ensuite en quelques semaines. Les biologistes postulent que ces durées de cycle de reproduction avec des nombres premiers ont évolué comme un mécanisme empêchant la synchronisation des prédateurs avec leurs cycles de vie. À l'inverse, les intervalles pluriannuels entre les événements de floraison chez les espèces de bambou sont supposés être des nombres lisses, caractérisés par des factorisations contenant uniquement de petits nombres premiers.

Arts et littérature

Les nombres premiers ont exercé une influence notable sur de nombreux artistes et personnalités littéraires. Le compositeur français Olivier Messiaen, par exemple, a utilisé les nombres premiers pour construire une musique amétrique, en s'inspirant des « phénomènes naturels ». Dans des compositions telles que La Nativité du Seigneur (1935) et Quatre études de rythme (1949-1950), Messiaen déploie simultanément des motifs musicaux dont les durées correspondent à des nombres premiers distincts, générant ainsi des motifs rythmiques imprévisibles. Plus précisément, les nombres premiers 41, 43, 47 et 53 sont évidents dans la troisième étude, intitulée « Neumes rythmiques ». Messiaen lui-même a expliqué que cette approche compositionnelle était « inspirée par les mouvements de la nature, des mouvements de durées libres et inégales ».

Dans son roman de science-fiction Contact, le scientifique Carl Sagan a proposé que la factorisation première pourrait servir de méthode pour établir des plans d'images bidimensionnels lors de la communication avec l'intelligence extraterrestre, un concept qu'il a initialement formulé de manière informelle avec l'astronome américain Frank Drake en 1975. Le roman de Mark Haddon The Curious Incident of The Dog in the Night-Time met en scène un narrateur qui structure les sections narratives à l'aide de nombres premiers consécutifs, véhiculant ainsi l'état psychologique du protagoniste, un adolescent doué en mathématiques et atteint du syndrome d'Asperger. De plus, les nombres premiers fonctionnent comme une métaphore de la solitude et de l'isolement dans le roman de Paolo Giordano La Solitude des nombres premiers, où ils sont décrits comme des « étrangers » au sein de l'ensemble des nombres entiers.

Références

"Nombre premier." Encyclopédie des mathématiques. Presse EMS, 2001 [1994].

"Nombre premier". Encyclopédie des mathématiques. Presse EMS. 2001 [1994].À notre époque, BBC.
"Pack enseignant : Nombres premiers." Plus, 1er décembre 2008, produit par le Millennium Mathematics Project de l'Université de Cambridge.

Le calculateur de facteurs premiers peut factoriser n'importe quel entier positif jusqu'à 20 chiffres.
Énorme base de données de nombres premiers.
Nombres premiers jusqu'à 1 000 milliards. Archivé le 27/02/2021 sur la Wayback Machine .

Nombre premier (Prime number)