Nombres premiers

Les humains ont créé les nombres il y a 30 000 ans environ, puis ont commencé à les étudier et ont créé les mathématiques. Cependant, parmi tout ces nombres, certains appelés "nombres premiers" sont particuliers. C'est ce que nous verrons dans cet article.

I- Les nombres premiers et l'arithmétique

A - Qu'est-ce qu'un nombre premier ?Autrement dit, un nombre premier doit être strictement supérieur à 1, et il s'agit d'un nombre qui ne peut pas être écrit sous la forme d'un produit de deux autres entiers (autres que 1 et le nombre lui-même). Les entiers qui ne sont pas premiers sont appelés nombres composés.

Par exemple, 5 est premier car il n'a pas d'autre diviseurs positifs que \(1\) et \(5\). Cependant \(21\) est composé car \(21 = 3 \times 7\).

La première apparition certaine des nombres premiers dans l'histoire remonte à l'Antiquité, en 1550 avant JC en Egypte où un papyrus avec une liste de nombres premiers a été trouvée. En Grèce, Euclide prouva qu'il existant une infinité de nombres premiers environ 300 ans avant JC, et le crible d'Erastothènes a été inventé à cette période.

B - Le théorème fondamental de l'arithmétique

L'arithmétique est un champ mathématique dans lequel les nombres sont étudiés pour résoudre des problèmes.

Le théorème fondamental de l'arithmétique établit que :Par exemple, \(462\) est égal à \(2 \times 3 \times 7 \times 11\). Ces entiers sont tous premiers, c'est pourquoi on appelle ceci la décomposition en produit de facteurs premiers de \(462\).

A cause de cette définition du théorème, les mathématiciens ont décidé que 1 n'était pas premier. Sinon, on aurait pu écrire \(462 = 2 \times 3 \times 7 \times 11 \times 1 = 2 \times 3 \times 7 \times 11 \times 1 \times 1 \times 1\)… et il y aurait une infinité de décompositions en produit de facteurs premiers possible pour chaque entier, ce qui ne serait pas compatible avec une définition claire du théorème fondamental de l'arithmétique.

C'est à cause de ce théorème que les nombres premiers sont dénommés ainsi, en effet ils apparaissent comme étant les élément élémentaires qui forment tous les autres nombres entiers.

C - Une infinité de nombres premiersAinsi, nous pouvons nous demander combien de nombres premiers il existe. En l'an 300 avant JC, Euclide avait déjà répondu à cette question avec une démonstration publiée dans ses Eléments. Cette démonstration est présentée ici.

Tout d'abord, supposons qu'il existe une liste contenant tous les nombres premiers, par exemple \({2;3;5;7}\).
On multiplie ces nombres puis on ajoute un, dans ce cas on a :
\(2 \times 3 \times 5 \times 7 + 1 = 211\)

Il y a alors deux situations possibles :
- si le résultat est lui-même premier, alors il n'était nécessairement pas dans la liste. C'est le cas de \(211\).
- sinon, le résultat est un nombre composé, mais qui n'est divisible par aucun des nombres premiers de la liste. Ceci est dû au fait que l'on ajoute \(1\), ce qui implique que le reste de la division euclidienne par chacun des nombres de la liste est 1. De plus on pourrait avancer que deux nombres entiers consécutifs sont toujours premiers entre eux. Ainsi dans la décomposition en produit de facteurs premiers du nombre en question, il y a de nouveaux nombres premiers qui n'étaient pas dans la liste.
Par exemple, ceci se produit avec la liste \({2;7}\). En effet, \(2 \times 7+1 = 15 = 3 \times 5\). \(3\) et \(5\) sont premiers mais n'étaient pas dans la liste.

Dans tous les cas, la liste est incomplète. Comme il manque toujours des nombres premiers, on en conclut qu'il existe une infinité de nombres premiers.

II - Trouver des nombres premiers

A travers l'histoire, de nombreux mathématiciens ont cherché des nouveaux premiers. Cependant, cette quête s'est révélée extrêmement complexe quand les nombres deviennent très grands. Dans cette partie, deux méthodes différentes pour chercher des nombres premiers sont présentées. Puis la recherche d'une formule pour générer ces nombres premiers sera abordée.

A - Une approche naïve : tester les diviseursPremièrement, pour vérifier si un entier est premier, la méthode la plus simple est de suivre la définition, selon laquelle un nombre premier est un entier naturel qui a exactement deux diviseurs distincts : \(1\) et lui-même. Il est possible de tester la divisibilité par tous les entiers inférieurs au nombre étudié. Pour être plus efficace, on peut remarquer que les diviseurs sont toujours regroupés par paire.En effet, pour chaque paire un des diviseurs est inférieur à la racine carrée du nombre et l'autre est supérieur. Ainsi, on peut n'essayer que les entiers inférieurs à la racine carrée du nombre que l'on étudie. D'autre part, on peut n'essayer de diviser que par d'autres premiers.

Cependant, cette méthode demeure très lente quand elle est appliquée à de grands entiers, et pour trouver de nouveaux nombres premiers il faut essayer chaque nombre un par un.

