Le roi des nombres premiers
12 978 189...
Non, ce n'est pas le plus long des nombres premiers (surtout que c'est pas un nombre premier), mais le nombre de chiffres nécessaire pour écrire le plus long des nombres premiers, récemment authentifié.
Rappelons-le au cas où : Un nombre premier est un nombre que le ne peut pas écrire comme le produit de deux autres nombres entiers.
Remontons à l'origine...
On date la découverte des nombres premiers aux années 23 000 avant Jésus-Christ, gravés sur un os les 4 nombres premiers 11, 13, 17 et 19.
Quelques années plus tard (vers 300 av J-C), Euclide prouve qu'il y en a une infinité, et depuis, l'humanité n'a pas arrêté de chercher des nombres premiers de plus en plus grands !
Les règles du jeu sont données par l'EFF Cooperative (Une ONG américaine qui défend la liberté d'expression sur internet):
50 000$ pour un nombre premier à au moins 1 000 000 de chiffres
100 000$ pour un nombre premier à au moins 10 000 000 de chiffres
150 000$ pour un nombre premier à au moins 100 000 000 de chiffres
250 000$ pour un nombre premier à au moins 1 000 000 000 de chiffres
Il faut trouver de tels nombres premiers, mais aussi prouver la primalité de tels nombres pour espérer gagner le pactole.
Aujourd'hui, seul GIMPS peut prétendre pouvoir trouver de tels nombres premiers. GIMPS, c'est le Great Internet Mersenne Prime Search, qui utilise internet et de nombreux volontaires pour effectuer tous les calculs nécessaires à la recherche des grands nombres premiers. Si vous voulez faire parti de ces volontaires et, avec de la chance, détenir l'ordinateur qui trouvera un nouveau grand nombre premier, c'est là-bas qu'il faut aller.
Depuis 1996, tous les nouveaux records sont détenus par le projet GIMPS, mais surtout, tous les nombres premiers découverts sont des nombres premiers de Mersenne.
Un nombre Mersenne, c'est un nombre de la forme Mp=2p-1, avec p un nombre premier.
Par exemple, avec p=7 (premier), on a M7=27-1=127 (premier)
Tous ces nombres ne sont pas forcément premiers (Avec p=11, on a M11=2047=23×89, donc non premier), mais ce sont les meilleurs candidats pour devenir les plus grands nombres premiers découverts !
Le test de primalité de Lucas-Lehmer
Pour savoir si un nombre n est premier, l'idée de base est de chercher à le diviser par tous les nombres de 2 à n-1. Si aucune de ces divisions ne tombe juste, c'est que n est premier.
Avec un peu plus de subtilité, on peut améliorer cet algorithme en ne testant que le nombre 2 et les nombres impairs de 3 à √n. On peut encore améliorer un tel programme en ne cherchant à diviser n que par les nombres premiers entre 2 et √n (mais cela suppose tous ces nombres premiers déjà connus). On a quand même découvert d'autre algorithmes permettant de tester la primalité d'un nombre de manière plus ou moins efficace...
Mais pour de très grands nombres, de tels algorithmes se révèlent bien trop long à mettre en place... Pr contre, quand on est face à des nombres de Mersenne, la donne est changée. Un test de primalité (celui de Lucas-Lehmer) est particulièrement adapté aux nombres de Mersenne :
Le test est le suivant :
On considère la suite de nombres sn définie par sn+1=sn²-2 avec s0=4.
Si la division de sp-2 par Mp est entière, alors Mp est un nombre premier !
Par exemple, le nombre M5=31 est-il premier ?
On calcule d'abord s3 :
s0=4
s1 = 4²-2 = 14
s2 = 194
s3 = 37634
Puisque 37634/31 = 1214 (la division est entière), c'est que M5 est un nombre premier !
(Bon, on s'en doutait, mais c'était histoire d'utiliser Lucas Lehmer !)
Dans la pratique, on ne va pas s'amuser à calculer explicitement la suite sn (Les nombres y sont vraiment trop grands), mais c'est tout comme.
Depuis le début de l'humanité, seuls 46 nombres premiers de Mersenne ont été découverts, dont 12 découverts depuis 1996 par le projet Gimps.
Les premiers de ces nombres premiers sont 3 (p=2), 7 (p=3), 31 (p=5) et 127 (p=7), connus depuis l'antiquité.
Au début de l'année 2008, 44 nombres premiers de Mersenne étaient connus (le dernier datant de septembre 2006). Et c'est au cours de l'été 2008 qu'un 45eme fut détecté. Puisque c'était les vacances, il a fallut attendre la rentrée avant de l'authentifier (Tester, avec d'autres ordinateurs, que ce nombre est bien premier). Mais le 6 septembre, un 46eme a été trouvé en Allemagne !
Les deux nouveaux nombres ont été révélés en même temps, après leur authentification (séparément aux USA (13 jours de calculs), en Nouvelle-Zélande (5 jours de calculs) en France et au Canada), le 15 septembre 2008.
Les deux nombres gravés dans l'histoire sont les suivants :
243 112 609-1
(12 978 189 chiffres)
et
237 156 667-1
(11 185 272 chiffres)
Mais à quoi ça sert de si grand nombre ?
Essentiellement, à pas grand chose !... Enfin, pour le plaisir de la certitude de la primalité de trèèès grands nombres ! On peut quand même trouver une utilité mathématique aux premiers de Mersenne : les nombres parfaits :
Un nombre parfait est un nombre égal à la somme de ses diviseurs propres (différents de lui). Par exemple, le nombre 6 possède 3 diviseurs : 1, 2 et 3. On a 1+2+3=6, donc 6 est un nombre parfait.
Au IIIe siècle avant Jésus-Christ, Euclide trouve un lien entre les nombres parfaits pairs et les nombres premiers de Mersenne :
Si Mp=2p-1 est premier, alors n = Mp*(Mp+1)/2 = (2p-1)*2p-1 est un nombre parfait.
Inversement, tous les nombres parfaits pairs peuvent s'écrire de cette façon :
6 = (22 − 1)21 est parfait
28 = (23 − 1)22 est parfait
496 = (25 − 1)24 est parfait
8128 = (27 − 1)26 est parfait
Le plus grand nombre parfait actuellement connu est donc
(243 112 609 − 1)243 112 608
Et qu'en est il des nombres parfaits impairs ? On vous le dira dès qu'un nombre parfait impair sera découvert... Pour l'instant, on est bien incapable de dire s'il en existe ou pas !
Sources :
Le site du projet GIMPS