Nombres de Fermat (1ère partie): Comment Euler a factorisé F5 ?

Dernièrement, on a beaucoup parlé des nombres de Mersenne avec la découverte d’un nouveau nombre de Mersenne premier: il s’agit de $2^{74 \, 207 \, 281} - 1$ , nombre qui comporte plus de 22 millions de chiffres en base 10. Pendant ce temps-là, le plus grand nombre de Fermat premier connu n’est que 65537. Et alors qu’on connaît 49 nombres de Mersenne premiers, on ne connaît que 5 nombres de Fermat premiers. Pourtant, ils sont tout aussi intéressants !

Que sont les nombres de Fermat ?

Un nombre de Fermat est un nombre qui peut s’écrire sous la forme $2^{2^n}+1$ . Par exemple, voici la liste des cinq premiers nombres de Fermat:

Comme leur nom l’indique, ces nombres ont été introduits par Pierre de Fermat, et la première trace que nous en avons est une lettre envoyée par Pierrot (oui c’est mon pote), datant de 1640.

Vous aurez peut-être remarqué que les cinq nombres de Fermat de la liste ci-dessus (3, 5, 17, 257 et 65537) sont tous des nombres premiers, ce qui a poussé Fermat à émettre la conjecture que tous les nombres de la forme $2^{2^n}+1$ sont premiers. Nous savons aujourd’hui que cette conjecture est fausse, c’est-à-dire qu’il existe des nombres de Fermat qui ne sont pas premiers (et même pire que cela, nous n’avons pas découvert ne serait-ce qu’un seul autre nombre de Fermat premier !).

Le premier à avoir prouvé que cette conjecture est fausse est Euler qui, en 1732, a démontré que le nombre $F_5=2^{2^5}+1=4 \, 294 \, 967 \, 297$ n’est pas premier en donnant une factorisation explicite de ce nombre. Plus précisément, il a prouvé que

$F_5 = 641 \times 6 \, 700 \, 417$

Le plus beau dans cette histoire est que cela ne lui a demandé de faire en tout et pour tout que 5 divisions. Comment a-t-il donc fait ?

Une condition nécessaire sur les diviseurs des nombres de Fermat

Euler ne s’est bien entendu pas bêtement lancé dans une succession de divisions de $F_5$ par 2, 3, 4, 5, … jusqu’à ce qu’il tombe sur un facteur. Non, il a été plus malin que cela car il a utilisé (et démontré) le théorème suivant:

Tout diviseur premier $p$ de $F_n=2^{2^n}+1$ est de la forme

$p=k \times 2^{n+1}+1$

où $k$ est un entier.

Voici une démonstration de cette propriété sans doute plus moderne que celle d’Euler, qui utilise la notion de congruence. Rappelons deux choses au préalable. Si $a$ et $p$ sont deux entiers premiers entre eux alors:

Il existe un plus petit entier $m>0$ tel que $a^m \equiv 1 \mod [p]$ qu’on appelle l’ordre de $a$ modulo $p$ .
Si $m'$ est un autre nombre tel que $a^{m'} \equiv 1 \mod [p]$ alors le nombre $m'$ est divisible par l’ordre de $a$ .

Cela étant dit, nous pouvons à présent prouver la propriété. Soit $p$ un diviseur premier du nombre de Fermat $F_n$ . Comme les nombres de Fermat sont impairs, on ne peut pas avoir $p=2$ et donc $p$ est premier avec 2 (cela nous permettra de parler de l’ordre de 2 modulo $p$ ).

• Commençons par montrer que l’ordre de 2 modulo $p$ est $2^{n+1}$ . Tout d’abord, le fait que $p$ divise $F_n$ se traduit par la congruence:

$F_n \equiv 0 \mod [p]$

d’où $2^{2^n} \equiv -1 \mod[p]$ . En prenant cette relation au carré (comme les règles sur les congruences le permettent), on obtient $\left(2^{2^n}\right)^2 \equiv (-1)^2 \mod [p]$ c’est-à-dire

$2^{2^{n+1}} \equiv 1 \mod [p]$

D’après le rappel n°2, cela signifie que l’ordre de 2 modulo $p$ est un diviseur de $2^{n+1}$ donc un nombre de la forme $2^r$ avec $0 \leqslant r \leqslant n+1$ . Si on avait $r\leqslant n$ , en prenant la relation $2^{2^r} \equiv 1 \mod [p]$ au carré $n-r$ fois (autant de fois qu’il faut pour aller de $r$ à $n$ ), on trouverait $2^{2^n} \equiv 1 \mod [p]$ ce qui n’est pas possible car nous avons dit que $2^{2^n} \equiv -1 \mod[p]$ . Ainsi, $r=n+1$ et donc l’ordre de 2 modulo $p$ est $2^{n+1}$ .

