Nombre de Fermat (encyclopédie mathématiques)

Pierre de Fermat étudie les propriétés des nombres portant maintenant son nom.

Un nombre de Fermat est un entier naturel qui peut s'écrire sous la forme 2^2ⁿ + 1, avec n entier. Le n^e nombre de Fermat, 2^2ⁿ + 1, est noté F_n.

Ces nombres doivent leur nom au mathématicien français Pierre de Fermat (1601-1665) 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 nombres de Fermat jusqu'à F₃₂. On ne sait pas si les nombres à partir de F₃₃ sont premiers ou composés. Les seuls nombres de Fermat premiers connus sont donc F₀, F₁, F₂, F₃ et F₄.

Ces nombres disposent de propriétés intéressantes, en général issues de l'arithmétique modulaire ; en particulier, Carl Friedrich Gauss a é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 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.

Sommaire

[modifier] Histoire

En 1640, dans une lettre adressée à Bernard Frénicle de Bessy, Pierre de Fermat énonce, et probablement démontre son petit théorème : « 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 »^[1]. Ce théorème lui permet d'étudier les nombres portant maintenant son nom. Dans cette même lettre^[2], il émet la conjecture que ces nombres sont tous premiers sans parvenir à trouver une preuve « 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 »^[3]. 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 Wallis le 16 juin 1658, Fermat donne encore sa conjecture^[4] comme non démontrée^[5]. Toutefois, dans une lettre de 1659 à Pierre de Carcavi^[6], il s'exprime en des termes qui, selon certains auteurs, impliquent qu'il estime avoir trouvé une démonstration^[7].

Cette conjecture se révèlera fausse, c'est d'ailleurs la seule conjecture erronée de Fermat. Leonhard Euler présente^[8] un diviseur de F₅ en 1732. Il ne dévoile la construction de sa preuve^[9] que quinze ans plus tard. Elle correspond exactement aux travaux de Fermat lui ayant permis de démontrer^[10] en 1640 la non primalité des candidats de paramètres 23 et 37 pour les nombres de Mersenne.^{[réf. insuffisante]}

[modifier] Propriétés

[modifier] Premières propriétés

La suite des nombres de Fermat possède plusieurs relations de récurrence. On peut citer par exemple si n est supérieur ou égal à 2 :

$F_n \ = \ (F_{n - 1} -1)^2 + 1 \quad ou \quad F_{n} = F_{n-1}^2 - 2(F_{n-2}-1)^2\;$

Ou encore, avec des produits de nombres de Fermat :

$F_n \ = \ \prod_{i=0}^{n-1} F_i \ + \ 2 \quad ou \quad F_{n} = F_{n-1} + 2^{2^{n-1}}\prod_{i=0}^{n-2} F_i\;$

On en déduit le théorème de Goldbach^[11] affirmant que :

Deux nombres de Fermat distincts sont premiers entre eux.

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

La valeur de D(n,b) est donnée par la formule suivante :

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

Les crochets désignent la fonction partie entière et log_b le logarithme de base b.

Aucun nombre de Fermat n'est somme de deux nombres premiers à l'exception de F₁ = 2 + 3.
Aucun nombre de Fermat n'est la différence de deux puissances de nombres premiers impairs.
La somme des inverses de tous les nombres de Fermat est irrationnelle^[12].

Démonstrations

$F_n \ = \ (F_{n - 1} -1)^2 + 1 \quad 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 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.

Soit n et m deux entiers positifs tel 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 :

$F_n = qF_m + 2 \quad si \quad q = \Big( \prod_{i=0}^{m-1} F_i \Big)\Big( \prod_{i=m+1}^{n-1} F_i \Big)$

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.

La valeur de D(n,b) est donnée par la formule suivante :

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

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).

[modifier] 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 :

Soit k un entier strictement positif, si le nombre 2^k + 1 est premier alors k est une puissance de 2.

Démonstration

Il existe deux entiers a et b tel que k = a . 2^b où a est un entier impair et b un entier. En posant c=2^{(2^b)}, on dispose alors des égalités suivantes :

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

qui montre que 1 + c est un diviseur du nombre premier 1 + 2^k et donc lui est égal, si bien que k=2^b.

Fermat a conjecturé que la réciproque était vraie, il a montré que :

F 0 = 3

est premier

F 1 = 5

est premier

F 2 = 17

est premier

F 3 = 257

est premier

F 4 = 65537

est premier

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é.

