Mystérieux nombres premiers

article-MathOS
 

“Prime numbers are the most basic objects in mathematics. They also are among the most mysterious, for after centuries of study, the structure of the set of prime numbers is still not well understood. Describing the distribution of primes is at the heart of much mathematics…”

[Andrew Granville]

Le principal obstacle à la vulgarisation des idées mathématiques est sans doute l’incroyable empilement de connaissances qui s’impose pour aborder le moindre thème de recherche contemporain.

Un chercheur en biologie cellulaire sera évidemment dans l’impossibilité d’exposer le détail de ses travaux à une personne non-initiée. Mais il pourra sans doute, même de façon imprécise, donner quelques indications sur la nature de ses recherches. Il pourra dire, par exemple : « j’étudie l’impact de l’environnement sur les mécanismes de mutation génétique chez certains mammifères marins » ou encore « je m’intéresse à la possibilité de transférer des gènes d’une espèce végétale vers une autre »…

En mathématiques, l’analogue est en général impossible. En disant à un non-spécialiste quelque chose du style « j’étudie les revêtements universels des variétés kählériennes compactes », on risque (au mieux) de lui faire prendre ses jambes à son cou !

On trouve cependant des exceptions à cette règle. L’arithmétique, notamment, est riche en questions difficiles, voire non résolues à ce jour pour certaines, et dont la formulation est parfaitement accessible au débutant, voire au profane.

Certaines de ces questions concerne les nombres premiers.

1 – Qu’est-ce qu’un nombre premier ?

 
Imaginons une collection d’objets identiques que l’on cherche à disposer en rangées de même longueur, pour obtenir une configuration « rectangulaire », comme dans l’illustration ci-dessous.

Avec 12 objets, on peut former 3 colonnes de 4 objets, ou bien 2 colonnes de 6 ou encore une seule colonne de 12 (bien entendu, on peut aussi réaliser 4 colonnes de 3, ou 6 colonnes de 2 ou encore 12 colonne réduites à un seul objet, mais c’est la même chose !!) :

 
En revanche, si l’on remplace 12 par 13, la seule possibilité consiste en une seule rangée rassemblant les 13 objets. On dit, pour cette raison, que 13 est un nombre premier.

Voici une définition plus « sérieuse » :

Un entier naturel est dit premier, lorsqu’il est supérieur ou égal à 2 et ne possède aucun diviseur, à l’exception de lui-même et de 1. Autre façon de dire la même chose : un entier n\geqslant2 est premier lorsqu’il ne possède aucun diviseur « non trivial » (les diviseurs triviaux de n sont 1 et n).

Les nombres premiers sont donc, parmi les entiers positifs, ceux qui sont « indécomposables », que l’on ne peut pas scinder en produit d’entiers plus petits. Si l’on osait une comparaison entre l’arithmétique et la chimie, on pourrait dire que les nombres premiers sont aux entiers naturels ce que les corps simples (fer, carbone, hydrogène, azote, oxygène, etc …) sont aux espèces chimiques plus générales (eau, méthane, glucose, acide désoxyribonucléique, etc …).

L’entier 1 n’est pas considéré comme premier, bien qu’il ne soit divisible que par 1 et par lui-même ! Ceci peut paraître étonnant, mais le point de vue contraire aurait une fâcheuse conséquence. En effet, le théorème fondamental de l’arithmétique (voir section 3) affirme l’existence et l’unicité de la décomposition en facteurs premiers d’un entier : en acceptant 1 dans l’ensemble des nombres premiers, on perdrait l’unicité de cette décomposition.

2 – Les premiers nombres premiers 🙂

 
Le plus petit nombre premier est 2. C’est évidemment le seul qui soit pair. Ensuite viennent, dans l’ordre croissant : 3, 5, 7, 11, 13, 17, 19, etc …

Voici la liste des nombre premiers inférieurs à 1000. Il en existe 168 :

table des nombres premiers jusqu'à 1000
 
Les cases colorées correspondent à une curiosité : il arrive qu’on trouve quatre nombres premiers un sein d’une même dizaine, c’est-à-dire des entiers de la forme 10k+1, 10k+3, 10k+7 et 10k+9 pour un certain k.

Ceci ne se produit que quatre fois parmi les entiers inférieurs à 1000 :

  • 11, 13, 17, 19
  • 101, 103, 107, 109
  • 191, 193, 197, 199
  • 821, 823, 827, 829