• Il nous reste à montrer que $p$ est de la forme $p=k \times 2^{n+1}+1$ . Comme $p$ est premier, le petit théorème de Fermat nous dit que:

$2^{p-1} \equiv 1 \mod [p]$

et donc le rappel n°2 nous dit que l’ordre de 2 modulo $p$ (dont on sait qu’il vaut $2^{n+1}$ ) divise $p-1$ . Ainsi, il existe un entier $k$ tel que $p-1 = k \times 2^{n+1}$ et on trouve bien que

$\boxed{ p = k \times 2^{n+1}+1 }$

La factorisation de F5

Grâce à la propriété précédente, Euler a d’abord remarqué que les diviseurs premiers de $F_5 = 2^{2^5} +1$ sont de la forme:

$p=k \times 2^{5+1}+1 = 64k+1$

Puis il a essayé de diviser $F_5$ par les différentes valeur de $p$ obtenues pour $k=1, 2, 3...$ . Petite remarque avant de le faire nous-mêmes: si le nombre $p$ obtenu pour une certaine valeur $k$ n’est pas premier, alors il ne peut forcément pas diviser $F_5$ car, si c’était le cas, les diviseurs premiers de $p$ (qui sont strictement plus petits que lui-même) seraient aussi de la forme $k\times 2^{n+1}+1$ et donc nous devrions être déjà tombé sur un diviseur de $F_5$ ! Cela étant dit, allons-y:

• Si $k=1$ alors $p=64 \times 1 + 1=65$ qui n’est pas premier (car divisible par 5), donc ne perdons pas notre temps à diviser $F_5$ par 65.

• Si $k=2$ alors $p=64 \times 2 + 1 = 129$ qui n’est pas premier non plus (car divisible par 3) donc passons au suivant.

• Si $k=3$ , on trouve $p=193$ qui est bien premier. Mais en effectuant la division de $F_5=4 \, 294 \, 967 \, 297$ par 193, on trouve un reste non nul, signe que $F_5$ n’est pas divisible par 193. Passons donc au suivant.

• Si $k=4$ , on a $p=257$ qui est lui aussi premier. Là encore, en effectuant la division de $F_5$ par 257, on trouve un reste non nul, donc 257 n’est pas un diviseur premier de $F_5$ .

• Si $k=5$ , on a $p=321$ qui n’est pas premier (car divisible par 3).

• Si $k=6$ , on trouve $p=385$ qui n’est pas premier non plus car divisible par 5.

• Si $k=7$ , on trouve $p= 449$ qui est premier mais la division de $F_5$ par 449 donne un reste non nul.

• Si $k=8$ , on a $p=513$ qui n’est pas premier (divisible par 3).

• Si $k=9$ , on a $p=577$ qui est bien premier mais le reste de la division de $F_5$ par 577 est non nul.

• Si $k=10$ , alors $p=641$ et là… YOUPI ! La division de $F_5$ par 641 tombe juste et donne le quotient 6 700 417. Cela démontre que $F_5 = 641 \times 6 \, 700 \, 417$ et donc que $F_5$ n’est pas premier.

Comme on le voit, il a fallu 5 divisions à Euler pour arriver à la factorisation voulue. En fait, on aurait même pu n’en faire que 4 car il était certain d’avance que 257 ne pouvait pas diviser $F_5$ . La raison en est que 257 est le nombre de Fermat $F_3$ et que deux nombres de Fermat sont toujours premiers entre eux ! Pour en savoir plus à ce propos, vous pouvez lire un autre article que j’avais écrit.

Lucas pour faire mieux qu’Euler

Je vous propose à présent de factoriser nous-mêmes d’autres nombres de Fermat. Mais avant cela, nous allons être encore plus astucieux qu’Euler car nous allons donner un raffinement du théorème précédent dû au mathématicien Édouard Lucas (bien moins connu qu’Euler, mais pourtant grand mathématicien lui aussi) qui nous permettra de faire moitié moins de divisions ! Voici l’énoncé de ce théorème:

Si $n \geqslant 2$ , tout diviseur premier $p$ de $F_n=2^{2^n}+1$ est de la forme

$p=k \times 2^{n+2}+1$

où $k$ est un entier.

Vous ne voyez pas de différence ? Regardez un peu l’exposant de 2, qui est $n+2$ au lieu de $n+1$ dans la propriété précédente. Par exemple, pour factoriser $F_5$ , ce théorème dit que les diviseurs premiers sont de la forme $p=k \times 2^{5+2}+1=128k+1$ . Il nous aurait donc seulement fallu tester les valeurs $p=129, 257, 385, 513, 641$ (correspondant respectivement à $k=1,2,3,4,5$ ), ce qui nous aurait valu de faire uniquement 2 divisions car seuls 257, et 641 sont premiers (et même une seule vu que 257 est un nombre de Fermat et qu’il ne peut pas diviser un autre nombre de Fermat).

