lundi, septembre 22, 2008

NOUVEAU NOMBRE PREMIER

Le plus grand nombre premier connu vient d'être découvert. Youppi!

Il compte 12.978.189 chiffres.

Et comme on le sait depuis Euclide, ce n'est pas le plus grand puisqu'il n'y a pas de nombre premier plus grand: ils sont en nombre infini.
La démonstration d'Euclide est remarquable et se trouve dans Les éléments, IX, 20. Je vais essayer de la rendre claire.


Quelques notions préalables

Si, partant d’un nombre naturel donné, on cherche les nombres par lesquels il peut être divisé, on trouve ses diviseurs. Cette opération s’appelle mise en facteurs.

Par exemple, 12 a pour diviseurs 2, 3, 4, 6 et 12 (oublions 1). Parmi ces diviseurs, certains peuvent à leur tour être divisés, d’autre non. Ceux qui peuvent être divisés (ici : 4, 6, et 12) sont des nombres qu’on dira composés; ceux qui ne peuvent l’être (ici : 3) sont dits des nombres premiers. Plus précisément, un nombre est dit premier s’il ne peut être divisé que par lui-même (et par 1) : si un nombre n’est pas premier, il sera composé.


Les nombres premiers jusqu’à 200 sont:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199


On note que 2 est le seul nombre pair de la liste. Voyez-vous pourquoi?


En d’autres termes, quand on décompose un nombre en facteurs et que nous trouvons, parmi ses diviseurs, des nombres composés, nous pouvons poursuivre la mise en facteur jusqu’à ce qu’on obtienne, exclusivement, des nombres premiers.

Considérons 1 386. Ce nombre est composé. On pourra écrire :

1 386 = 2 X 693

Mais 693 n’est pas premier. On aura donc :

693 = 3 X 231

231 n’est pas premier. On poursuit donc :

231 = 3 X 77

Puis, pour la même raison :

77 = 7 X 11

11 est un nombre premier et notre décomposition en facteurs premiers pend fin.

On a donc :

1 386 = 2 X 3 X 3X 7 X 11

On le voit : à terme, nous avons abouti à des nombres qui sont tous premiers. Est-ce que ce sera toujours le cas? Dans les Éléments, Euclide a établi que oui. Autrement dit : il a démontré que tout entier naturel est ou bien premier ou bien composé et pouvant alors être exprimé comme le produit (unique) de nombres premiers.
***
Les nombres premiers sont donc les composants de base des nombres naturels, un peu comme les atomes le sont du modne matériel. Mais on constate aussi qu’à mesure qu’on avance dans la suite des nombres naturels, ils deviennent plus rares — ce qu’on peut déjà constater en examinant la liste des nombres premiers jusqu’à 200 donnée précédemment. : il y a plus de nombres premiers entre 1 et 10 qu’entre 30 et 40; et plus entre 1 et 100 qu’entre 101 et 200.

Une question finit alors immanquablement par se poser : si on poursuit notre énumération des nombres premiers arrive-t-on à un moment où on a atteint le dernier? Ou est-ce que les nombres premiers sont au contraire en nombre infini? Laquelle de ces deux hypothèses est la bonne?

On pourrait penser que puisque les nombres naturels sont infinis, les nombres premiers le sont aussi. Mais ce n’est pas nécessairement le cas et pour le constater, il suffit de remarquer que puisque 2 et 3 sont premiers, il suffit de les multiplier entre eux ou par eux-mêmes (en certains cas, ce sera un très, très grand nombre de fois!) pour obtenir n’importe quel nombre naturel. La question reste donc posée : laquelle des deux hypothèses précédentes est vraie?

Euclide a établi que c’est la deuxième hypothèse qui est la bonne.

Voici le texte d’Euclide ; après quoi, je le commenterai:



Les nombres premiers sont plus nombreux que toute multitude de nombres premiers proposée.

Soient les nombres premiers proposés A, B, C. Je dis que les nombres premiers sont plus nombreux que A, B, C.

En effet, que soit pris le plus petit [nombre] mesuré par A, B, C, et que ce soit DE et que l'unité DF soit ajoutée à DE. Alors ou bien EF est premier ou bien non. D'abord qu'il soit premier ; donc sont trouvés les nombres premiers A, B, C, EF plus nombreux que A, B, C.

Mais alors que EF ne soit pas premier ; il est donc mesuré par un certain nombre premier (VII.32). Qu'il soit mesuré par le [nombre] premier G. Je dis que G n'est pas le même que l'un quelconque des A, B, C. En effet, si c'est possible, qu'il le soit. Or A, B, C mesurent DE ; donc G mesurera aussi DE. Mais il mesure aussi EF : il mesurera aussi l'unité DF restante tout en étant un nombre ; ce qui est absurde. G n'est donc pas le même que l'un des A, B, C. Et il est supposé premier. Donc sont trouvés les nombres premiers A, B, C, G, plus nombreux que la multitude proposée des A, B, C. Ce qu'il fallait démontrer.

