Nombre de Fermat

LemathématicienfrançaisPierre de Fermat(1601-1665) étudia les propriétés des nombres portant maintenant son nom.

Unnombre de Fermatest unnombrequi peut s'écrire sous la forme$2^{2^{n}}+1$,avec$n$entier naturel.Le nombre de Fermat de rang$n$,$2^{2^{n}}+1$,est noté$F_{n}$.

La suite$(F_{n})$,qui débute par3, 5, 17, 257, 65537, 4294967297, 18446744073709551617est répertoriée comme suiteA000215de l'OEIS.

Ces nombres doivent leur nom àPierre de Fermat,qui émit laconjectureque tous ces nombres étaientpremiers.Cette conjecture se révéla fausse,F₅étant composé, de même que tous les suivants jusqu'àF₃₂.On ne sait pas si les nombres à partir deF₃₃sont premiers ou composés. Ainsi, les seuls nombres de Fermat premiers connus sont au nombre de cinq, à savoir les cinq premiersF₀,F₁,F₂,F₃etF₄,qui valent respectivement 3, 5, 17, 257 et65 537.

Les nombres de Fermat disposent de propriétés intéressantes, en général issues de l'arithmétique modulaire.En particulier, lethéorème de Gauss-Wantzelétablit un lien entre ces nombres et laconstruction à la règle et au compasdespolygonesréguliers: un polygone régulier à$n$côtés peut être construit à la règle et au compas si et seulement si$n$est une puissance de 2, ou le produit d'une puissance de 2 et de nombres de Fermat premiers distincts.

Histoire

En1640,dans une lettre adressée àBernard Frénicle de Bessy,Pierre de Fermat énonceson petit théorèmeet commente:«Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long.»Ce théorème lui permet d'étudier les nombres portant maintenant son nom. Dans cette même lettre,il émet la conjecture que ces nombres sont tous premiers mais reconnaît:«je n'ai pu encore démontrer nécessairement la vérité de cette proposition».Cette hypothèse le fascine; deux mois plus tard, dans une lettre àMarin Mersenne,il écrit:«Si je puis une fois tenir la raison fondamentale que 3, 5, 17, etc. sont nombres premiers, il me semble que je trouverai de très belles choses en cette matière, car j'ai déjà trouvé des choses merveilleuses dont je vous ferai part.»Il écrit encore àBlaise Pascal:«je ne vous demanderais pas de travailler à cette question si j'avais pu la résoudre moi-même».Dans une lettre àKenelm Digby,non datée mais envoyée par Digby àJohn Wallisle16 juin 1658,Fermat donne encore sa conjecturecomme non démontrée.Toutefois, dans une lettre de1659àPierre de Carcavi,il s'exprime en des termes qui, selon certains auteurs, impliquent qu'il estime avoir trouvé une démonstration.Si Fermat a soumis cette conjecture à ses principaux correspondants, elle est par contre absente desArithmétiquesdeDiophanterééditées en 1670, où son fils retranscrivit les quarante-sept autres conjectures qui furent plus tard prouvées. C'est la seule conjecture erronée de Fermat.

En1732,le jeuneLeonhard Euler,à quiChristian Goldbachavait signalé cette conjecture trois ans auparavant,la réfute:F₅est divisible par 641. Il ne dévoile la construction de sa preuveque quinze ans plus tard. Il y utilise une méthode similaire à cellequi avait permis à Fermat defactoriserlesnombres de MersenneM₂₃etM₃₇.

Il est probable que les seuls nombres premiers de cette forme soient 3, 5, 17, 257 et65 537,car Boklan etConwayont prépublié enmai 2016une analyse très fine estimant la probabilité d'un autre nombre premier à moins d'un sur un milliard.

Propriétés

Premières propriétés

La suite des nombres de Fermat peut se définir parrécurrence simple:

${\begin{cases}F_{0}=3\\F_{n}\ =\ (F_{n-1}-1)^{2}+1,&{\text{pour }}n\geqslant 1\end{cases}}$

ou par récurrence double:

${\begin{cases}F_{0}=3,F_{1}=5\\F_{n}=F_{n-1}^{2}-2(F_{n-2}-1)^{2},&{\text{pour }}n\geqslant 2\end{cases}}$

ou par récurrence forte:

${\begin{cases}F_{0}=3\\F_{n}\ =\ \prod _{i=0}^{n-1}F_{i}\ +\ 2,&{\text{pour }}n\geqslant 1\end{cases}}$

ou encore:

${\begin{cases}F_{0}=3,F_{1}=5\\F_{n}=F_{n-1}+2^{2^{n-1}}\prod _{i=0}^{n-2}F_{i},&{\text{pour }}n\geqslant 2\end{cases}}$.

On en déduit lethéorème de Goldbachaffirmant que:

Deux nombres de Fermat distincts sontpremiers entre eux.

Soit$D(n,b)$le nombre de chiffres utilisés pour écrire$F_{n}$enbase$b$.

$D(n,b)=\left\lfloor \log _{b}\left(2^{2^{\overset {n}{}}}+1\right)+1\right\rfloor \approx \lfloor 2^{n}\,\log _{b}2+1\rfloor,$

où les crochets désignent la fonctionpartie entièreet$\log _{b}$lelogarithmede base$b$.

La suite$(D(n,10))$,qui débute par1, 1, 2, 3, 5, 10, 20, 39, 78, 155est répertoriée comme suiteA057755de l'OEIS.

Tous les nombres de Fermat à partir de$F_{2}=17$se terminent par le chiffre 7 enécriture décimale.

Les nombres de Fermat premiers ne sont pas desnombres brésiliensalors que les nombres de Fermat composés sont tous desnombres brésiliens.

Démonstrations

• $F_{n}\ =\ (F_{n-1}-1)^{2}+1\quad {\rm {ou}}\quad F_{n}=F_{n-1}^{2}-2(F_{n-2}-\ 1)^{2}.$

En effet:

$F_{n}\ =\ 2^{2^{n}}+1\ =\ (2^{2^{n-1}})^{2}+1\ =\ (F_{n-1}\ -\ 1)^{2}+1\ =\ F_{n-1}^{2}-2F_{n-1}+2\ =\ F_{n-1}^{2}-2(F_{n-2}\ -\ 1)^{2}.$

• $F_{n}\ =\ \prod _{i=0}^{n-1}F_{i}\ +\ 2\quad {\rm {ou}}\quad F_{n}=F_{n-1}+2^{2^{n-1}}\prod _{i=0}^{n-2}F_{i}.$

Une récurrence et l'égalité suivante permet de calculer le premier produit:

$F_{n}-2=(F_{n-1}\ -1)^{2}-1\ =\ F_{n-1}(F_{n-1}-2).$

La seconde égalité s'en déduit:

$F_{n}=2^{2^{n}}+1\ =\ 2^{2^{n-1}}+1+2^{2^{n-1}}(2^{2^{n-1}}-1)\ =\ F_{n-1}+2^{2^{n-1}}(F_{n-1}-2)=F_{n-1}\ +\ 2^{2^{n-1}}\prod _{i=0}^{n-2}F_{i}.$

• Deux nombres de Fermat distincts sont premiers entre eux.

Soitnetmdeux entiers positifs tels quenest strictement plus grand quem.Montrons que le seul facteur commun àF_netF_mest 1. Un calcul précédent montre que

$F_{n}=qF_{m}+2\quad {\rm {si}}\quad q=\left(\prod _{i=0}^{m-1}F_{i}\right)\left(\prod _{i=m+1}^{n-1}F_{i}\right)$

donc un diviseur commun àF_netF_mest aussi un diviseur de 2. Or 2 ne divise pasF_n.Ces trois entiers sont donc premiers entre eux deux à deux.

• $D(n,b)=\left\lfloor \log _{b}\left(2^{2^{n}}+1\right)+1\right\rfloor \approx \left\lfloor 2^{n}\,\log _{b}2+1\right\rfloor.$

