Nombre de Fermat

Fichier:Pierre de Fermat.jpg

Le mathématicien français Pierre de Fermat (1601-1665) étudia les propriétés des nombres portant maintenant son nom.

Un nombre de Fermat est un nombre qui peut s'écrire sous la forme <math>2^{2^n}+1</math>, avec <math>n</math> entier naturel. Le nombre de Fermat de rang <math>n</math>, <math>2^{2^n}+1</math>, est noté <math>F_n</math>.

La suite <math>(F_n)</math>, qui débute par 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617 est répertoriée comme Modèle:OEIS.

Ces nombres doivent leur nom à Pierre de Fermat, qui émit la conjecture que tous ces nombres étaient premiers. 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 de F₃₃ sont premiers ou composés. Ainsi, les seuls nombres de Fermat premiers connus sont au nombre de cinq, à savoir les cinq premiers F₀, F₁, F₂, F₃ et F₄, qui valent respectivement 3, 5, 17, 257 et 65 537.

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

Histoire

En 1640, dans une lettre adressée à Bernard Frénicle de Bessy, Pierre de Fermat énonce son petit théorème et commente : Modèle:Citation Ce théorème lui permet d'étudier les nombres portant maintenant son nom. Dans cette même lettre<ref>Dans une autre lettre à Frénicle il écrit aussi : Modèle:Citation, Lettre XLIII, août ? 1640, dans Modèle:Harvsp.</ref>, il émet la conjecture que ces nombres sont tous premiers mais reconnaît : Modèle:Citation. Cette hypothèse le fascine ; deux mois plus tard, dans une lettre à Marin Mersenne, il écrit : Modèle:Citation Il écrit encore à Blaise Pascal : Modèle:Citation. Dans une lettre à Kenelm Digby, non datée mais envoyée par Digby à John Wallis le Modèle:Date-, Fermat donne encore sa conjecture<ref>Modèle:Citation étrangère (Modèle:Citation)</ref> comme non démontrée<ref>Modèle:Citation étrangère (Modèle:Citation), lettre XCVI dans Modèle:Harvsp.</ref>. Toutefois, dans une lettre de 1659 à Pierre de Carcavi<ref>Lettre CI, point 5, dans Modèle:Harvsp. Fermat énumère des questions qui se traitent par sa méthode de la descente infinie. Il place parmi ces questions sa conjecture (erronée) sur les nombres dits depuis nombres de Fermat et il ne dit plus, comme il l'avait fait dans des lettres antérieures, qu'il n'a pas encore trouvé de démonstration de cette conjecture.</ref>, il s'exprime en des termes qui, selon certains auteurs, impliquent qu'il estime avoir trouvé une démonstration<ref>C'est l'interprétation que donne H.M. Edwards, Fermat's Last Theorem, Springer, 1977, p. 24, prenant position contre les vues contraires de E.T. Bell, The Last Problem, New York, 1961, p. 256.</ref>. Si Fermat a soumis cette conjecture à ses principaux correspondants, elle est par contre absente des Arithmétiques de Diophante réé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.

En 1732, le jeune Leonhard Euler, à qui Christian Goldbach avait signalé cette conjecture trois ans auparavant<ref name=Sandifer>Modèle:Lien web.</ref>, la réfute<ref>Modèle:Article.</ref> : F₅ est divisible par 641. Il ne dévoile la construction de sa preuve<ref>Modèle:Article (présenté en 1747/48).</ref> que quinze ans plus tard. Il y utilise une méthode similaire à celle<ref>Décrite dans Modèle:MacTutor</ref> qui avait permis à Fermat de factoriser les nombres de Mersenne M₂₃ et M₃₇<ref>Fermat, dans sa lettre XL à Mersenne de juin ? 1640 Modèle:Harv, découvre pour M₃₇ le diviseur 6 × 37 + 1, après avoir détaillé sa méthode sur l'exemple connu M₁₁ = 23 × 89. Dans sa lettre XLIII à Frénicle (août ? 1640) déjà citée, il signale de plus, pour M₂₃, le diviseur 47.</ref>.

Il est probable que les seuls nombres premiers de cette forme soient 3, 5, 17, 257 et 65 537, car Boklan et Conway<ref>Modèle:Article.</ref> ont prépublié en Modèle:Date- une 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 par récurrence simple :

<math> \begin{cases} F_0=3 \\ F_n \ = \ (F_{n - 1} -1)^2 + 1, & \text{pour }n \geqslant1 \end{cases}</math>

ou par récurrence double :

<math> \begin{cases} F_0=3,F_1=5 \\ F_{n} = F_{n-1}^2 - 2(F_{n-2}-1)^2 , & \text{pour }n \geqslant2 \end{cases}</math>