Existe-t-il une infinité de tels quadruplets ?

 

Une célèbre conjecture de Hardy et Littlewood affirme que oui, mais elle reste à ce jour non prouvée. Noter qu’une confirmation établirait l’existence d’une infinité de nombres premiers jumeaux ! Voir à ce sujet l’article “Qu’est-ce qu’une conjecture en mathématiques ?” ainsi que la dernière section du présent texte, consacrée à quelques conjectures célèbres.

3 – Décomposition en produit de facteurs premiers

Tout nombre entier n\geqslant2 possède au moins un diviseur premier.

C’est assez facile à comprendre. En effet, il se peut que n soit lui-même premier, auquel cas un diviseur premier est tout trouvé : n lui-même !

Et sinon, cela signifie que n possède un diviseur non trivial, disons a (avec 1<a<n). On peut appliquer le même argument à l’entier a : soit il est premier, soit il possède un diviseur strictement compris entre 1 et a.

On reproduisant ce schéma, on abouti fatalement à un nombre premier, après un certain nombre d’étapes. En effet, si le processus se poursuivait indéfiniment sans jamais déboucher sur un nombre premier, cela donnerait naissance à une suite interminable de nombres entiers positifs, chacun étant strictement inférieur au précédent, ce qui est impossible (car il n’existe pas de suite strictement décroissante d’entiers positifs) !

On peut aussi, de façon plus rigoureuse, procéder par récurrence forte :

Montrons que l’assertion \mathcal{A}_{n} suivante :

il existe un nombre premier qui divise n

est vraie pour tout entier n\geqslant2.

  • [ Initialisation ] L’assertion \mathcal{A}_{2} est vraie puisque 2 est premier.
  • [ Hérédité ] Supposons \mathcal{A}_{k} vraie pour tous les entiers k tels que 2\leqslant k. Si n est premier, c’est réglé. Et sinon, n admet un diviseur d tel que 2\leqslant d<n. D’après l’hypothèse de récurrence, d admet un diviseur premier, qui est aussi diviseur de n.

Considérons maintenant un entier n\geqslant2. Divisons n par son plus petit facteur premier et notons n_{1} le résultat de cette opération. Clairement, n_{1}<n et nous pouvons envisager deux possibilités :

  • Soit n_{1}=1 et c’est terminé,
  • Soit n_{1}\geqslant2 auquel cas on peut recommencer : on divise n_{1} par son plus petit facteur premier, ce qui donne un entier n_{2}<n_{1} et ainsi de suite …

Lorsque ce processus se termine, n apparaît comme un produit de nombres premiers.

Certains d’entre-eux peuvent être égaux, ce qui nous incite à les regrouper, pour obtenir au final la « décomposition en facteurs premiers » (ou DFP) de n :

    \[ \boxed{n=p_{1}^{\alpha_{1}}\cdots p_{r}^{\alpha_{r}}} \]

Dans cette expression : r\geqslant1, les entiers p_{i} sont premiers, deux à deux distincts et les exposants \alpha_{i} sont des entiers naturels non nuls.

Remarque. On a établi ici l’existence de la DFP. Nous laisserons de côté, dans cet article, la question de l’unicité (à l’ordre près des facteurs). Le lecteur intéressé pourra la trouver par ailleurs.

Le fait que tout entier naturel supérieur ou égal à 2 puisse s’écrire, de manière unique à l’ordre près des facteurs, comme un produit de nombres premiers constitue le Théorème Fondamental de l’Arithmétique.

 

A titre d’exemple, calculons la DFP de n=728.
  • Le plus petit facteur premier (ou PPFP) de 728 est 2 et n_{1}=728/2=364
  • Le PPFP de 364 est encore 2 et n_{2}=364/2=182
  • Le PPFP de 182 est toujours 2 et n_{3}=182/2=91
  • Le PPFP de 91 est 7 et n_{4}=91/7=13
  • Enfin, 13 est premier. 

Donc 728=2\times2\times2\times7\times13, ce qu’on note de manière plus compacte :

    \[ \boxed{728=2^{3}\times7\times13} \]

 

L’exemple ci-dessus se traite sans difficulté. Mais si l’entier n est assez grand, le calcul de son PPFP (et a fortiori de sa DFP) peut demander beaucoup de travail…

Et pour des entiers de grande taille (quelques milliers de chiffres décimaux), ce calcul est carrément hors de portée – du moins dans l’état actuel de nos connaissances et avec les outils de calcul électronique dont nous disposons.

