Nombres Premiers : Définition, Propriétés et Liste 100

Les nombres premiers constituent l’une des notions les plus fondamentales et fascinantes des mathématiques. Depuis l’Antiquité jusqu’à nos jours, ces nombres intriguent les mathématiciens et trouvent des applications essentielles en cryptographie moderne. Dans ce guide complet, nous explorerons en profondeur la définition, les propriétés remarquables, les méthodes de détermination et les théorèmes qui régissent ces nombres exceptionnels.

Qu’est-ce qu’un nombre premier : Définition fondamentale

Cette définition mérite plusieurs précisions importantes. Tout nombre entier possède au moins deux diviseurs triviaux : 1 et le nombre lui-même. Les nombres premiers se distinguent en n’ayant aucun autre diviseur. Par exemple, le nombre 7 est premier car ses seuls diviseurs sont 1 et 7. En revanche, 12 n’est pas premier car il possède six diviseurs : 1, 2, 3, 4, 6 et 12.

Pourquoi 1 n’est-il pas considéré comme un nombre premier ?

Le nombre 1 occupe un statut particulier en arithmétique. Bien qu’historiquement certains mathématiciens l’aient considéré comme premier, la convention moderne exclut 1 des nombres premiers. Cette décision n’est pas arbitraire : elle garantit l’unicité de la décomposition en facteurs premiers, pierre angulaire du théorème fondamental de l’arithmétique. Si 1 était premier, tout nombre pourrait s’écrire d’une infinité de façons différentes en incluant autant de facteurs 1 que souhaité.

Les premiers nombres premiers

Voici la liste complète des vingt-cinq nombres premiers inférieurs à 100 :

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

On remarque que 2 est le seul nombre premier pair, car tous les autres nombres pairs sont divisibles par 2. De plus, à l’exception de 2 et 5, tous les nombres premiers se terminent par 1, 3, 7 ou 9, car les nombres se terminant par 0, 2, 4, 6, 8 sont pairs et ceux se terminant par 5 sont multiples de 5.

Nombres composés et décomposition en facteurs premiers

Par opposition aux nombres premiers, on appelle nombre composé tout entier naturel supérieur à 1 qui possède au moins trois diviseurs positifs. Autrement dit, un nombre composé peut s’écrire comme le produit de deux entiers strictement supérieurs à 1.

Ce théorème affirme que les nombres premiers sont les « briques élémentaires » de tous les entiers. Pour un nombre \( n \geq 2 \), il existe des nombres premiers \( p_1, p_2, \ldots, p_r \) et des exposants entiers \( \alpha_1, \alpha_2, \ldots, \alpha_r \geq 1 \) tels que :

Par exemple, la décomposition de 360 en facteurs premiers s’écrit :

Cette décomposition permet de déterminer facilement le plus grand commun diviseur (PGCD) et le plus petit commun multiple (PPCM) de deux nombres, notions essentielles en arithmétique.

Le crible d’Ératosthène : méthode classique de détermination

Le crible d’Ératosthène est un algorithme ancien et élégant permettant de trouver tous les nombres premiers inférieurs à un entier donné \( N \). Inventé par le mathématicien grec Ératosthène de Cyrène au IIIe siècle avant J.-C., ce procédé reste aujourd’hui l’une des méthodes les plus efficaces pour générer des listes de nombres premiers.

Principe de fonctionnement

L’algorithme procède par éliminations successives :

1. On écrit tous les entiers de 2 à \( N \) dans un tableau
2. On commence par le plus petit nombre non barré (initialement 2)
3. On entoure ce nombre : c’est un nombre premier
4. On barre tous ses multiples stricts (c’est-à-dire tous les nombres de la forme \( kp \) où \( k \geq 2 \))
5. On passe au nombre suivant non barré et on répète l’opération
6. On peut s’arrêter dès que le nombre considéré dépasse \( \sqrt{N} \)

Cette dernière optimisation repose sur un principe fondamental : si un nombre \( n \) est composé, alors il possède nécessairement un diviseur inférieur ou égal à \( \sqrt{n} \). En effet, si \( n = a \times b \) avec \( a \) et \( b \) tous deux supérieurs à \( \sqrt{n} \), alors \( n = a \times b > \sqrt{n} \times \sqrt{n} = n \), ce qui est impossible.

