Introduction aux nombres premiers
Les mathématiciens ont toujours été fascinés par les nombres premiers. Impossible par exemple de trouver le moyen de tous les engendrer ou de trouver une logique dans leurs apparitions. Certains ont cherché avec plus ou moins de bonheur des formules indiquant qu’un nombre est premier (Mersenne puis Fermat, par exemple). Âgé de quatorze ans, Gauss conjectura que le nombre de nombres premiers inférieurs à un entier naturel \(n\) est égal au quotient de \(n\) par son logarithme népérien. Pourtant, malgré les tentatives de milliers de chercheurs d’énigmes capables des plus belles prouesses intellectuelles, il y a fort à parier que cette forteresse de l’arithmétique tiendra bon.
Leur rôle est primordial en arithmétique puisqu’ils permettent d’obtenir tous les entiers. Il est également essentiel en cryptographie.
Définitions
Un entier naturel est un nombre premier s’il admet exactement deux diviseurs : 1 et lui-même.
Il a longtemps été admis que 1 était un nombre premier mais comme il n’admet qu’un seul diviseur, on ne le considère plus comme tel. Le plus petit est donc 2 (qui d’ailleurs est le seul nombre premier pair).
Un entier qui n’est pas premier est un nombre composé, à l’exception de 0 et 1 qui ne sont ni l’un ni l’autre.
Théorème
Tout entier supérieur ou égal à 2 admet au moins un diviseur premier.
Primalité
Tout nombre non premier \(n\) supérieur à 2 admet un nombre premier \(p\) tel que \(p\) divise \(n\) et \(p \leqslant \sqrt{n}.\)
Donc, si \(n\) n’est divisible par aucun nombre premier inférieur à la racine carrée de \(n,\) alors \(n\) est premier (c’est d’ailleurs assez évident !).
Exemple : pour savoir si 613 est un nombre premier, on calcule sa raciné carrée. Soit environ 24,8. On cherche donc si 613 a un diviseur entre 2 et 24. Il est inutile d’aller au-delà (et il est également inutile de chercher à le diviser par des nombres qui ne sont pas premiers).
Il y a 2 200 ans, Ératosthène, qui par ailleurs démontra que la Terre était sphérique et en donna une assez bonne mesure, élabora un procédé pour déterminer si un nombre \(n\) est premier. Sa technique est connue sous l’expression « crible d’Ératosthène ». On écrit tous les nombres de 2 à \(n.\) On retient 2 et, si \(n\) n’est pas divisible par 2, on raye tous les multiples de 2. Puis on recommence avec tous les nombres premiers suivants : 3, 5, 7, 11… Tous les nombres non rayés, y compris éventuellement \(n,\) sont premiers.
Bien sûr, la méthode devient délicate à mettre en œuvre sur des nombres très grands. Aujourd’hui, on connaît des nombres premiers qui s’écrivent avec des dizaines de millions de chiffres.
Propriété
Soit \(n\) et \(m\) deux entiers relatifs non nuls et \(p\) un nombre premier. Si \(p\) divise \(nm,\) alors il divise \(n\) ou \(m.\)
Théorème fondamental de l’arithmétique
Tout entier naturel supérieur ou égal à 2 peut s’écrire comme un produit de nombres premiers (écriture appelée décomposition primaire). Cette décomposition est unique, (c’est ce principe que l’on utilise pour simplifier des fractions).
Par exemple, \(180 = 2^2 × 3^2 × 5.\)
Il n’est pas difficile de trouver ce résultat, même sans calculatrice. On prend le plus petit nombre premier : 2. On voit que l’on peut diviser 180 par 2 (oui, c’est un nombre pair). Résultat : 90. Encore un nombre pair, donc une deuxième division par 2. On obtient 45. Ce nombre étant impair, on passe au nombre premier suivant : 3. Pour savoir si un nombre est divisible par 3, on vérifie si la somme de ses chiffres donne un multiple de 3. Il se trouve que \(4 + 5 = 9.\) On divise donc 45 par 3 et on obtient 15. Lui aussi divisible par 3. On obtient 5. Ce nombre étant premier, on le retient et on en reste là.
Infinité
Il existe une infinité de nombres premiers.
La preuve a été apportée grâce à la première démonstration par l’absurde qui nous soit parvenue. Elle est due à Euclide.
Si l’ensemble des nombres premiers était fini, il existerait un nombre premier plus grand que tous les autres. Supposons que ce soit le cas.
Multiplions à présent tous les nombres premiers entre eux. On peut le faire puisqu’on suppose qu’ils ne sont pas une infinité. On obtient un entier \(q.\) Soit à présent le nombre \(q + 1.\) Comme l’ensemble des nombres premiers est supposé fini, \(q + 1\) est un composé. Il est donc divisible par au moins un nombre premier \(p.\)
Par conséquent, \(p\) divise à la fois \(q\) et \(q + 1.\)
Donc, \(p\) divise aussi leur différence, c’est-à-dire 1. Mais ceci est absurde car aucun nombre premier ne divise 1.
Donc l’ensemble des nombres premiers est infini.
Pour mémoire, Euler a lui aussi apporté la preuve de l’infinité des nombres premiers. Sa démonstration est beaucoup moins simple !
Chaos inexplicable
L’apparition des nombres premiers semble n’obéir à aucune règle. Les plus petits sont très rapprochés (2, 3, 5, 7…). Bien sûr, lorsque les entiers deviennent très grands on en trouve beaucoup moins. Il peut exister des suites de trillons de nombres composés avant qu’apparaisse un nombre premier.
Les nombres premiers sont dit « jumeaux » lorsqu’ils ne sont séparés que de deux unités. Par exemple 197 et 199. Mais on a aussi trouvé en 2016 deux nombres jumeaux de près de 400 000 chiffres. Alors oui, la fréquence d’apparition des nombres premiers est très chaotique !
La conjecture de Goldbach
Dans une lettre à son ami Euler, le mathématicien allemand Christian Goldbach (1690 – 1764) a émis la conjecture selon laquelle tout nombre pair supérieur à 2 est la somme de deux nombres premiers.
Exemple : \(100 = 47 + 53.\)
Cette conjecture a toujours été vérifiée, même sur des nombres immensément grands mais pas sur tous puisque, là encore, aucune démonstration n’a pour l’instant été apportée.
Le postulat de Bertrand
Le Français Joseph Bertrand a lui aussi émis un postulat, qui a ensuite été démontré, d'abord par le Russe Pafnouti Thebychev puis d'une autre façon par le Hongrois Paul Erdös. C'est donc à présent un théorème : entre tout nombre et son double, il existe au moins un nombre premier. Par exemple, entre 2 et 4 il y a 3, entre 5 et 10 il y a 7, entre 20 et 40 il y a 23 (et d'autres), etc.