***

La preuve d’Euclide est une preuve indirecte. Il commence par supposer qu’il y a un nombre fini de nombres premiers, puis il va tirer une contradiction de cette assomption.

Admettons donc avec lui qu’il y a un nombre fini de nombres premiers. On pourra en ce cas en faire la liste, qui se clôt avec P, le dernier nombre premier. Écrivons cela comme suit, les […] désignant tous les autres nombre premiers :

2, 3, 5, 7, 11, 13 … P

Nous allons à présent construire un nouveau nombre en multipliant entre eux tous les nombres premiers de cette liste. Appelons N le résultat auquel on aboutira. On aura donc :

2 X 3 X 5 X 7 X 11 X 13 X … X P = N
Jusqu’ici, on le voit, rien de compliqué. Euclide nous demande ensuite, et c’est un coup de génie, de simplement ajouter 1 à N, autrement dit, de construire un nouveau nombre appelé N + 1.

[Notons au passage toute la puissance, la précision et l’économie de la notation mathématique, qui permet d’écrire ce que je viens d’expliquer avec seulement quatre symboles : N!+1]

Attardons-nous maintenant à ce N + 1. Ce nombre est-il sans reste divisible par 2? À l’évidence, la réponse est non : si on le divise par 2, il restera ce que nous avons ajouté à N. Est-il divisible sans reste par 3, par 5, par 7, par 11 ou par n’importe quel autre nombre premier? À chaque fois la réponse est non et toujours pour la même raison : il restera toujours cette unité que nous avons ajoutée à N. Qu’est-ce que cela signifie pour N + 1? Ce nombre est, par définition, ou premier ou composé. Si N + 1 est un nombre premier, il est plus grand que P; s’il est composé, il est divisible par un nombre premier autre que ceux que nous avons considérés et donc plus grand que P.

Mais, rappelez vous, nous avions supposé que P était le plus grand nombre premier. La contradiction à laquelle elle nous a conduite permet d’assurer que cette hypothèse est fausse. CQFD.


Il est bien difficile de ne pas accorder à Jean Paul Delahaye que cette démonstration constitue «[…] le parangon de la preuve mathématique : quelques mots constituant un argument si fort que toute personne saine d’esprit est contrainte d’en accepter la conclusion; celle-ci donne accès à une vérité qu’aucun calcul, aussi long soit-il, n’aurait jamais dévoilé .»

Je termine sur la conjoncture de Goldbach en me disant que certaines personnes ne la connaissent peut-être pas.

Le nom du mathématicien Christian Goldbach (1690 - 1764) reste en effet attaché à une célèbre conjoncture (c’est-à-dire une proposition vérifiée dans tous les cas examinés, mais pas encore prouvée) de la théorie des nombres et qui concerne justement les nombres premiers. La voici : «Tout entier pair autre que 2 est la somme de deux nombres premiers».

Considérez par exemple 16, qui est un entier pair. Il est la somme de 11 et 5, qui sont bien des nombres premiers.

Considérez à présent 24. Cet entier pair est la somme de 11 et 13, qui sont encore une fois des nombres premiers.

La conjoncture de Goldbach affirme que cela vaudra également pour, disons: 619 380. Or c’est bien le cas, puisque : 619 380= 173 + 619207.

Il s’agit maintenant de prouver que cela vaut pour tout entier pair.

Depuis trois siècles, cette conjoncture a résisté à tous les efforts faits pour la démontrer.

4 commentaires:

Enforcer a dit…

Puisque je suis étudiant aux cycles supérieurs en informatique, et que je me réclame de l'anarchisme (j'ai d'ailleurs bien apprécié votre livre L'ordre moins le pouvoir), j'ai presque envie de faire un rapprochement entre l'anarchisme et le sujet de ce billet, soit les nombres premiers.

Quel peut bien être le lien?

Les ordinateurs et des réseaux de communication prennent de plus en plus de place dans notre société. Cependant, le fait que nos vies et nos interactions avec nos semblables dépendent de plus en plus de ces infrastructures numérisées et automatisées fait en sorte qu'il est beaucoup plus pratique pour l'État et ces tyrannies privées que sont les entreprises d'affaires de surveiller massivement la population, dans toutes sortes de buts. Dans un tel contexte, je crois qu'il est tout à fait légitime de percevoir ces intrusions dans notre vie privées comme une forme illégitime d'autorité et de domination, et qu'il est légitime de se défendre contre elles.

Or, les mathématiques nous fournissent d'excellents outils de défense contre la surveillance informatisée. Plusieurs techniques de chiffrement de données utilisées aujourd'hui sont basées sur les propriétés des nombres premiers.