Exemple appliqué : nombres premiers jusqu’à 50

Pour déterminer les nombres premiers inférieurs à 50, on commence par écrire tous les entiers de 2 à 50. Ensuite, on élimine les multiples de 2 (sauf 2), puis les multiples de 3 (sauf 3), puis les multiples de 5 (sauf 5), et enfin les multiples de 7 (sauf 7). Puisque \( \sqrt{50} \approx 7{,}07 \), on peut s’arrêter après avoir traité les multiples de 7. Les nombres restants sont tous premiers.

Théorème d’Euclide : infinité des nombres premiers

L’un des résultats les plus remarquables de la théorie des nombres est l’infinité des nombres premiers. Cette démonstration, attribuée à Euclide et figurant dans ses Éléments (livre IX, proposition 20), utilise un raisonnement par l’absurde d’une élégance remarquable.

Démonstration

Supposons par l’absurde qu’il n’existe qu’un nombre fini de nombres premiers. Notons-les \( p_1, p_2, p_3, \ldots, p_k \). Considérons alors le nombre :

Ce nombre \( N \) est strictement supérieur à 1, donc il admet au moins un diviseur premier. Soit \( p \) un tel diviseur premier. Deux cas se présentent :

Premier cas : Si \( p \) appartient à la liste \( \{p_1, p_2, \ldots, p_k\} \), alors \( p \) divise le produit \( p_1 \times p_2 \times \cdots \times p_k \). Puisque \( p \) divise également \( N \), il doit diviser leur différence :

Or aucun nombre premier ne peut diviser 1. Nous aboutissons à une contradiction.

Second cas : Si \( p \) n’appartient pas à la liste initiale, alors nous avons trouvé un nombre premier qui ne figurait pas dans notre liste supposée complète. C’est encore une contradiction.

Dans les deux cas, notre hypothèse de départ était fausse. Il existe donc nécessairement une infinité de nombres premiers.

Attention : Ce raisonnement ne prouve pas que \( N \) lui-même est premier, mais seulement qu’il possède au moins un diviseur premier qui ne figurait pas dans la liste initiale. Par exemple, avec les trois premiers nombres premiers 2, 3 et 5, on obtient \( N = 2 \times 3 \times 5 + 1 = 31 \), qui est effectivement premier. Mais avec 2, 3, 5 et 7, on obtient \( N = 2 \times 3 \times 5 \times 7 + 1 = 211 \), qui est également premier. Cependant, avec les cinq premiers, on obtient \( N = 2 \times 3 \times 5 \times 7 \times 11 + 1 = 2311 \), qui reste premier, mais en poursuivant, on trouve des contre-exemples où \( N \) est composé.

Propriétés remarquables des nombres premiers

Les nombres premiers possèdent de nombreuses propriétés arithmétiques fondamentales qui en font des objets mathématiques d’une importance capitale.

Lemme d’Euclide

Cette propriété peut sembler évidente, mais elle est essentielle et caractérise les nombres premiers. En notation mathématique :

Cette propriété se généralise à un produit quelconque : si un nombre premier divise un produit de plusieurs facteurs, il divise nécessairement au moins l’un de ces facteurs.

Nombres premiers entre eux

Deux entiers \( a \) et \( b \) sont dits premiers entre eux si leur plus grand commun diviseur vaut 1, c’est-à-dire s’ils ne partagent aucun diviseur commun autre que 1. On note cette relation \( \text{pgcd}(a, b) = 1 \).

Quelques propriétés importantes :

• Deux nombres premiers distincts sont toujours premiers entre eux
• Si \( p \) est premier et si \( p \) ne divise pas \( a \), alors \( p \) et \( a \) sont premiers entre eux
• Si \( a \) et \( b \) sont premiers entre eux et si \( a \) divise \( b \times c \), alors \( a \) divise \( c \) (théorème de Gauss)

Test de primalité par division