ou par récurrence forte :

<math> \begin{cases} F_0=3 \\ F_n \ = \ \prod_{i=0}^{n-1} F_i \ + \ 2 , & \text{pour }n \geqslant1 \end{cases}</math>

ou encore :

<math> \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 \geqslant2 \end{cases}</math>.

On en déduit le théorème de Goldbach<ref>Modèle:Lien web.</ref> affirmant que : Modèle:Énoncé

Soit <math>D(n,b)</math> le nombre de chiffres utilisés pour écrire <math>F_n</math> en base <math>b</math>.

<math>D(n,b) = \left\lfloor \log_{b}\left(2^{2^{\overset n{}}}+1\right)+1\right\rfloor \approx \lfloor 2^{n}\,\log_b2+1 \rfloor,</math>

où les crochets désignent la fonction partie entière et <math>\log_b</math> le logarithme de base <math>b</math>.

La suite <math>(D(n,10))</math>, qui débute par 1, 1, 2, 3, 5, 10, 20, 39, 78, 155 est répertoriée comme Modèle:OEIS.

Tous les nombres de Fermat à partir de <math>F_2=17</math> se terminent par le chiffre 7 en écriture décimale.

Les nombres de Fermat premiers ne sont pas des nombres brésiliens alors que les nombres de Fermat composés sont tous des nombres brésiliens<ref>B. Schott, [1], Les nombres brésiliens, Quadrature, Modèle:N°, 2010, Prop. 3 p.36.</ref>.

Modèle:Démonstration)^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.</math>

• <math>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.</math>

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

<math>F_n - 2 = (F_{n-1} \ - 1)^2 - 1 \ = \ F_{n-1}(F_{n-1} -2).</math>

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

<math>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.</math>

• Deux nombres de Fermat distincts sont premiers entre eux.

Soit n et m deux entiers positifs tels que n est strictement plus grand que m. Montrons que le seul facteur commun à F_n et F_m est 1. Un calcul précédent montre que

<math>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) </math>

donc un diviseur commun à F_n et F_m est aussi un diviseur de 2. Or 2 ne divise pas F_n. Ces trois entiers sont donc premiers entre eux deux à deux.

• <math>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.</math>

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

• F_n se termine par 7 pour n supérieur ou égal à 2 car c'est le produit de F₁ = 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<ref>Modèle:Harvsp appellent Modèle:Citation (avec un t en italique) les nombres premiers de la forme 2^k + 1 avec k entier positif ou nul, qui sont donc 2 et les « vrais » nombres premiers de Fermat.</ref> :

Modèle:Énoncé Modèle:Démonstration/débutIl existe deux entiers a impair et b tels que k = a 2^b. En posant c = 2^(2b), on dispose alors des égalités suivantes :

<math>2^k+1=c^a + 1= (c + 1)\sum_{i=0}^{a-1} (-1)^i c^i,</math>

qui montrent que c + 1 est un diviseur du nombre premier 2^k + 1 et donc lui est égal, si bien que k = 2^b. Modèle:Démonstration/fin Fermat a conjecturé (erronément, comme on l'a vu) que la réciproque était vraie ; il a montré que les cinq nombres

<math>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.}</math>

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 Fermat F_n, pour n entre 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<ref>Pour des résultats plus récents, voir par exemple Modèle:Lien web.</ref>, le plus grand nombre de Fermat dont on savait qu'il est composé était : F_{2 747 497} ; l'un de ses diviseurs est le nombre premier de Proth 57×2^{2 747 499} + 1<ref>Modèle:Lien web.</ref>.

Factorisation des nombres de Fermat composés