Nous allons à présent décrire un petit algorithme qui permet le calcul du PPFP d’un entier n\geqslant2.

4 – Calcul du plus petit facteur premier

Etant donné un entier n\geqslant2, on va déterminer son plus petit facteur premier, noté PPFP\left(n\right).

Commençons par une observation-clef, qui nous évitera d’envisager des tests superflus.

Si un entier n\geqslant2 ne possède aucun diviseur non trivial parmi les entiers inférieurs ou égaux à \sqrt{n}, alors n est premier.

Preuve :

On raisonne par l’absurde. Si n est composé (c’est-à-dire non premier), alors n possède un diviseur d tel que 1<d<n. Vue l’hypothèse, on sait que d>\sqrt{n}. Mais l’entier d'=\frac{n}{d} est aussi un diviseur de n strictement compris entre 1 et n; on a donc pour les mêmes raisons d'>\sqrt{n}. Il s’ensuit que n=dd'>\left(\sqrt{n}\right)^{2}=n.

C’est absurde !

Avec ce résultat en poche, on peut proposer l’algorithme suivant :

Algorithme standard de calcul du PPFP

Etant donné un entier n\geqslant2, on calcule PPFP\left(n\right) comme suit :

  • Si n est pair, alors PPFP\left(n\right)=2.
  • Sinon, on parcourt dans l’ordre croissant la liste des entiers impairs de 3 à la “racine carrée entière” de n (càd : le plus grand entier naturel dont le carré est inférieur ou égal à n), à la recherche d’un éventuel diviseur de n (noter que cette liste est vide si n=3, 5 ou 7).
    • Si un diviseur d est détecté, on interrompt la recherche et PPFP\left(n\right)=d.
    • Sinon, c’est que PPFP\left(n\right)=n (et, bien sûr, n est premier).

Traitons à la main le cas n=101, pour voir.

Pour commencer, la  racine carrée entière de 101 est 10 puisque 10^{2}\leqslant101 tandis que 11^{2}>101.

Ensuite, on recherche d’éventuels diviseurs de 101 parmi les entiers impairs de 3 à 9 :

  • 101 n’est pas multiple de 3 car la somme de ses chiffres décimaux ne l’est pas,
  • 101 n’est pas multiple de 5 car son chiffre des unités n’est ni 0 ni 5,
  • 101 n’est pas multiple de 7 puisque 101=7\times14+3,
  • Il est inutile de tester la divisibilité par 9 puisque 3 n’est déjà pas diviseur de 101.

→ Ceci prouve que 101 est un nombre premier.

Autre exemple, avec n=323. La racine carrée entière de 323 est 17 (car 17^{2}=289\leqslant323 tandis que 18^{2}=324>323). Aucun diviseur de 323 ne figure parmi les entiers 3,5,7,11,13.

En revanche : 323=17\times19. Ainsi, 323 est un nombre composé, dont le PPFP est 17.

Cet algorithme est connu depuis au moins 9 siècles ! Il apparaît dans le Liber Abaci, l’immense ouvrage achevé en 1202 par Leonardo Pisano (en français : Léonard de Pise, plus connu sous le pseudonyme de Fibonacci).

Liber Abaci

warning-math-os Pour des entiers un peu trop grands, cette méthode est impraticable et il serait illusoire d’espérer trouver le PPFP de cette manière. Imaginons en effet un nombre impair N dont l’écriture décimale comporte une centaine chiffres :

    \[ 10^{99}\leqslant N<10^{100} \]

La racine carrée entière de N est alors peu différente de 10^{50} et notre algorithme va nous conduire à effectuer jusqu’à 5\times10^{49} tests de divisibilité (la moitié de 10^{50}, puisque les entiers pairs ne sont pas testés). Bien sûr, l’algorithme peut très bien se terminer plus tôt, mais si N est premier (ce que nous supposerons dans la suite), il devra se poursuivre jusque là !

En admettant que nous disposions d’un ordinateur capable d’effectuer en moyenne un million de tests par seconde, cela signifie que le temps de calcul sera de l’ordre de :

    \[ 5\times10^{43}\text{ secondes} \]

soit (après division par 60\times60\times24\times365) :

    \[ 1,6\times10^{36}\text{ années} \]

 

Cette durée est très supérieure à l’âge de l’Univers…

5 – L’infinité des nombres premiers