Pour déterminer si un nombre \( n \) est premier, il suffit de vérifier qu’aucun nombre premier inférieur ou égal à \( \sqrt{n} \) ne le divise. Si tous ces tests de divisibilité échouent, alors \( n \) est nécessairement premier.

Par exemple, pour tester si 223 est premier, on calcule \( \sqrt{223} \approx 14{,}93 \). Il suffit donc de vérifier que 223 n’est divisible par aucun des nombres premiers inférieurs à 15, c’est-à-dire 2, 3, 5, 7, 11 et 13. Si aucune de ces divisions n’est exacte, alors 223 est premier.

Nombres de Mersenne et records de primalité

Les nombres de Mersenne sont des nombres de la forme \( M_n = 2^n – 1 \), où \( n \) est un entier naturel. Ils doivent leur nom au moine français Marin Mersenne (1588-1648), qui les étudia au XVIIe siècle. Lorsqu’un nombre de Mersenne est premier, on parle de nombre premier de Mersenne.

Propriétés des nombres de Mersenne

La démonstration repose sur une factorisation algébrique. Si \( n = a \times b \) avec \( a, b > 1 \), alors :

Or cette expression se factorise selon l’identité algébrique \( x^b – 1 = (x-1)(x^{b-1} + x^{b-2} + \cdots + x + 1) \), ce qui montre que \( 2^n – 1 \) est composé.

Attention : La réciproque est fausse. Par exemple, 11 est premier, mais \( M_{11} = 2^{11} – 1 = 2047 = 23 \times 89 \) n’est pas premier.

Les plus grands nombres premiers connus

Depuis plusieurs décennies, les plus grands nombres premiers découverts sont presque toujours des nombres de Mersenne. Cette prédominance s’explique par l’existence du test de primalité de Lucas-Lehmer, exceptionnellement rapide pour ces nombres particuliers.

En octobre 2024, le plus grand nombre premier connu est \( M_{136279841} = 2^{136279841} – 1 \), découvert le 12 octobre 2024. Ce nombre colossal possède plus de 41 millions de chiffres décimaux. Cette découverte a été réalisée grâce au projet collaboratif GIMPS (Great Internet Mersenne Prime Search), qui utilise des milliers d’ordinateurs répartis dans le monde entier.

Les premiers nombres premiers de Mersenne sont :

Nombres premiers jumeaux et conjectures célèbres

Deux nombres premiers sont dits jumeaux lorsqu’ils sont consécutifs dans la liste ordonnée des nombres premiers et que leur différence vaut exactement 2. Par exemple, (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43) sont des paires de nombres premiers jumeaux.

La conjecture des nombres premiers jumeaux

L’une des questions non résolues les plus célèbres en mathématiques concerne l’infinité des nombres premiers jumeaux. Cette conjecture, formulée depuis plus d’un siècle, affirme qu’il existe une infinité de paires de nombres premiers dont la différence vaut 2.

Malgré de nombreuses tentatives, cette conjecture n’a jamais été démontrée ni réfutée. Cependant, des progrès significatifs ont été réalisés ces dernières années. En 2013, le mathématicien chinois Yitang Zhang a démontré qu’il existe une infinité de paires de nombres premiers dont l’écart est inférieur à 70 millions. Ce résultat, bien qu’éloigné de la conjecture originale, constituait une percée majeure.

Par la suite, James Maynard et Terence Tao ont considérablement amélioré ce résultat. Le projet collaboratif Polymath8 a finalement démontré qu’il existe une infinité de paires de nombres premiers dont la différence est inférieure à 246. Si ce résultat reste encore loin de prouver la conjecture des nombres premiers jumeaux, il représente une avancée remarquable dans la compréhension de la distribution des nombres premiers.

Théorème des nombres premiers et distribution asymptotique

Au-delà de savoir qu’il existe une infinité de nombres premiers, les mathématiciens se sont interrogés sur leur distribution parmi les entiers naturels. Le théorème des nombres premiers, démontré indépendamment par Jacques Hadamard et Charles-Jean de La Vallée Poussin en 1896, répond partiellement à cette question.

