Les nombres premiers (Travaux Pratiques Encadrés)

« nombres premiers s'observe sur l'allure de la courbe rr(x).

Bien que cette dernière tende vers l'infini, elle a une direction asymptotique horizontale .

Au début du XIX' siècle, Gauss et Legendre ont formulé séparément la même conjecture : ils supposèrent que le comportement de la fonction rr(x) à l'infini était le même que celui de x(Log(x).

Cette conjecture a en effet été démontrée en 1896 de manière indépendante par Jacques Hadamard et Charles-Jean de la Vallée Poussin, et porte le nom de « théorème de la raréfaction des nombres premiers ».

LA RENAISSANCE DE L'ARITHMÉTIQUE Après avoir été développée initialement dans l'Antiquité, l'arithmétique a connu sa renaissance au xvii' siècle avec notamment les travaux de Fermat, Pascal et Leibniz.

Parallèlement à ces travaux, ces savants sont les principaux découvreurs du calcul différentiel et ont beaucoup fait progresser la connaissance des séries infinies, c'est-à-dire des fondements de ce que les mathématiciens appellent aujourd'hui l'analyse.

Cela n'est pas un hasard : la découverte du calcul différentiel est directement liée au développement de l'arithmétique comme Leibniz en témoigne lui-même dans sa Quadrature arithmétique du cercle, de l'ellipse et de l'hyperbole .

L'arithmétique n'a elle-même pu progresser que par la découverte des principes qui engendrent les nombres, donc par une meilleure connaissance des nombres premiers.

LEs rHtoRÈMES DE FERMAT Deux «théorèmes» de Fermat, particu­lièrement célèbres en arithmétique , ont longtemps été considérés comme des conjectures (bien qu'il ait -....

-.. _..._ _....,. lui-même déclaré les avoir prouvés), car on n'en a pas retrouvé de démonstration après sa mort.

L'un d'entre eux, appelé« petit théorème de Fermat », concerne les nombres premiers.

Pierre de Fermat énonce que si n est un nombre entier et p un nombre premier, alors (n'-n) est divisible par p.

Ce théorème a été démontré par la suite par Leonhard Euler et généralisé par Gauss qui en fit un fondement de ses travaux sur les résidus quadratiques dans ses Recherches arithmétiques.

Un autre théorème de Fermat a joué un rôle clef dans le développement ultérieur de l'arithmétique : il énonce que tout nombre premier de la forme 4n + 1, par exemple 17 = (4 x 4) + 1, peut être considéré comme la somme de deux carrés , c'est-à-dire 17 = 42 + 1'.

Cependant , Fermat a aussi émis une conjecture qui s'avéra fausse par la suite.

Espérant avoir trouvé une progression régulière de nombres premiers, il dit que tous les nombres de Fermat, ceux qui s'écrivent sous la forme 22 " + 1, sont des nombres premiers.

Plus tard, Euler montra que 2 '5 + 1, c'est-à-dire 4 294 967 297 est égal à 6 700 417 x 641, donc qu'il n'est pas premier.

LES N O M B RES PREMIERS DE MERSENNE Marin Mersenne est un contemporain de Fermat qui s'est beaucoup intéressé aux nombres premiers.

Il a notamment cherché à déterminer les nombres premiers de la forme M = 2' - 1, l'exposant pétant un nombre entier .

Les nombres qui s'écrivent sous cette forme sont appelés « nombres de Mersenne».

Attention : tous les nombres de la forme 2' - 1 ne sont pas nécessairement des nombres premiers.

Néanmoins, les nombres premiers de Mersenne présentent certaines propriétés remarquables.

Une propriété énonce que siM est un nombre premier de Mersenne, alors le nombre M(M + 1 )/ 2 est un nombre dit «parfait>>, c'est-à-dire égal à la somme de ses diviseurs propres.

Un exemple de nombre parfait est 6 : 6 = 1 x 2 x 3 = 1 + 2 + 3.

En prenant M = 7, alors M(M+ 1 )/ 2 = 28 = 1 + 2 + 4 + 7 + 14 (somme des diviseurs propres de 28).

Par ailleurs, suivant la formulation M = 2' - 1, si M est un nombre premier, alors p l'est également.

Cependant, la réciproque est fausse : par exemple, si p = 11, alors M = 2 047 = 23 x 89.

Le plus grand nombre premier actuel, découvert en mai 2004 par un réseau d'ordinateurs (projet GIMPS), est un nombre de Mersenne : 224036583 -1, il comprend 7 235 733 chiffres.

lhio!IŒ!i.IIFJUM Au xv111' siècle, Euler enrichit l'arithmétique d'une multitude de théorèmes particuliers.

Travaillant sur les liens entre les séries infinies et l'a rithmétiqu e, il étudia plus particulièrement les séries zêta qui faisaient depuis longtemps l'objet de recherches : Ç(s) = 1 + 1(2' + 1/3' + 1/ 4 ' + 1/5' + ..

.

, s étant un nombre entier.

On savait notamment que cette somme infinie diverge (elle tend vers l'infini) pour s = 1 et converge (elle tend vers une valeur finie) pour s > 1.

Euler découvrit en particulier que Ç(2) = rr'/6, donc une nouvelle expression de la quadrature du cercle .

Il découvrit également que, dans le cas général, Ç(s) peut s'exprimer sous la forme du produit infini suivant : Ç(s) = 1/(1 -1/2 ') .1/(1 -1/3 ').

1/ (1 -1/ 5 ').1/(1 -1/7 ' ).1/(1 -1/11 ') ...

Ou encore : Ç(s) = nl/(1 - 1/ p ' ), p prenant successivement la valeur de tous les nombres premiers (n représente les p premiers) .

On arrive donc à un résultat assez surprenant: dans l'écriture de Ç(s) en somme infinie, tous les nombres entiers sont successivement élevés à l'exposants, tandis que dans l'écriture en produit infini, les nombres premiers jouent un rôle privilégié.

Ce produit infini prit plus tard le nom de « fonction zêta >> et constitua un lien très important entre deux domaines apparemment séparés : l'arithmétique et l'analyse.

Avec les travaux de Gauss au début du XIX' siècle concernant le domaine complexe et ses Recherches arithmétiques, il est clair que l'on ne peut p lus admettre l'idée selon laquelle un nombre sert simplement à compter des objets.

Les nombres complexes décrivent un double mouvement de rotation et d'extension.

De ce point de vue, les nombres entiers ainsi que les nombres dits « réels >> ne doivent être considérés que comme des cas particu liers de tels mouvements.

Ils sont les reflets d'une harmonie plus générale que l'harmonie des nombres entiers : celle du domaine complexe.

Si l'on désigne par z un nombre complexe donné et par i, le nombre dont le carré est égal à -1, alors il existe deux nombres réels uniques a et b, respectivement la partie entière et la partie imaginaire de z, tels que : z =a + bi.

Dans cette perspective , - 1 correspond à une demi-rotation dans le plan complexe et i à un quart de rotation.

Ceci étant posé, Gauss entreprit de développer une arithmétique complexe (les nouveaux nombres entiers considérés ici sont tels que a et b sont des nombres entiers naturels) et de chercher, en particulier, ce que devient la notion de nombre premier (générateur) dans ce contexte.

Compte tenu du théorème de Fermat qui énonce que tous les nombres premiers (au sens des entiers naturels) de la forme 4n + 1 peuvent s'écrire sous la forme d'une somme de deux carrés, il en déduit que ces nombres ne sont plus« premiers >> au sens de l'arithmétique complexe .

En effet, ils sont le produit de deux nombres « entiers complexes » conjugués.

Par exemple : 5 = (2 + i)(2 -i).

Par contre , 7 n'a dmet pas un e telle décomposition et reste un nombre premier dans cette nouvelle arithmétique.

Donc , comme on le voit, la notion de nombre premier n'est pas absolue, mais relative au type d'arithmétique considéré .

Ayant généralisé la fonction zêta au domaine complexe , c'est-à-dire ayant donné un sens rigoureux à l'expression Ç(Z), Z étant un nombre complexe et pas simplement un nombre entier naturel, Bernhard Riemann, en bon élève de Gauss, montre que l'étude de cette fonction permet de connaître la valeur de rr(x) , c'est-à-dire le nombre de nombres premiers inférieurs à x.

Il établit ainsi que, derrière le chaos apparent de la répartition des nombres premiers du point de vue de l'arithmétique des nombres entiers naturels, se trouve une harmonie du point de vue plus général du domaine complexe.

Plus précisément , Riemann montre que pour déterminer rr(x), il suffit de connaître les zéros de la fonction zêta, c'est-à-dire les nombres Spirale d 'Ula m complexes Z, tels que Ç(Z) = O.

Cependant, cette dernière question est encore ouverte à l'heure actuelle, tous les zéros de cette fonction n'ayant pas été déterminés dans le cas général.

Riemann conjecture que tous ont une partie entière égale à 1/2, comme c'est le cas pour ceux que l'on connaît déjà.

Bien qu'elle ait suscité une avalanche de recherches et de résultats partiels , cette proposition, capitale à plus d'un titre, non seulement pour l'arithmétique mais également pour l'analyse, n'a jamais été démontrée ni infirmée.

Elle reste aujourd'hui l'un des défis les plus célèbres pour les mathématiciens.

LA SPIRALE D'ULAM , VERS DE NOUVELLES HARMONIES Il est clair que le chaos ou le désordre que l'on croit souvent percevoir dans différents domaines comme celui des nombres premiers, n'est que le reflet de notre ignorance , mais pas de la réalité.

Pour s'en convaincre un peu plus , considérons la spirale des nombres premier s découverte par le mathématicien Stanislav Ulam en 1963.

Son prin cipe de construction est le suivant.

On place au centre d'une feuille quadrillée le nombre 1.

On place 2 à la gauche de 1 et 3 au-dessus de 2.

On place ensuite 4 à la droite de 3, 5 à la droite de 4, 6 au-dessous de 5, 7 au-dessous de 6, 8 à la gauche de 7, 9 à la gauche de 8, 10 à la gauche de 9, et ainsi de suite .

Une fois qu'un grand n ombre de cases ont ainsi été numéro tées, on marque toutes celles qui correspondent à des nombres premier s.

Si l'on observe la figure ainsi obtenue , on y découvre un grand nombre d'alignements obliques de cases m arquées.

Tout aussi remarquable : cette propriété subsiste même si la spirale démarre d'un autre nombre que 1.

Ainsi, on devine à travers cette simple illustration, la présence d'une profonde harmonie dont l'or igine reste à découvrir.

UNE APPLICATION :LA CRYPTO GRAPHIE La cryptographie consiste en la fabrication de codes secrets ainsi qu'au décodage de messages secrets.

Aujourd'hui, grâce aux performances de plus en plus élevées des ordinateurs, elle intervient dans tous les domaines : dans la sécurité militaire mais aussi civile comme le commerce électronique qui nécessite la sécurité des paieme nts en réseaux.

Depuis la mise en place d'algorithmes nécessitant des nombres premiers en cryptographie, ils représentent un réel enjeu actuel : des sommes considérables sont offertes pour stimuler la recherche de nombres premiers de plus en plus grands.

Parmi les différentes méthodes utilisées en cryptographie, l'une des plus connues est le système RSA dit «à clé publique>>.lnventée en 1978 par trois mathématiciens -Rives!, Shamir et Ad leman -cette méthode est caractérisée par le fait que l'algorithme de chiffrement (c'est-à­ dire l'encodage) et la clé sont connus de tous et cependant, une seule per sonne peut déchiffrer le message.

Voici la méthode utilisée : On choisit p et q deux nombres premiers.

On pose n = pq, et on choisit e tel que e est prem ier avec le produit h = (p -1)(q -1), e porte le nom d'exposant public.

La clé publique est le couple (n,e).

Comme e est premier avec (p- 1)(q- 1), il existe des entiers d et k tels que ed + k(p- 1)(q- 1) = 1.

Le couple (n,d) est la clé secrète.

Pour crypter en RSA , on utilise les nombres e et n, qui sont les clés publiques du destinataire du message crypté, sans connaître p et q (seul le destinataire les connaît).

Pour déchiffrer le message, le destinataire calcule d (étant le seul à connaître p et q) et reconstitue le message initial.

Pour décrypter un message il est donc indispensable de retrouver p et q connaissant n et e.

Or si pour des nombres premiers p et q de quelques dizaines de chiffres il est facile de décomposer n, l'affaire devient très compliquée lorsque p et q sont des nombres premiers de plus d'un million de chiffres.

Le système RSA est très largement utilisé notamment pour chiffrer les e-mails.. »