Les nombres premiers

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 <= racine 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. Cette décomposition est unique (c’est ce principe que l’on utilise pour simplifier des fractions).

Par exemple, 180 = 2² × 3² × 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, 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.