Mersenne, Fermat et le démenti d'Euler

Ce qu'on a le droit d'utiliser. Deux identités du chapitre sur les sommes : pour tout entier $d\ge 1$, $x^d-1=(x-1)\left(x^{d-1}+x^{d-2}+\cdots +x+1\right)$ ; et pour $d$ impair, $x^d+1=(x+1)\left(x^{d-1}-x^{d-2}+\cdots -x+1\right)$, qui s'obtient de la première en remplaçant $x$ par $-x$. La stratégie : une identité qui factorise est un énoncé de divisibilité, et un nombre premier n'a pas de diviseur strict.

a) Les nombres de Mersenne. Supposons $a^n-1$ premier. L'identité $a^n-1=(a-1)\left(a^{n-1}+\cdots +1\right)$ montre que $a-1$ divise $a^n-1$. Or $1\le a-1<a^n-1$ : la première inégalité car $a\ge 2$, la seconde car $a^n-1\ge a^2-1=(a-1)(a+1)>a-1$ puisque $a+1>1$. Un diviseur d'un nombre premier strictement compris entre $1$ et ce nombre n'existe pas, sauf s'il vaut $1$ : donc $a-1=1$, $a=2$.

Montrons que $n$ est premier, par contraposée. Si $n=de$ avec $1<d<n$, alors, avec $x=2^d$, $2^n-1=(2^d{)}^e-1=(2^d-1)\left(2^{d(e-1)}+\cdots +2^d+1\right)$, et $1<2^d-1<2^n-1$ car $1<d<n$ et $k\mapsto 2^k$ est strictement croissante. Le nombre $2^n-1$ aurait un diviseur strict non trivial : il ne serait pas premier. Donc $n$ est premier.

La réciproque est fausse. $11$ est premier, mais $2^{11}-1=2047=23\times 89$. La condition « $n$ premier » est nécessaire, pas suffisante — et l'on ne sait pas aujourd'hui s'il existe une infinité de premiers de Mersenne $2^p-1$.

b) Les nombres de Fermat. Par contraposée encore. Supposons que $n$ ne soit pas une puissance de $2$ : sa décomposition en facteurs premiers contient un premier impair, et l'on peut écrire $n=2^{k}m$ avec $m$ impair, $m\ge 3$. Posons $x=2^{2^k}$ ; avec $d=m$ impair, la seconde identité donne $$2^n+1=x^m+1=(x+1)\left(x^{m-1}-x^{m-2}+\cdots +1\right).$$ Le facteur $x+1=2^{2^k}+1$ vérifie $1<2^{2^k}+1<2^n+1$ (car $2^k<n$ puisque $m\ge 3$) : c'est un diviseur strict non trivial de $2^n+1$, qui n'est donc pas premier. Si $2^n+1$ est premier, $n$ est une puissance de $2$.

Le point délicat. Dans les deux questions, la factorisation ne prouve rien tant qu'on n'a pas vérifié que le facteur trouvé est strictement compris entre $1$ et le nombre : tout entier « se factorise » en $1\times n$. Les deux inégalités ne sont pas décoratives.

c) Le démenti d'Euler. Les nombres $F_0=3$, $F_1=5$, $F_2=17$, $F_3=257$, $F_4=65537$ sont premiers, et Fermat conjectura que tous les $F_k$ le sont. Suivons Euler, modulo $641$.

Première congruence. $641=5\cdot 2^7+1$ signifie exactement $5\cdot 2^7=641-1$, donc $5\cdot 2^7\equiv -1[641]$.

Élévation à la puissance quatrième. Les congruences sont compatibles avec les produits, donc avec les puissances : ${\left(5\cdot 2^7\right)}^4\equiv (-1{)}^4[641]$, soit $$5^4\cdot 2^{28}\equiv 1[641].$$

Seconde congruence. $641=2^4+5^4$ signifie $5^4=641-2^4$, donc $5^4\equiv -2^4[641]$. Remplaçons $5^4$ par $-2^4$ dans la congruence précédente (compatibilité avec le produit) : $$-2^4\cdot 2^{28}\equiv 1[641],\text{c’est-aˋ-dire}-2^{32}\equiv 1[641].$$

Conclusion. $2^{32}+1\equiv 0[641]$ : $641$ divise $F_5=2^{32}+1$. Comme $F_5>641$, $F_5$ n'est pas premier. On n'a jamais eu à écrire $F_5=4294967297$, ni à effectuer la division ; le quotient vaut $6700417$, et l'on peut vérifier que $641\times 6700417=4294967297$. La condition du b) est nécessaire et non suffisante : c'est l'un des grands démentis de l'histoire des mathématiques, et l'on ne connaît aucun nombre de Fermat premier au-delà de $F_4$.

Ce que l'exercice installe. Une identité algébrique est un énoncé de divisibilité : chaque factorisation de $x^d\pm 1$ dit qui divise qui, et le chapitre sur les polynômes systématisera ces factorisations. Et le calcul d'Euler montre la puissance des congruences : on établit une divisibilité sur un nombre de dix chiffres sans jamais l'écrire, en travaillant sur des restes.