B - Le crible d'Eratosthènes

Pour remédier à cela, les mathématiciens ont créé des techniques plus efficaces. L'une des plus simples est le crible d'Eratosthènes, qui a été inventé en Grèce pendant l'Antiquité, environ 200 ans avant JC, par le mathématicien du même nom. L'idée principale est d'utiliser la liste des premiers entiers consécutifs et d'éliminer tous les multiples de \(2\), \(3\), etc... Ainsi les nombres restants sont tous premiers puisqu'ils ne sont multiples d'aucun autre entier que \(1\) et eux-mêmes.

Bien qu'elle ait été inventée il y a près de deux mille ans, cette méthode reste une des plus efficaces connues à ce jour et est utilisée par les ordinateurs, bien qu'elle nécessite d'avoir en mémoire tous les entiers à tester.

C - Records

Un nombre premier de Mersenne est un nombre premier de la forme \(2^n -1\) avec \(n\) un nombre premier. Ils ont été inventés par Marin Mersenne, un mathématicien et religieux français qui vécu de 1588 à 1648. Il remarqua que beaucoup de nombres de cette forme étaient premiers. De plus il existe un test de primalité (qui permet de vérifier si un entier est premier ou non) très efficace pour ces nombres. Comme \(2^n\) croît très vite, il est utilisé pour chercher les plus grands nombres premiers connus.

A ce jour, la plus grand premier connu est \(2^82589933 – 1\) qui contient \(24 862 048\) chiffres lorsqu'il est écrit en base décimale. Il a été découvert grâce à un projet qui utilise beaucoup d'ordinateurs personnels pour rechercher des nombres premiers de Mersenne.

En effet, la recherche de nombres premiers a été accélérée par l'avènement des ordinateurs.

D - Vers une formule pour les nombres premiers ?

Malgré tout, ces calculs demeurent extrêmement longs et pourraient être évités si une formule pour les nombres premiers venait à être découverte.

Le mathématicien Bernhard Riemann a conjecturé la célèbre hypothèse qui porte aujourd'hui son nom. Si elle était prouvée, cela signifierait que les nombres premiers ne sont pas répartis au hasard mais qu'il existe une règle dans leur organisation. L'institut mathématique Clay a même promis un million de dollars à la première personne capable de prouver cette conjecture.

La recherche d'une telle formule a captivé les plus grands mathématiciens : Euler, Ramanujan ou Gauss. Deux méthodes sont présentées ici.

Leonhard Euler est un mathématicien suisse qui a vécu au XVIIIe siècle. Il est connu pour ses nombreuses contributions à divers sujets mathématiques. En 1772, il découvrit le polynôme suivant :
\(n^2+n+41\)
Sa particularité est qu'il produit des nombres premiers pour tout \(n\) entier entre \(0\) et \(39\), et même après beaucoup de résultats sont premiers.

Cette formule est liée à la spirale d'Ulam. Il s'agit d'une représentation où tous les nombres sont organisés suivant une spirale et où les nombres premiers sont colorés. Des lignes semblent alors y apparaître, sans savoir vraiment pourquoi, et le polynôme d'Euler suit une de ces lignes.

La formule de Mill est un autre résultat impressionnant, elle est basée sur cette constante :
\(A = 1,306377883863080690468…\)

Alors, la partie entière de \(A^{3^n}\) est toujours un nombre premier à condition que l'hypothèse de Riemann soit prouvée. Cependant, les puissances croissent très rapidement et la formule ne peut pas être utilisée même en utilisant des ordinateurs, lorsque \(n\) dépasse \(10\).

Bien que ces résultats soient encourageants, pour l'instant personne n'a trouvé la formule qui produirait facilement tous les nombres premiers. Il s'agit donc encore d'un problème ouvert.

III - Un usage des nombres premiers : la cryptographie

Les nombres premiers sont utilisés en mathématiques et particulièrement en arithmétique, mais aussi dans la cryptographie. L'objectif de cette discipline est de cacher des informations pour communiquer secrètement.

Comme nous l'avons vu, trouver des nombres premiers peut s'avérer fastidieux lorsque l'on s'attaque à de très grands entiers, et la même chose se produit lorsque l'on tente de factoriser un grand nombre. Ce concept a été utilisé par Ronald Rivest, Adi Shamir et Leonard Adleman qui on publié en 1978, un système de cryptographie à clef privée appelé RSA (d'après leurs initiales). Ceci signifie que tout le monde peut encoder un message pour le destinataire mais que celui-ci est le seul à pouvoir le déchiffrer.

Pour craquer un code RSA, il faut factoriser un entier dont la taille dépasse \(2^{1024}\). Dans cette situation, avoir une longue liste de nombres premiers peut s'avérer très utile, bien que cela prendrait tout de même des années en utilisant un ordinateur très puissant.


En conclusion les nombres premiers sont un sujet très complexe qui est toujours activement étudié tandis que beaucoup de conjectures et de questions restent sans réponse.

retour vers la liste d'articles