On note \( \pi(x) \) le nombre de nombres premiers inférieurs ou égaux à \( x \). Par exemple, \( \pi(10) = 4 \) car il y a quatre nombres premiers inférieurs à 10 : 2, 3, 5 et 7.

Cette équivalence asymptotique signifie que le quotient \( \dfrac{\pi(x)}{x/\ln(x)} \) tend vers 1 lorsque \( x \) tend vers l’infini. En d’autres termes, pour des valeurs de \( x \) suffisamment grandes, on peut estimer le nombre de nombres premiers inférieurs à \( x \) en calculant approximativement \( \dfrac{x}{\ln(x)} \).

Ce théorème fondamental révèle que les nombres premiers se raréfient progressivement : la « densité » des nombres premiers autour d’un entier \( n \) est approximativement \( \dfrac{1}{\ln(n)} \). Par exemple, autour de 1 million, environ un nombre sur 14 est premier, tandis qu’autour de 1 milliard, seulement un nombre sur 21 est premier.

Applications modernes des nombres premiers

Longtemps considérés comme un domaine purement théorique des mathématiques, les nombres premiers ont trouvé des applications pratiques essentielles au cours des dernières décennies, notamment dans le domaine de la cryptographie.

Cryptographie RSA

Le système de cryptographie RSA, inventé en 1978 par Ronald Rivest, Adi Shamir et Leonard Adleman, repose entièrement sur les propriétés des nombres premiers. Ce système de chiffrement asymétrique utilise deux clés différentes : une clé publique pour chiffrer les messages et une clé privée pour les déchiffrer.

Le principe fondamental du RSA exploite le fait qu’il est facile de multiplier deux grands nombres premiers, mais extrêmement difficile de factoriser le produit obtenu. Par exemple, multiplier deux nombres premiers de 200 chiffres chacun est une opération quasi instantanée sur un ordinateur moderne. En revanche, retrouver ces deux facteurs premiers à partir du produit (qui possède environ 400 chiffres) nécessiterait des millions d’années de calcul avec les algorithmes actuels.

Cette asymétrie entre la facilité de la multiplication et la difficulté de la factorisation constitue le fondement de la sécurité du chiffrement RSA, utilisé aujourd’hui pour sécuriser les communications sur Internet, les transactions bancaires et les signatures numériques.

Autres applications

Au-delà de la cryptographie, les nombres premiers interviennent dans de nombreux domaines :

• Informatique théorique : génération de nombres pseudo-aléatoires, tables de hachage
• Musique : certaines structures rythmiques utilisent des nombres premiers pour créer des motifs non répétitifs
• Biologie : certaines espèces de cigales émergent selon des cycles de 13 ou 17 ans, évitant ainsi la synchronisation avec les prédateurs
• Théorie des jeux : stratégies optimales basées sur des séquences de nombres premiers

Conclusion et perspectives

Les nombres premiers représentent l’un des objets mathématiques les plus fascinants et les plus étudiés de l’histoire des mathématiques. Depuis les travaux fondateurs d’Euclide jusqu’aux découvertes les plus récentes, ces nombres n’ont cessé d’intriguer les mathématiciens par leur apparente simplicité et leur complexité cachée.

Nous avons exploré dans ce guide les aspects essentiels de la théorie des nombres premiers : leur définition rigoureuse, le crible d’Ératosthène pour les déterminer, le théorème d’Euclide prouvant leur infinité, les nombres de Mersenne qui permettent de découvrir les plus grands nombres premiers connus, et les conjectures célèbres comme celle des nombres premiers jumeaux qui restent à ce jour non résolues.

Les nombres premiers constituent les fondations de l’arithmétique moderne et trouvent des applications concrètes dans la cryptographie qui sécurise nos communications numériques quotidiennes. Malgré des millénaires de recherches, de nombreux mystères persistent, comme la répartition exacte des nombres premiers ou l’existence d’une infinité de nombres premiers jumeaux.

L’étude des nombres premiers reste un domaine de recherche actif en mathématiques, attirant aussi bien les mathématiciens professionnels que les passionnés du monde entier à travers des projets collaboratifs comme GIMPS.

Questions fréquemment posées sur les nombres premiers