Les nombres premiers

On désire disposer régulièrement n billes pour former un rectangle complet, non réduit à une ligne :

Si on y arrive, n est le produit de 2 nombres. Ci-dessus : 12 = 3 (lignes) x 4 (colonnes). On dit que n est un nombre composé.
Si on n’y arrive pas, n ne se décompose pas en produit de deux nombres, on dit que n est un nombre premier.
On voit ci-dessous que 7 est un nombre premier.

 

Un nombre premier est donc un nombre dont ses seuls diviseurs sont 1 et lui-même. Citons quelques nombres premiers : 2, 3, 5, 7, 11, 13, 17, 19, … et quelques plus grands : 22 091, 9 576 890 767 ou encore ce géant :

95 647 806 479 275 528 135 733 781 266 203 904 794 419 563 064 407.

Amusez-vous à leurs trouver un diviseur autre que 1 ou eux-mêmes …!

 

Les plus anciennes traces des nombres premiers ont été trouvées près du lac Edouard au Zaïre sur un os (de plus de 20000 ans), l’os d’Ishango, recouvert d’entailles marquant les nombres premiers 11, 13, 17 et 19. Est-ce ici l’ébauche d’une table de nombres premiers ou cette correspondance est-elle due au hasard ?

On peut supposer aussi, que par leurs travaux sur les nombres, égyptiens et babyloniens ont certainement été menés à rencontrer des nombres premiers, mais nous ne possédons aucune preuve à ce sujet.

Un peu plus tard, les grecs de l’Ecole Pythagoricienne, passionnés par l’arithmétique, étudieront la notion de diviseur et les nombres parfaits (nombre égal à la somme de ses diviseurs propres).

Par exemple, 28 est un nombre parfait, car 28 = 1 + 2 + 4 + 7 + 14.

Euclide d'Alexandrie (-320? ; -260?)

C’est avec Euclide d'Alexandrie (-320? ; -260?), que les théories sur les nombres premiers se mettent en place.
Dans « Les éléments » (livres VII, VIII, IX), il donne des définitions, des propriétés et démontre certaines affirmations du passé, comme l’existence d’une infinité de nombres premiers.

« Les nombres premiers sont en quantité plus grande que toute quantité proposée de nombres premiers ».

Il présente aussi la décomposition en facteurs premiers liée à la notion de PGCD.

Exemple : 30 se décompose en 2 x 3 x 5 et 70 se décompose en 2 x 5 x 7. Tous les facteurs sont des nombres premiers.
Les diviseurs de 30 sont : 1, 2, 3, 5, 6, 10, 15 et 30
Les diviseurs de 70 sont : 1, 2, 5, 7, 10, 14, 35 et 70
Les diviseurs communs à 30 et 70 sont : 1, 2, 5 et 10. Le plus grand est 10.
On dit que 10 est le PGCD (Plus Grand Commun Diviseur) de 30 et 70.

Cette méthode permettant de déterminer le PGCD de deux nombres voit vite ses limites. Euclide a laissé son nom à un algorithme étudié en 3e et permettant de calculer le PGCD de deux nombres. Pour obtenir plus de détails et essayer l'algorithme d'Euclide, cliquez sur le lien en bas de page.

On dit aussi de deux nombres qu’ils sont premiers entre eux si leur PGCD est égal à 1. Par exemple, 15 et 77 sont premiers entre eux.

 

Eratosthène de Cyrène (-276 ; -194)

Un autre grec, Eratosthène de Cyrène (-276 ; -194), est l’auteur d’un célèbre crible qui permet par une méthode simple d'obtenir des nombres premiers ! Par éliminations successives des multiples des premiers nombres premiers de la liste, on obtient les suivants.

Image M.Qrius

 

Il faudra ensuite attendre plusieurs siècles et le développement de la numération indienne pour voir apparaître de nouvelles avancées. De plus, la naissance de la trigonométrie et le développement de l’algèbre occupent déjà beaucoup les mathématiciens de l’époque et ne les incitent guère à se lancer dans des problèmes d’arithmétique.

On observe tout de même quelques recherches en Chine et dans le monde musulman avec al-Marrakushi ibn Al-Banna (1258 ; 1339) qui fait progresser le crible d’Eratosthène.

