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:

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

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:

  1. 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.
  2. 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

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:

  1. 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).
  2. 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:

Programme_factorisation_nombres_de_FermatPour 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…
Advertisements
Cet article, publié dans Arithmétique, Nombres, est tagué , , , , , . Ajoutez ce permalien à vos favoris.

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

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

  2. Anonyme dit :

    Tres bien explique!

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s