Il n’est pas évident a priori de savoir si la liste des nombres premiers se termine par un nombre premier plus grand que tous les autres ou si, au contraire, cette liste est interminable.

C’est à Euclide que revient le mérite d’avoir su prouver que pour tout nombre premier donné, il en existe un autre qui lui est supérieur; autrement dit, qu’il existe une infinité de nombres premiers. Ce résultat est apparu, il y a environ 23 siècles, dans les éléments d’Euclide, livre IX, proposition 20.

Voici l’argument.

On suppose que a_{1}, a_{2},\cdots, a_{n} sont des nombres premiers tous distincts et l’on note P leur produit. On considère alors l’entier :

    \[ N=1+P \]

On sait (voir section 3) que N possède au moins un diviseur premier q.

Si l’on avait q=a_{j} pour un certain indice j, alors q diviserait évidemment P. Mais comme q divise N, q diviserait aussi N-P, autrement dit q diviserait 1 : c’est absurde !

Le nombre premier q ne figure donc pas dans la liste a_{1},\cdots,a_{n}.

Notons désormais p_{i} le i-ème nombre premier :

    \[ p_{1}=2,\quad p_{2}=3,\quad p_{3}=5\quad\ldots p_{10000}=104\thinspace729\quad\ldots\quad\textrm{etc}\quad\ldots \]

Pour tout n\geqslant1, posons :

    \[ f_{n}=p_{1}p_{2}\cdots p_{n}\qquad\text{et}\qquad N_{n}=1+f_{n} \]

Une question naturelle se pose à la suite de la preuve d’Euclide : Les entiers N_{n} sont-ils premiers ?

Regardons pour les petites valeurs de n (on note q\in\mathbb{P} lorsque q est un nombre premier) :

Pour n=1 :

    \[ \boxed{1+2=3\in\mathbb{P}} \]

Pour n=2 :

    \[ \boxed{1+2\times3=7\in\mathbb{P}} \]

Pour n=3 :

    \[ \boxed{1+2\times3\times5=31\in\mathbb{P}} \]

Pour n=4 :

    \[ \boxed{1+2\times3\times5\times7=211\in\mathbb{P}} \]

Pour n=5 :

    \[ \boxed{1+2\times3\times5\times7\times11=2311\in\mathbb{P}} \]

Mais pour n=6 :

    \[ \boxed{1+2\times3\times5\times7\times11\times13=30031=59\times509\notin\mathbb{P}} \]

La réponse est donc négative. Quant à savoir si N_{n}\in\mathbb{P} pour une infinité d’indices n (ou non), cette question demeure à ce jour sans réponse.

On ne sait pas davantage s’il existe une infinité d’indices n pour lesquels N_{n} est composé !

Terminons en signalant la “conjecture de Fortune”, du nom de l’anthropologue néo-zélandais Reo Franklin Fortune (1903 – 1979).

Notons q_{n} le plus petit nombre premier plus grand que f_{n} et intéressons-nous à l’écart d_{n}=q_{n}-f_{n}. Voici ce qu’on obtient pour les petites valeurs de n :

Conjecture de Fortune

De façon assez surprenante, la valeur de d_{n} semble être soit 1 soit un nombre premier.

Et ça continue … La conjecture a été testée jusqu’à n=1300 environ, sans qu’aucun contre-exemple n’apparaisse… mais comme toujours, cela ne prouve rien ! La suite des nombres d_{n} est référencée par l’OEIS (Online Encyclopedia of Integer Sequences) : voir ici

6 – Un théorème de Dirichlet

 
On peut adapter l’argument d’Euclide (présenté à la section précédente) pour démontrer qu’il existe une infinité de nombres premiers de la forme 4k-1.

Voici comment.

Etant donnés des nombres premiers \pi_{1},\cdots,\pi_{n} distincts avec, pour chaque i : \pi_{i}=4k_{i}-1, considérons l’entier

    \[ N=4\pi_{1}\cdots\pi_{n}-1 \]

Les diviseurs premiers de ce nombre impair ne peuvent pas tous être de la forme 4m+1, sans quoi il en irait de même pour N.