Et en Italie, Léonard de Pise dit Fibonacci (1170 ; 1250) donne une liste complète de nombres premiers et étudie certains critères de divisibilité.

 

Marin Mersenne (1588 ; 1648)

C’est un ecclésiastique français, Marin Mersenne qui apporte un souffle nouveau à la recherche sur les nombres premiers. Il en propose une famille nouvelle qui repose sur la question suivante :

« Si p est un nombre premier, 2^p - 1 est-il un nombre premier ? »

La réponse est non, mais il affirme à raison que c’est vrai pour p = 2, 3, 5, 7, 13, 17, 19, 31. Il ne démontrera pas sa découverte et fera quelques erreurs sur des nombres plus grands. Elle est pourtant remarquable et est encore utilisée aujourd’hui pour la recherche de nombres premiers géants.

Avec p=19 , par exemple, on obtient le nombre premier 2¹⁹ - 1, soit 524 287.

 

Mersenne entretient des correspondances avec les grands mathématiciens de l’époque tels que Blaise Pascal (1623 ; 1662) ou Pierre de Fermat (1601 ; 1665). C’est ce dernier qui est l’auteur de la plus célèbre conjecture des mathématiques :

« L’équation xⁿ + yⁿ = zⁿ n’a pas de solution avec x, y, z > 0 et n > 2 ».

Fermat prétendait en détenir une preuve étonnante, mais il inscrivit dans la marge d’un ouvrage de Diophante d'Alexandrie (IIIème siècle de notre ère) ne pas avoir assez de place pour la rédiger !!! ? Il fallu attendre trois siècles et demi pour qu’en 1995, un anglais, Andrew Wiles, en vienne à bout et empoche récompenses et célébrité.

Plus tard, Christian Goldbach (1690 ; 1764) affirmera que « Tout nombre pair supérieur à 2 est la somme de deux nombres premiers. »
A l’heure où vous lisez ces lignes, cette conjecture dont l’énoncé est pourtant très simple, reste sans preuve. Vous souhaitez vous aussi devenir célèbre … lancez-vous alors dans sa démonstration !

A partir du XVIII ème siècle, les mathématiciens s’acharnent à battre les records en démontrant l’existence de nombres premiers de plus en plus grands.
Le suisse Leonhard Euler (1707 ; 1783) prouve que 2³¹ - 1 est premier. L'allemand Carl Friedrich Gauss (1777 ; 1855) et le français Adrien-Marie Legendre (1752 ; 1833) s’intéressent à leur répartition et démontrent que les nombres premiers se raréfient parmi les grands nombres.

Formule de Minàc-Willans permettant de générer les nombres premiers

L’histoire évolue plus rapidement encore avec les progrès des méthodes de calculs et l’apparition de nouvelles formules de plus en plus performantes. Mais c’est quand l’ordinateur prend le relais de l’homme que les nombres premiers découverts (calculés) deviennent "astronomiques".

Aujourd’hui le plus grand nombre premier connu est un nombre de Mersenne, le 51ème, 2^{82 589 933} - 1, qui comprend 24 862 048 de chiffres et qui a été découvert le 7 décembre 2018 par un réseau d’ordinateurs (projet GIMPS) permettant d’accélérer les recherches de façon considérable en distribuant les calculs.
Télécharger ce nombre.
Télécharger des nombres de Mersenne.

Avec votre modeste ordinateur, vous pouvez aussi contribuer à ce projet (voir lien en bas de page) et participer à la recherche de nombres premiers géants.

Depuis quelques années, les records se succèdent, il faut dire que l’EFF (Electronic Frontier Foundation), association de défense et de promotion de l’utilisation du réseau Internet, offre de belles récompenses :

100 000$ pour un nombre premier de 10 millions de chiffres (on y est presque),

150 000$ pour 100 millions de chiffres,

250 000$ pour un milliard de chiffres.

 

Quelques liens qui traitent du sujet :

• homeomath explique le fonctionnement de l'algorithme d'Euclide par un petit programme permettant de calculer le PGCD de deux nombres au choix.
• Délices de maths présente le crible d'Eratosthène.
• GIMPS qui coordonne la recherche de nombres premiers "géants".
• NOMBRES - Curiosités, théorie et usages définition, règles et théorie.
• NOE maths donne la liste des nombres premiers inférieurs à 50 000.
• Bibliographie