Voyons maintenant comment démontrer ce théorème de Lucas. Là encore, voici deux rappels (beaucoup moins évidents que les rappels précédents) qui nous allons utiliser:

Si un entier $a$ est un carré modulo $p$ alors $a^{\frac{p-1}{2}} \equiv 1 \mod [p]$ (on appelle cela le critère d’Euler).
Si $p$ est de la forme $p=8m+1$ alors 2 est un carré modulo $p$ .

C’est parti pour la démonstration. On considère un diviseur premier $p$ de $F_n$ . Nous avions démontré qu’il existe alors un entier $k$ tel que $p=k \times 2^{n+1}+1$ . Comme on suppose $n \geqslant 2$ , on a $n+1 \geqslant 3$ ce qui entraîne que $2^{n+1}$ est divisible par $2^3=8$ . Donc, le nombre $p$ est de la forme $p=8m +1$ (avec $m=k\times 2^{n-2}$ ). D’après le second rappel, on en déduit que 2 est un carré modulo $p$ ce qui, d’après le premier rappel, nous donne la relation:

$2^{\frac{p-1}{2}} \equiv 1 \mod [p]$

Ainsi, l’ordre de 2 modulo $p$ (dont nous avions vu qu’il valait $2^{n+1}$ ) doit diviser $\frac{p-1}{2}$ . Il existe donc un entier $k'$ tel que:

$k' \times 2^{n+1} = \frac{p-1}{2}$

ce qui donne bien $p = k' \times 2^{n+2} +1$ . CQFD.

Factorisation de quelques nombres de Fermat

Avec le théorème de Lucas et un ordinateur, on va pouvoir factoriser $F_6$ , $F_9$ , $F_{10}$ , $F_{11}$ et $F_{12}$ . Pour cela j’ai écrit un programme qui renvoie le plus petit nombre qui divise $F_n$ (ce nombre étant forcément premier). Le programme est disponible ici:

Plus petits diviseurs des nombres de Fermat

et le voici en action:

Pour obtenir une factorisation, il suffit de diviser par le facteur premier trouvé. Par exemple, en divisant $F_6$ par 274 177, on trouve:

$F_6 = 274 \, 177 \times 67 \, 280 \, 421 \, 310 \, 721$

Attention: cette factorisation n’est peut-être pas une décomposition en facteurs premiers car il se peut que le deuxième facteur (67 280 421 310 721) ne soit pas premier.

Mais au fait, vous devriez me demander: pourquoi avoir soigneusement évité de factoriser $F_7$ ? Si vous lancez le programme pour ce nombre, vous constaterez que le programme tourne, tourne, tourne… sans s’arrêter ! Il y a deux raisons possibles à cela: soit il est premier, soit ses facteurs premiers sont gigantesques !

En lançant le programme pour $F_8$ , on se retrouve confronté au même problème. En fait, il se trouve que $F_7$ et $F_8$ ne sont pas premiers, mais le montrer en essayant de trouver un facteur premier a l’air de prendre du temps. Nous verrons donc dans la deuxième partie de cet article comment prouver qu’ils ne sont pas premiers, sans même être capables de donner explicitement leurs facteurs !

Sources et notes

Pour de plus amples précisions historiques, vous pouvez consulter avec profit: « How Euler did it? Factoring F5 » (par Ed Sandifer).
Si vraiment vous voulez connaître les factorisations de $F_7$ et $F_8$ , vous pouvez consulter la page Wikipédia à ce sujet (et vous constaterez que leurs plus petits facteurs premiers sont respectivement des nombres à 17 et 16 chiffres !).
Pour finir, voici les démonstrations des rappels énoncés dans cet article. La dernière démonstration (qui est un cas particulier de la loi de réciprocité quadratique) est particulièrement intéressante ! Normal, elle est due à Gauss…

5 commentaires pour Nombres de Fermat (1ère partie): Comment Euler a factorisé F5 ?

Ping : Nombres de Fermat (2ème partie): comment montrer que F7 n’est pas premier ? | Blogdemaths
Anonyme dit :

23 février 2017 à 4 h 12 min

Tres bien explique!

J’aimeAimé par 1 personne

Réponse
- blogdemaths dit :
  
  23 février 2017 à 20 h 28 min
  
  Merci 🙂
  
  J’aimeJ’aime
  
  Réponse
Claude Mariotti dit :

22 août 2021 à 16 h 19 min

Bonjour, je viens de citer votre blog sur ma page Fermat de Wikiversité. Merci ! Je voulais éviter de mettre un lien qui aurait fait »pub », mais comme je suis moi aussi sur WordPress… on le verra malgré tout, je crois… Cordiales salutations. CM

J’aimeJ’aime

Réponse
Ping : Un théorème, une mathématicienne et leur lecteur : l’énigme de Fermat passée au crible – Le Théorème de Fermat et ses lecteurs

Laisser un commentaire Annuler la réponse.

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.