En effet, le produit de deux entiers congrus à 1 modulo 4 est
encore de cette forme puisque :

    \begin{eqnarray*} \left(4m+1\right)\left(4m'+1\right) & = & 16mm'+4m+4m'+1\\ & = & 4M+1 \end{eqnarray*}

à condition de poser :

    \[ M=4mm'+m+m' \]

Ceci montre que N possède un diviseur premier p=4k-1. Or p ne peut pas figurer parmi \pi_{1},\cdots,\pi_{n}, sans quoi p diviserait 4\pi_{1}\cdots\pi_{n} et donc (par différence), diviserait 1.

Il est naturel de chercher à généraliser en se posant la question suivante :

Etant donnés deux entiers a,b premiers entre eux, existe-t-il une infinité de nombres premiers de la forme ak+b ?

La réponse est affirmative, comme l’a montré en 1837 le mathématicien allemand Peter Gustav Leujeune-Dirichlet (1805 – 1859). La preuve de ce résultat, parfois appelé “théorème de la progression arithmétique”, est bien trop élaborée pour être présentée ici. Disons simplement que Dirichlet combine des notions de théorie des groupes (les caractères d’un groupe abélien fini) et d’analyse complexe pour établir la divergence de la série des inverses des nombres premiers congrus à b modulo a.

7 – La rareté des nombres premiers

 

Combien existe-t-il de nombres premiers parmi les entiers inférieurs à 30 ?

Un rapide décompte montre qu’il y en a 10, à savoir : 2, 3, 5, 7, 11, 13, 17, 19, 23 et 29.

Plus généralement, si x>0, on note \pi\left(x\right) le nombre de nombres premiers qui sont inférieurs ou égaux à x :

    \[ \pi\left(x\right)=\sum_{p\leqslant x}1 \]

warning-math-os

Le symbole \pi utilisé ici n’a rien à voir avec le rapport de la circonférence d’un cercle à son diamètre !

On sait (voir section 5) que l’ensemble des nombres premiers est infini, ce qui revient à dire que :

    \[ \lim_{x\rightarrow+\infty}\pi\left(x\right)=+\infty \]

mais au fur et à mesure que l’on progresse dans l’ensemble des entiers naturels, les nombres premiers se font “rares”.

Afin de préciser cette affirmation un peu floue, disons plutôt que la proportion de nombres premiers parmi les entiers inférieurs à x tend vers 0 lorsque x tend vers l’infini. Autrement dit :

    \[ \lim_{x\rightarrow+\infty}\frac{\pi\left(x\right)}{x}=0 \]

On exprime ceci en disant que la densité de l’ensemble des nombres premiers est nulle (ce résultat, non détaillé ici, pourrait faire l’objet d’un prochain article). Ceci revient à dire que la probabilité qu’un nombre pris au hasard dans \left\{ 1,\cdots,n\right\} soit premier tend vers 0 lorsque n tend vers l’infini.

Une nouvelle question, plus précise, se forme aussitôt : à quelle “vitesse” la raréfaction des nombres premiers se produit-elle ?

Autrement dit : quel est le comportement asymptotique de \pi\left(x\right) en l’infini ? Cette question fondamentale s’est posée il y a environ deux siècles et demi. On peut, schématiquement, décomposer le travail accompli par les mathématiciens en trois temps :

  • Carl Friedrich Gauss (allemand, 1777 – 1855) et Adrien-Marie Legendre (français, 1752 – 1833) conjecturèrent vers la fin du XVIIIème siècle que :

        \[ \pi\left(x\right)\sim\frac{x}{\ln\left(x\right)} \]

  • Pafnouti Lvovitch Tchebychev (russe, 1821 – 1894) s’approcha du résultat en montrant en 1851 que, pour x\geqslant30 :

        \[ 0,9\:\frac{x}{\ln\left(x\right)}\leqslant\pi\left(x\right)\leqslant1,2\:\frac{x}{\ln\left(x\right)} \]

    Tchebychev montra également que si \frac{\pi\left(x\right)\ln\left(x\right)}{x} admet en +\infty une limite, alors celle-ci est nécessairement égale à 1, mais ne parvint pas à prouver l’existence de cette limite.

  • Enfin, à la toute fin du XIXème siècle Jacques Hadamard (français, 1865 – 1963) et Charles-Jean de la Vallée Poussin (belge, 1866 – 1962) démontrèrent indépendamment la conjecture formulée deux siècles plus tôt par Gauss et Legendre.

Ce résultat, publié en 1896, est le “théorème des nombres premiers”.

Le graphique ci-dessous montre une partie du graphe de la fonction x\mapsto\frac{\pi\left(x\right)\ln\left(x\right)}{x} : on visualise ainsi le fait que sa limite en +\infty vaut 1.

Illustration du théorème des nombres premiers

8 – Mersenne et Fermat

 

L’immense domaine que constitue l’étude des nombres premiers est jalonné de niches, où le promeneur non spécialiste (mais curieux) peut s’émerveiller de questions simples en apparence, qui cachent en leur sein des abimes de complexité et font intervenir des entiers de taille colossale.

A l’aube du XVIIème siècle, le moine Marin Mersenne (1588 – 1648) porta (comme d’autres avant lui) son regard sur les entiers de la forme M_{p}=2^{p}-1.
Il affirma – à juste titre – que si M_{p} est premier, alors p est aussi premier. La réciproque de cette implication est fausse, et le plus petit contre-exemple apparaît avec p=11 :

    \[ M_{11}=2047=23\times89 \]

Mersenne dressa une liste des exposants p, inférieurs ou égaux à 257, pour lesquels M_{p} est premier. Ceci constitue une performance pour l’époque, même si cette liste comportait cinq erreurs. En effet, deux exposants (67 et 257) y figuraient à tort :

    \[ 2^{67}-1=193\thinspace707\thinspace721\times761\thinspace838\thinspace257\thinspace287 \]

    \[ 2^{257}-1=535\thinspace006\thinspace138\thinspace814\thinspace359\times1\thinspace155\thinspace685\thinspace395\thinspace246\thinspace619\thinspace182\thinspace673\thinspace033\times P \]

avec

    \[ P=374\thinspace550\thinspace598\thinspace501\thinspace810\thinspace936\thinspace581\thinspace776\thinspace630\thinspace096\thinspace313\thinspace181\thinspace393 \]

(on accordera donc notre indulgence à Mersenne pour ces erreurs !) et trois autres exposants (61, 89 et 107) étaient manquants.

Malgré sa ténacité, Mersenne ne découvrit aucune structure, aucun motif régulier, qui lui aurait permis de savoir s’il existe – ou non – une infinité de nombres premiers de la forme M_{p}. Aujourd’hui encore, cette question est ouverte.

On trouvera ici d’autres éléments d’informations sur les nombres de Mersenne.

C’est sensiblement à la même époque que Pierre de Fermat (160? – 1665), conseiller au parlement de Toulouse et génial mathématicien amateur, s’intéressa (entre autres choses !) aux nombres qui portent aujourd’hui son nom. Il montra que si a et n sont des entiers supérieurs ou égaux à 2 et si a^{n}+1 est premier, alors a est pair et n est une puissance de 2. Ceci le conduisit à porter plus spécialement son attention sur les nombres, dits “de Fermat”, F_{n}=2^{2^{n}}+1.

En formulant l’hypothèse que tous les F_{n} sont premiers, Fermat se trompa lourdement. On ne connaît aujourd’hui que cinq nombres premiers parmi les F_{n} (à savoir F_{0}=3, F_{1}=5, F_{2}=17, F_{3}=257 et F_{4}=65\thinspace537).

En dépit de leur talent, Mersenne et Fermat furent évidemment limités, dans leurs investigations, par la taille gigantesque de ces nombres. Ainsi, Fermat ne parvint pas à voir que F_{5}=4\thinspace294\thinspace967\thinspace297
est composé (car multiple de 641, comme l’a découvert Euler en 1732).

Et pour un entier comme F_{11}, dont l’écriture décimale comporte 617 chiffres ou bien F_{16} avec ses quelques 19\thinspace729 chiffres, même le génial Euler ne pouvait pas faire grand chose.

L’avènement des ordinateurs a rendu possibles des calculs dépassant de très loin les rêves les plus fous des deux pionniers. Ce qui suit devrait donner une petite idée du chemin parcouru…

On sait aujourd’hui que F_{n} est composé pour 5\leqslant n\leqslant32 et le statut (premier ou composé) de F_{33} est inconnu. On connaît en tout 298 exposants n pour lesquels F_{n} est composé. Pour autant, on ne connaît pas, en général, la DFP de ces nombres sauf pour sept d’entre eux : les F_{n} pour 5\leqslant n\leqslant11.

Par exemple, on sait que :

    \[ F_{7}=59\thinspace649\thinspace589\thinspace127\thinspace497\thinspace217\times5\thinspace704\thinspace689\thinspace200\thinspace685\thinspace129\thinspace054\thinspace721 \]

mais aucun facteur premier de F_{20} n’est connu.

Dernier résultat paru (Gary Gostin, mars 2018) : F_{63\thinspace480} est divisible par 242\thinspace445\times2^{63\thinspace484}+1.

Pour information :

F_{63\thinspace480} s’écrit avec plus de 7\times10^{19\thinspace108} chiffres décimaux !!!

Mais ce n’est pas le plus grand nombre de Fermat composé connu…
On sait en effet (R. Ottusch, Reynolds, Penné & Fougeron – juillet 2014) que F_{3\thinspace329\thinspace780} est divisible par 193\times2^{3\thinspace329\thinspace782}+1.

Ce sont là des entiers dont la taille donne véritablement le vertige.

Ajoutons, pour finir, que la question de savoir s’il existe (ou non) une infinité de nombres de Fermat premiers est ouverte.

Pour en savoir plus sur les nombres de Fermat et l’état d’avancement des recherches les concernant, on pourra consulter cette page.

 

9 – Nombres premiers et cryptographie

 
Le britannique Godfrey Harold Hardy (1877 – 1947) fut un mathématicien de premier plan, comme en témoignent la qualité et la profondeur de ses contributions à l’analyse et à la théorie des nombres. Sa renommée doit aussi beaucoup à l’étonnante et fructueuse collaboration qui est née de sa rencontre avec le génie mathématique indien Srinivasa Ramanujan.

Courant 1915, lors d’un exposé relatif aux nombres premiers, Hardy fit – avec une certaine dose de cynisme – le commentaire suivant :

The theory of Numbers has always been regarded as one of the most obviously useless branches of Pure Mathematics. The accusation is one against which there is no valid defense; and it is never more just than when directed against the parts of the theory which are more particularly concerned with primes. A science is said to be useful if its development tends to accentuate the existing inequalities in the distribution of wealth, or more directly promotes the destruction of human life. The theory of prime numbers satisfies no such criteria. Those who pursue it will, if they are wise, make no attempt to justify their interest in a subject so trivial and so remote, and will console themselves with the thought that the greatest mathematicians of all ages have found it in it a mysterious attraction impossible to resist.

que l’on peut traduire comme suit :

La théorie des nombres a toujours été perçue comme l’une des branches les moins utiles des Mathématiques Pures. On ne trouvera guère de défense face à cette accusation, et encore moins lorsqu’elle vise les parties de la théorie plus particulièrement liées aux nombres premiers. Une science est qualifiée d’utile si son développement contribue à accentuer les inégalités dans la répartition des richesses ou, lorsqu’il promeut plus directement la destruction de la vie humaine. La théorie des nombres premiers ne vérifie pas de tels critères. Ceux qui l’explorent ne tenteront en aucun cas, si toutefois ils sont sages, de justifier l’intérêt qu’ils portent à un sujet si futile et isolé et se consoleront à l’idée que les plus grands mathématiciens de tous les temps y ont trouvé un attrait mystérieux, auquel il est impossible de se soustraire.

Il est assez frappant de constater qu’environ six décennies plus tard, les faits donnèrent tort – et de manière cinglante – à Hardy. Avec l’apparition du commerce électronique et, plus généralement, dans tous les domaines où informatique et cryptographie se côtoient, les nombres premiers sont devenus tout simplement incontournables.

Largement utilisé à l’échelle planétaire, le système de cryptographie à clef publique RSA (du nom de ses trois inventeurs Rivest, Shamir et Adleman) donne un exemple significatif de cette interaction. Citons (en les traduisant…) les auteurs :

Pour crypter un message, on commence par le représenter au moyen d’un entier M. On calcule ensuite M^{e}\pmod{n} où l’exposant e et l’entier n sont connus publiquement, n étant le produit de deux grands nombres premiers p et q maintenus secrets. Le résultat de ce calcul constitue le cryptogramme S. Ce dernier peut ensuite être décrypté en calculant S^{d}\pmod{n} où l’exposant d est secret et vérifie ed\equiv1\pmod{\left(p-1\right)\left(q-1\right)}.C’est la difficulté de factoriser n (autrement dit de retrouver ses deux facteurs premiers p et q) qui garantit la sécurité de ce système.

Le texte intégral de l’article

“A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”

publié en 1978 dans la revue Communications of the ACM (Vol. 21-2) est disponible sur la page de Ronald L. Rivest.

10 – Quelques problèmes ouverts

Voici, pour finir, quelques célèbres questions non résolues (ou incomplètement résolues). Elles ont au moins un point en commun (outre le fait qu’elle portent toutes sur les nombres premiers) : leur énoncé est totalement élémentaire. La célèbre hypothèse de Riemann ne figure donc pas dans cette courte liste.

Les quatre premières questions constituent ce qu’on appelle les problèmes de Landau. Le mathématicien Edmund Landau les proposa, lors du cinquième congrès international des mathématiciens qui se tint à Cambridge en 1912.

La dixième et dernière question a été sommairement examinée à la section 5 du présent texte.

P-1 Existe-t-il une infinité de couples \left(p,q\right) de nombres premiers vérifiant q-p=2 ?

La conjecture des “nombres premiers jumeaux” consiste à répondre affirmativement à cette question. Le mathématicien chinois Jingrun Chen montra en 1966 l’existence d’une infinité de nombres premiers p pour lesquels p+2 est soit premier soit le produit de deux nombres premiers.

En 2013, un autre mathématicien chinois, Yitang Zhang, prouva qu’il existe une infinité de couples \left(p,q\right) de nombres premiers pour lesquels p<q<p+7\times10^{7}. Cet écart a été réduit, depuis lors, à une valeur moindre, mais un écart de 2 semble, pour le moment, hors d’atteinte. Pour la petite histoire, Y. Zhang était titulaire d’un poste d’assistant avant de publier son travail. Il est désormais professeur à l’université de Santa Barbara, en Californie.

Yitang Zhang
Yitang Zhang, Mathématicien

 

P-2 Tout entier pair supérieur ou égal à 4 est-il la somme de deux nombres premiers ?

En juin 1742, Goldbach proposa à Euler une conjecture selon laquelle tout entier n>2 est la somme de trois nombres premiers (Goldbach considérait que 1 est premier). A la fin du mois, Euler lui répondit qu’il était convaincu que tout entier pair supérieur ou égal à 4 est la somme de deux nombres premiers, mais qu’il n’était pas capable de le prouver. Aujourd’hui encore, cet énoncé resiste. Cependant, une forme \og faible \fg{} de la conjecture, à savoir que tout nombre impair supérieur ou égal à 7 est la somme de trois nombres premiers, a été prouvée en 2013 par le mathématicien péruvien Harald Helfgott.

On pourra écouter en ligne une interview de ce mathématicien, réalisée en 2014 à l’Ecole Normale Supérieure, rue d’Ulm.

P-3 Etant donné un entier n\geqslant1, existe-t-il au moins un nombre premier compris entre n^{2} et \left(n+1\right)^{2} ?

La conjecture de Legendre affirme que c’est vrai quel que soit n. Le “postulat de Bertrand”, selon lequel pour tout entier n\geqslant1, il existe un nombre premier compris entre n et 2n fut démontré à la fin du XIXème siècle par Tchebytchev. On en trouve une très jolie preuve, due à P. Erdös, dans l’excellent livre Proofs from the Book

P-4 Existe-t-il une infinité de nombres premiers de la forme n^{2}+1 ?
P-5 Existe-t-il une infinité de nombre de Mersenne premiers ?
P-6 Existe-t-il une infinité de nombre de Fermat premiers ?
P-7 Existe-t-il une infinité de nombre de Fibonacci premiers ?
P-8 Existe-t-il une infinité de nombres premiers p tels que 2p+1 soit aussi premier ?

Sophie Germain, mathématicienne française (1776 – 1831), démontra que si p et 2p+1 sont premiers, alors l’équation diophantienne x^{p}+y^{p}=z^{p} ne possède aucune solution dans \mathbb{N}^{\star3}.

P-9 Les nombres premiers de Wilson sont des nombres premiers p tels que p^{2} divise 1+\left(p-1\right)!. On en connaît trois : 5, 13 et 563. En existe-t-il d’autres ?
P-10 Si p_{i} désigne le i-ème nombre premier et si q_{n} désigne le plus petit nombre premier supérieur au produit e_{n}=p_{1}\cdots p_{n}, est-il vrai que q_{n}-e_{n} est, pour tout n\geqslant1, égal à 1 ou bien à un nombre premier ?

Ainsi s’achève ce petit survol d’un domaine des mathématiques que je trouve absolument passionnant. Merci de vos commentaires, si vous partagez cette passion avec moi 🙂

Partager cet article
  • 23
  •  
  •  
  •  
  •  

Laisser un commentaire

Fermer le menu