Euler démontre le théorème : Modèle:Énoncé (Lucas a même démontré plus tard que tout facteur premier d'un nombre de Fermat F_n est de la forme k.2ⁿ⁺² + 1.)

Ceci lui permet de trouver rapidement : Modèle:Énoncé

• Tout facteur premier p d'un nombre de Fermat F_n est de la forme k.2ⁿ⁺¹ + 1, où k est un entier.
  Modulo p, F_n est congru à 0 donc 2²ⁿ est congru à –1, si bien que l'ordre multiplicatif de 2 dans l'anneau ℤ/pℤ est égal à Modèle:Nobr Or cet ordre multiplicatif est un diviseur de Modèle:Nobr, ce qui termine la démonstration.
• <math>F_5=641\times6~700~417.</math>
  On peut le vérifier par un simple calcul, mais expliquons comment Euler découvrit le diviseur 641. On cherche un entier k tel que le nombre p = 64k + 1 soit à la fois premier et diviseur strict de F₅. Les premières valeurs de k ne conviennent pas, mais dès k = 10, on constate que Modèle:Nobr est premier et que modulo p,
  <math>-~2^4\equiv5^4</math> donc <math>-2^{32}\equiv5^4\times2^{28}=(5\times2^7)^4=640^4\equiv(-1)^4=1</math> et <math>F_5\equiv0</math>.
• Tout facteur premier p de F_n pour n > 1 peut s'écrire sous la forme s.2ⁿ⁺² + 1, où s est un entier.
  D'après la démonstration précédente, p est de la forme k.2ⁿ⁺¹ + 1. Édouard Lucas est allé plus loin :
  Comme n > 1, p est congru à 1 modulo 8. D'après la deuxième loi complémentaire de la loi de réciprocité quadratique, 2 est donc un résidu quadratique modulo p, c'est-à-dire qu'il existe un entier a tel que <math>a^2\equiv2\pmod p</math>.
  Il est également possible de remarquer directement que 2 est un résidu quadratique modulo p, car

<math>\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.</math>
Comme une puissance impaire de 2 est un résidu quadratique modulo p, 2 lui-même en est un aussi.
On a alors <math>a^{2^{n+1}} \equiv\ (a^2)^{2^{n}} \equiv\ 2^{2^n} \equiv\ -1</math>, et <math>a^{2^{n+2}} \equiv\ 2^{2^{n+1}} \equiv\ 1 \pmod p</math>.
Ainsi l'ordre de a modulo p est égal à <math>2^{n+2}</math>, et d'après le petit théorème de Fermat, p − 1 est donc divisible par <math>2^{n+2}</math> ; p peut alors s'écrire sous la forme <math>s2^{n+2} + 1</math>.

Le cas général est un problème difficile du fait de la taille des entiers F_n, même pour des valeurs relativement faibles de n. En 2020, le plus grand nombre de Fermat dont on connaisse la factorisation complète est F₁₁<ref>{{#invoke:Langue|indicationDeLangue}} Richard P. Brent, Factorization of the Tenth and Eleventh Fermat Numbers, février 1996.</ref>, dont le plus grand des cinq diviseurs premiers a 564 chiffres décimaux (la factorisation complète de F_n, pour n inférieur à 10, est, elle aussi, entièrement connue). En ce qui concerne F₁₂, 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<ref>Depuis le Modèle:Date-, on connaît six des diviseurs premiers de F₁₂, mais toujours pas sa décomposition complète. Voir [2].</ref>. Quant à F₂₀, c'est, en 2020, le plus petit nombre de Fermat composé dont on ne connaisse aucun diviseur premier<ref>Avant 2010, le plus petit tel nombre était F₁₄. Le Modèle:Date-, un diviseur à 54 chiffres de F₁₄ a été découvert par Tapio Rajala, Département de Mathématiques et Statistiques, Université de Jyväskylä, Finlande. Voir le site prothsearch et mersenneforum : k.2Modèle:16 + 1, où k est un nombre à 49 chiffres.</ref>.

Série des inverses des nombres de Fermat

La série des inverses des nombres de Fermat est convergente et sa somme <math>\sum_{n=0}^{\infty}\frac1{2^{2^n}+1}\approx 0{,}596</math><ref>Suite Modèle:OEIS2C de l'OEIS.</ref> est irrationnelle<ref>Modèle:Article.</ref> et même transcendante<ref>Modèle:Article.</ref>. Ces résultats viennent de ce que cette somme est trop bien approchée par des rationnels.

Polygone régulier

Modèle:Article détaillé Gauss et Wantzel ont établi un lien entre ces nombres et la construction à la règle et au compas des polygones réguliers : un polygone régulier à n côtés est constructible si et seulement si n est 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, le pentagone ré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 que Modèle:Math soit premier, Modèle:Math doit nécessairement être pair et Modèle:Math doit être une puissance de 2.

On appelle couramment « nombres de Fermat généralisés<ref>Modèle:MathWorld.</ref> » les nombres de la forme <math>a^{2^n}+1</math> (avec Modèle:Math)<ref>{{#invoke:Langue|indicationDeLangue}} Generalized Fermat Prime search.</ref>, mais Hans Riesel a donné aussi ce nom aux nombres de la forme <math>a^{2^n}+b^{2^n}</math><ref>Modèle:Ouvrage.</ref>. Le plus grand nombre premier de la forme <math>a^{2^n}+1</math> connu en 2017 est <math>24518^{2^{18}}+1</math>, un nombre de plus d'un million de chiffres<ref>{{#invoke:Langue|indicationDeLangue}} The prime database.</ref>.

Voir aussi

• Test de Pépin
• Modèle:OuvrageModèle:Commentaire biblio SRL
• {{#invoke:Langue|indicationDeLangue}} Suite Modèle:OEIS2C de l'OEIS