Prenons par exemple RSA, inventé par trois chercheurs du MIT à la fin des années 1970. Pour aller à l'essentiel, la technique consiste à choisir deux grands (quelques centaines de chiffres) nombres premiers gardés secrets, et à les multiplier pour former leur produit, qui sera bien sûr un nombre composé. On choisit ensuite deux autres nombres (appelons les e et d) parmi l'ensemble des nombres possédant certaines propriétés face aux deux nombres premiers secrets. Le produit des deux nombres premiers, ainsi que e, sont utilisés pour chiffrer des messages; on conjecture que la connaissance de d est nécéssaire pour déchiffrer ces derniers.

RSA fonctionne parce que bien qu'il est facile de déterminer si un nombre est premier ou non (dans ce contexte, "facile" signifie qu'il est possible pour un ordinateur de déterminer la solution à un problème dans un délai raisonnable et en utilisant une quantité de mémoire raisonnable), il est beaucoup plus difficile, même pour un ordinateur, de procéder à la mise en facteurs d'un nombre composé, surtout si celui-ci est grand (oui, il est possible de déterminer si un nombre est premier sans procéder à sa mise en facteurs; je vous épargne les détails). Si nous pouvions procéder facilement à la mise en facteurs d'un grand nombre composé, il nous serait alors possible de récupérer d à partir du produit des deux nombres premiers secrets, et donc de déchiffrer tous les messages destinés à une personne.

Je vous épargne le reste de RSA, mais si vous ne souffrez toujours pas d'indigestion mathématique :-), vous pourrez en apprendre plus long ici: http://en.wikipedia.org/wiki/RSA.

Pour terminer, notons deux choses:

1. Nous savons que si nous pouvons procéder à la mise en facteurs du produit de deux grands nombres premiers, nous pouvons récupérer d et lire tous les messages destinés à une personne. Cependant, n'avons aucune preuve qu'il est impossible de déchiffrer des messages chiffrés par RSA sans récupérer d, ni aucune preuve qu'il est impossible de récupérer d sans connaitre les deux nombres premiers secrets.

2. Nous ne savons pas s'il sera toujours difficile pour un ordinateur de procéder à la mise en facteurs d'un grand nombre composé; personne n'a trouvé de technique efficace pour y arriver avec un ordinateur classique (les ordinateurs quantiques, c'est un autre dossier), mais personne n'a encore prouvé qu'une technique efficace est impossible.

Pourquoi toutes ces informations?
1. Pour essayer d'établir un rapprochement entre l'anarchisme et les mathématiques
2. Pour faire la promotion éhontée :-) de mes intérêts de recherche en informatique, soit les technologies de protection de la vie privée (honnêtement, je crois qu'on ne discute pas assez de ces enjeux en dehors des milieux techniques, et c'est très dommage.)

Au plaisir!

Normand Baillargeon a dit…

Bonjour, Enforcer,

Merci de ce riche commentaire. Je suis content de voir que nous avons en commun ces intérêts pour l'anarchisme et les maths. Pour ces dernières, je ne suis qu'un amateur, mais j'avoue que j'aurais bien aimé faire des maths à un haut niveau.

Il se trouve, ô hasard, que je suis en train d'étudier ce RSA dont vous parlez. Je vais aller voir le lien que vous donnez, puisque, je l'avoue, ce n,est pas encore très, très clair pour moi. J'ai découvert le sujet dans The Music of the Primes, chapitre 10, un livre de Marcus du Sautoy.(http://www.amazon.com/Music-Primes-Searching-Greatest-Mathematics/dp/0060935588/ref=pd_bbs_sr_2?ie=UTF8&s=books&qid=1222257527&sr=8-2)


J'ai également lu un article de Martin Gardner, paru en 1977 je pense. Il a été le premier à faire connaître RSA au grand public et c'est quelqu'un que je tiens en très haute estime.lLe papier s'intitule: " A new kind of cypher that would take millions of years to break"

Merci de votre précieuse contribution à ce blogue et à ma réflexion.

Cordialement,

Normand B.

Anonyme a dit…

I'm truly enjoying the design and layout of your site. It's a very easy
on the eyes which makes it much more pleasant for
me to come here and visit more often. Did you hire out a developer
to create your theme? Fantastic work!

Feel free to surf to my web page ... how safe is quantrim
my webpage :: quantrim weight loss

Anonyme a dit…

Woah! I'm really enjoying the template/theme of this site. It's simple,
yet effective. A lot of times it's very hard to get that "perfect balance" between usability and appearance. I must say that you've done a very good job
with this. In addition, the blog loads extremely fast for me on Opera.

Superb Blog!

my blog ... where to buy Quantrim