À la date du 22 juin 2011, le plus grand nombre de Fermat dont on sait qu'il est composé est F_{2 543 548}^[13]

[modifier] Factorisation des nombres de Fermat composés

Euler utilise une méthode de Fermat pour démontrer que F₅ n'est pas premier. Il démontre pour cela trois propositions :

Un facteur premier du nombre de Fermat F_n est de la forme k. 2 ^m + 1 où k est un entier impair, et m $> = n + 2$ .

L'entier k de la proposition précédente possède un facteur premier impair.

F₅ est divisible par 641.

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$ . Aujourd'hui, le plus grand nombre de Fermat dont on connaisse la factorisation complète est F₁₁^[14], dont le plus grand des cinq diviseurs premiers a 560 chiffres (la factorisation complète de $F n$ , pour $n$ entre 5 et 10, est, elle aussi, entièrement connue). En ce qui concerne F₁₂, on sait qu'il est composé mais c'est, à la date du 27 mars 2010, le plus petit nombre de Fermat dont on ne connaisse pas la factorisation complète^[15]. Quant à F₂₀, c'est, à la date du 3 février 2010, le plus petit nombre de Fermat composé dont on ne connaisse aucun diviseur premier^[16]

Démonstrations

Un facteur premier p du nombre de Fermat F_n est de la forme k 2ⁿ⁺¹ + 1 où k est un entier.

F_n est congru à zéro modulo p. On en déduit que 2^2ⁿ est congru à -1 modulo p et 2^2ⁿ⁺¹ à 1 modulo p.

Montrons que l'ordre multiplicatif de 2 est 2ⁿ⁺¹ dans l'anneau Z/pZ. Soit m l'ordre multiplicatif de 2, m est un diviseur de 2ⁿ⁺¹, donc il existe un entier θ tel que m = 2^θ. L'entier 2^{2^θ} est congru à un modulo p donc si h est un entier strictement supérieur à θ, 2^{2^h} est aussi congru à un modulo p, si θ est strictement plus petit que n + 1 alors 2^2ⁿ est congru à un modulo p ce qui est faux car nous avons montré qu'il est congru à -1.

De plus, le petit théorème de Fermat montre que 2^p-1 est congru à un modulo p. Ce résultat et le fait que l'ordre multiplicatif de 2 est 2ⁿ⁺¹ dans Z/pZ montre que p - 1 est un multiple de 2ⁿ⁺¹. Ce qui termine la démonstration.

L'entier k de la proposition précédente possède un facteur premier impair.

Si k est une puissance de deux, alors p est un nombre premier de Fermat différent de F_n, or les nombres de Fermat n'ont pas de facteur commun. Cette remarque termine la démonstration.

F₅ est divisible par 641.

Un diviseur premier de F₅ est de la forme 64.k + 1. Les valeurs de k possibles sont 3, 5, 6, 7, 9, 10 ... Les valeurs 5 et 6 ne correspondent pas à des nombres premiers, les valeurs à tester sont donc 193, 449, 557 et 641. Euler limite donc l'étude à quatre cas au lieu de plus d'une centaine. Etudions le cas où k est égal à 10.

$2^{16} \ = \ 65 536 = 641 \times 102 + 154 \equiv 154 \pmod {641}\,$ $2^{32} \equiv 154^2 \equiv 23716 \equiv 641 \times 36 + 640 \equiv -1 \pmod {641} \,$

Ce qui montre que 2³² + 1 est congru à zéro modulo 641 et la proposition est démontrée.

[modifier] Polygone régulier

Article détaillé : Théorème de Gauss-Wantzel.

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₂.

[modifier] Généralisation

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

Pour que $m = a b + 1$ soit premier, a doit être pair ( $a = 2 k$ ) et b une puissance de 2 ( $b = 2 n$ ).

On appelle ces nombres les nombres de Fermat généralisés.

[modifier] Bibliographie

Michal Křížek, Florian Luca et Lawrence Somer, 17 Lectures on Fermat Numbers: From Number Theory to Geometry, Springer, New York, 2001, 257 p. (ISBN 978-0-387-95332-8) (Contient une bibliographie étendue.)

[modifier] Notes et références

[modifier] Notes