Il suffit de remarquer que le nombre de chiffres nécessaire pour écrire un entieraen basebest égal à la partie entière de log_b(a)+1.

• F_nse termine par 7 pournsupérieur ou égal à 2 car c'est le produit deF₁= 5 par un nombre impair, plus 2.

Nombre de Fermat et primalité

La raison historique de l'étude des nombres de Fermat est la recherche de nombres premiers. Fermat connaissait déjà la proposition suivante:

Soitkun entier strictement positif; si le nombre 2^k+ 1 est premier, alorskest une puissance de 2.

Démonstration

Il existe deux entiersaimpair etbtels quek=a2^b.En posantc= 2^(2b),on dispose alors des égalités suivantes:

$2^{k}+1=c^{a}+1=(c+1)\sum _{i=0}^{a-1}(-1)^{i}c^{i},$

qui montrent quec+ 1 est un diviseur du nombre premier 2^k+ 1 et donc lui est égal, si bien quek= 2^b.

Fermat a conjecturé (erronément, comme on l'a vu) que la réciproque était vraie; il a montré que les cinq nombres

$F_{0}=2^{1}+1=3,\quad F_{1}=2^{2}+1=5,\quad F_{2}=2^{4}+1=17,\quad F_{3}=2^{8}+1=257\quad {\rm {et}}\quad F_{4}=2^{16}+1=65\,537\quad {\text{sont premiers.}}$

Actuellement, on ne connaît que cinq nombres de Fermat premiers, ceux cités ci-dessus.

On ignore encore s'il en existe d'autres, mais on sait que les nombres de FermatF_n,pournentre 5 et 32, sont tous composés;F₃₃est le plus petit nombre de Fermat dont on ne sait pas s'il est premier ou composé.

En 2013,le plus grandnombre de Fermatdont on savait qu'il est composé était:F_{2 747 497};l'un de sesdiviseursest lenombre premier de Proth57×2^{2 747 499}+ 1.

Factorisation des nombres de Fermat composés

Euler démontre le théorème:

Tout facteur premier d'un nombre de FermatF_nest de la formek.2ⁿ⁺¹+ 1, oùkest un entier.

(Lucasa même démontré plus tard que tout facteur premier d'un nombre de FermatF_nest de la formek.2ⁿ⁺²+ 1.)

Ceci lui permet de trouver rapidement:

$F_{5}=2^{32}+1=4\,294\,967\,297=641\times 6\,700\,417$(semi-premier).

$(641=10\times 2^{5+1}+1=5\times 2^{5+2}+1)$

Démonstrations

• Tout facteur premierpd'un nombre de FermatF_nest de la formek.2ⁿ⁺¹+ 1, oùkest un entier.
  Modulop,F_nestcongruà 0 donc 2²ⁿest congru à –1, si bien que l'ordre multiplicatifde 2 dans l'anneau ℤ/pℤest égal à2ⁿ⁺¹.Or cet ordre multiplicatif est un diviseur dep– 1,ce qui termine la démonstration.
• $F_{5}=641\times 6~700~417.$
  On peut le vérifier par un simple calcul, mais expliquons comment Euler découvrit le diviseur 641. On cherche un entierktel que le nombrep= 64k+ 1 soit à la fois premier et diviseur strict deF₅.Les premières valeurs dekne conviennent pas, mais dèsk= 10, on constate quep= 641est premier et que modulop,
  $-~2^{4}\equiv 5^{4}$donc$-2^{32}\equiv 5^{4}\times 2^{28}=(5\times 2^{7})^{4}=640^{4}\equiv (-1)^{4}=1$et$F_{5}\equiv 0$.
• Tout facteur premierpdeF_npourn> 1 peut s'écrire sous la formes.2ⁿ⁺²+ 1, oùsest un entier.
  D'après la démonstration précédente,pest de la formek.2ⁿ⁺¹+ 1. Édouard Lucas est allé plus loin:
  Commen> 1,pest congru à 1 modulo 8. D'après la deuxième loi complémentaire de laloi de réciprocité quadratique,2 est donc unrésidu quadratiquemodulop,c'est-à-dire qu'il existe un entieratel que$a^{2}\equiv 2{\pmod {p}}$.
  Il est également possible de remarquer directement que 2 est un résidu quadratique modulop,car

$\left(2^{2^{n-1}}+1\right)^{2}\equiv 2^{2^{n}}+1+2^{2^{n-1}+1}\equiv F_{n}+2^{2^{n-1}+1}\equiv 2^{2^{n-1}+1}{\pmod {p}}.$
Comme une puissance impaire de 2 est un résidu quadratique modulop,2 lui-même en est un aussi.
On a alors$a^{2^{n+1}}\equiv \ (a^{2})^{2^{n}}\equiv \ 2^{2^{n}}\equiv \ -1$,et$a^{2^{n+2}}\equiv \ 2^{2^{n+1}}\equiv \ 1{\pmod {p}}$.
Ainsi l'ordredeamodulopest égal à$2^{n+2}$,et d'après lepetit théorème de Fermat,p − 1 est donc divisible par$2^{n+2}$;ppeut alors s'écrire sous la forme$s2^{n+2}+1$.

Le cas général est un problème difficile du fait de la taille des entiersF_n,même pour des valeurs relativement faibles den.En 2020, le plus grand nombre de Fermat dont on connaisse la factorisation complète estF₁₁,dont le plus grand des cinq diviseurs premiers a 564 chiffres décimaux (la factorisation complète deF_n,pourninférieur à 10, est, elle aussi, entièrement connue). En ce qui concerneF₁₂,on sait qu'il est composé; mais c'est, en 2020, le plus petit nombre de Fermat dont on ne connaisse pas la factorisation complète.Quant àF₂₀,c'est, en 2020, le plus petit nombre de Fermat composé dont on ne connaisse aucun diviseur premier.

Série des inverses des nombres de Fermat

Lasériedes inverses des nombres de Fermat estconvergenteet sa somme$\sum _{n=0}^{\infty }{\frac {1}{2^{2^{n}}+1}}\approx 0{,}596$estirrationnelleet mêmetranscendante.Ces résultats viennent de ce que cette somme esttrop bien approchée par des rationnels.

Polygone régulier

GaussetWantzelont établi un lien entre ces nombres et laconstruction à la règle et au compasdespolygones réguliers:un polygone régulier àncôtés est constructible si et seulement sinest le produit d'une puissance de 2 (éventuellement égale à 2⁰= 1) et d'un nombre fini (éventuellement nul) de nombres de Fermat premiers distincts.

Par exemple, lepentagonerégulier est constructible à la règle et au compas puisque 5 est un nombre de Fermat premier; de même, un polygone à 340 côtés est constructible à la règle et au compas puisque 340 = 2².F₁.F₂.

Généralisations

Il est possible de généraliser une partie des résultats obtenus pour les nombres de Fermat.

Pour queaⁿ+ 1soit premier,adoit nécessairement êtrepairetndoit être unepuissance de 2.

On appelle couramment « nombres de Fermat généralisés» les nombres de la forme$a^{2^{n}}+1$(aveca≥ 2),maisHans Riesela donné aussi ce nom aux nombres de la forme$a^{2^{n}}+b^{2^{n}}$.Le plus grand nombre premier de la forme$a^{2^{n}}+1$connu en 2017 est$24518^{2^{18}}+1$,un nombre de plus d'un million de chiffres.

Notes et références

(en)Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé«Fermat number»(voir la liste des auteurs).

Voir aussi

• Test de Pépin
• Nombre trapézoïdal(lesnombres triangulairesnon trapézoïdaux font intervenir les nombres de Fermat premiers)
• (en)Michal Křížek(cs),Florian Luca(en)et Lawrence Somer,17 Lectures on Fermat Numbers: From Number Theory to Geometry,New York, Springer,2001,257p.(ISBN978-0-387-95332-8,lire en ligne)— Contient une bibliographie étendue.
• (en)Suite A000215de l'OEIS