↑ Lettre XLIV à Frénicle, 18 octobre 1640, dans Œuvres de Fermat, t. 2, p. 209.
↑ Dans une autre lettre à Frénicle il écrit aussi : « Mais voici ce que j'admire le plus : c'est que je suis quasi persuadé que tous les nombres progressifs augmentés de l'unité, desquels les exposants sont des nombres de la progression double, sont nombres premiers, comme 3, 5, 17, 257, 65537, 4 294 967 297 et le suivant de 20 lettres 18 446 744 073 709 551 617 ; etc. Je n'en ai pas la démonstration exacte, mais j'ai exclu si grande quantité de diviseurs par démonstrations infaillibles, et j'ai de si grandes lumières, qui établissent ma pensée, que j'aurois peine à me dédire. », Lettre XLIII, août ? 1640, dans Œuvres de Fermat, t. 2, p. 206.
↑ Lettre XLV, 25 Décembre 1640, dans Œuvres de Fermat, t. 2, p. 213. Édouard Lucas, dans ses Récréations mathématiques, tome II, p. 234 donne cette citation infidèle (7 n'a pas à être dans la liste) : « Si je puis une fois tenir la raison fondamentale que 3, 5, 7, 17, 257, 65537 sont nombres premiers […]».
↑ « Potestates omnes numeri 2, quarum exponentes sunt termini progressionis geometricæ ejusdem numeri 2, unitate auctae, sunt numeri primi » « Toutes les puissances du nombre 2 dont les exposants sont des termes de la progression géométrique du même nombre 2, donnent, si on les augmente d'une unité, des nombres premiers ».
↑ « propositiones aliquot quarum demonstrationem a nobis ignorari non diffitemur (...) Quaeritur demonstratio illius propositionis, pulchræ sane, sed et verissimæ » (« quelques propositions dont nous ne nierons pas ignorer la démonstration (...) Il reste à trouver une démonstration de cette proposition, certainement belle mais aussi très vraie », lettre XCVI dans Œuvres de Fermat, t. 2, p. 402-405.
↑ Lettre CI, point 5, dans Œuvres de Fermat, t. 2, p. 433-434. 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.
↑ 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.
↑ (la) L. Euler, Observationes de theoremate quodam Fermatiano aliisque ad numeros primos spectantibus, Commentarii academiae scientiarum Petropolitanae (6) 1738 p. 102-103 1732
↑ (la) L. Euler, Theoremata circa divisors numerorum, Novi commentarii academiae scientiarum Petropolitanae (1) 1750 p. 20-48 1747/48
↑ (en) John J. O’Connor et Edmund F. Robertson, « Marin Mersenne », dans MacTutor History of Mathematics archive, université de St Andrews [lire en ligne] .
↑ L. Durman, Histoire des nombres de Fermat sur Distributed search for Fermat number divisors 2003
↑ (en) S. W. Golomb, On the sum of the reciprocals of the Fermat numbers and related irrationalities, Canad. J. Math. 15 (1963), 475-478.
↑ (en) World record prime Fermat divisor, PrimeGrid, 22 juin 2011.
↑ (en) Richard P. Brent, Factorization of the Tenth and Eleventh Fermat Numbers, février 1996.
↑ Depuis le 27 mars 2010, on connaît six des diviseurs premiers de F₁₂, mais toujours pas sa décomposition complète. Voir [1].
↑ Avant le 3 février 2010, le plus petit nombre de Fermat composé dont on ne connaissait aucun diviseur premier était F₁₄. Le 3 février 2010, un facteur premier 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. Tapio Rajala a annoncé sur le mersenneforum que F₁₄ est divisible par 116928085873074369829035993834596371340386703423373313.

[modifier] Référence

Œuvres de Fermat, t. 2, Paris, Gauthier-Villars, 1894 [lire en ligne]

[modifier] Voir aussi

[modifier] Articles connexes

Nombre premier
Nombre premier de Mersenne

[modifier] Liens externes

(en) Generalized Fermat Prime search
(en) How Euler did it par E. Sandifer
(en) Sur la factorisation des nombres de Fermat composés (attention, les nombres de chiffres annoncés pour les grands facteurs de F₈ à F₁₁ sont inexacts).

Nombre de Fermat

Sommaire

[modifier] Histoire

[modifier] Propriétés

[modifier] Premières propriétés

[modifier] Nombre de Fermat et primalité

[modifier] Factorisation des nombres de Fermat composés

[modifier] Polygone régulier

[modifier] Généralisation

[modifier] Bibliographie

[modifier] Notes et références

[modifier] Notes

[modifier] Référence

[modifier] Voir aussi

[modifier] Articles connexes

[modifier] Liens externes

Rechercher

Menu

Espace membre

Changer d'île