Petit théorème de Fermat

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Théorèmes de Fermat.

En mathématiques, le petit théorème de Fermat est un résultat de l'arithmétique modulaire, qui peut aussi se démontrer avec les outils de l'arithmétique élémentaire.

Il s'énonce comme suit : « si p est un nombre premier et si a est un entier non divisible par p, alors a p–1 – 1 est un multiple de p. ». Autrement dit, sous les mêmes conditions sur a et p :

 a^{p-1}-1\equiv 0 \pmod p.

Un énoncé équivalent est : « si p est un nombre premier et si a est un entier quelconque, alors p – a est un multiple de p. »

Il doit son nom à Pierre de Fermat, qui l'énonce la première fois en 1640.

Il dispose de nombreuses applications, à la fois en arithmétique modulaire et en cryptographie.

Pierre de Fermat propose le théorème sans apporter de démonstration.
Leonhard Euler présente en 1736 la première démonstration publiée du théorème.

Histoire[modifier | modifier le code]

La première apparition connue de l'énoncé de ce théorème provient d'une lettre de Fermat à Frénicle de Bessy datée d'octobre 1640[1], qui a été publiée par son fils Samuel en 1679 par dans les Varia Opera[2]. On peut y lire ceci : « Tout nombre premier mesure infailliblement une des puissances – 1 de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné – 1 ; et, après qu'on a trouvé la première puissance qui satisfait à la question, toutes celles dont les exposants sont multiples de l'exposant de la première satisfont tout de même à la question. »[3], soit en termes modernes, pour tout nombre premier p et tout nombre a (premier avec p), il existe un entier t tel que p divise at -1, et, t étant le plus petit entier vérifiant ceci, t divise p - 1 et tous les multiples n de t vérifient que p divise an -1.

On en déduit immédiatement l'énoncé donné en introduction, et réciproquement on déduit facilement de celui-ci l'énoncé plus précis que donne Fermat. Comme habituellement dans sa correspondance Fermat ne donne aucune démonstration de ce résultat, ni même, comme il le fait parfois, d'indications à propos de celle-ci, mais précise : « 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. »[3].

À cette époque, il est d'usage de ne pas publier les preuves des théorèmes. Ainsi Leibniz rédige une démonstration[4] vers 1683 mais ne la publie pas. Euler en présente une en 1736 à l'Académie des sciences de Saint-Pétersbourg, qui procède par récurrence et utilise le développement du binôme. Elle est publiée en 1741[5]. Euler en donne une autre preuve, par l'étude de la répatition des restes modulo le nombre premier considéré[6]. On trouve la seconde preuve d'Euler dans les Disquisitiones arithmeticae[7] que Gauss publie en 1801. Gauss y résume également la première démonstration d'Euler[8], et en donne une version plus rapide utilisant le développement du multinôme[9].

Gauss mentionne en 1801 que « Ce théorème remarquable, tant par son élégance que par sa grande utilité, s'appelle ordinairement théorème de Fermat, du nom de l'inventeur »[8]. On trouve la dénomination petit théorème de Fermat (kleine Fermatsche Satz) dans un ouvrage de Kurt Hensel de 1913[10].

Le jeune James Jeans a avancé (en 1897) que le théorème était déjà connu en Chine 2 500 ans auparavant, dans le cas particulier a = 2, et accompagné d'une réciproque (fausse). Il a été repris par Dickson en 1919 dans sa monumentale histoire de la théorie des nombres[11]. Mais ceci a été réfuté par Joseph Needham[12], qui n'en a trouvé aucune trace et juge que l'erreur a probablement pour origine une erreur de traduction.

Exemples[modifier | modifier le code]

Voici quelques exemples (basés sur le second énoncé) :

  • 53 − 5 = 120 est divisible par 3
  • 72 − 7 = 42 est divisible par 2.
  • 25 − 2 = 30 est divisible par 5.
  • (−3)7 + 3 = − 2 184 est divisible par 7.
  • 297 − 2 = 158 456 325 028 528 675 187 087 900 670 est divisible par 97.

Applications[modifier | modifier le code]

Les applications sont nombreuses, particulièrement en cryptographie. On trouve néanmoins des exemples classiques d'applications du théorème en mathématiques pures.

Applications théoriques[modifier | modifier le code]

Le petit théorème de Fermat est historiquement utilisé pour analyser la décomposition en produit de facteurs premiers de certains entiers. Ainsi Fermat écrit[13] à Mersenne (1588-1648) : « Vous me demandez si le nombre 100 895 598 169 est premier ou non, et une méthode pour découvrir, dans l'espace d'un jour, s'il est premier ou composé. À cette question, je réponds que ce nombre est composé et se fait du produit de ces deux : 898 423 et 112 303, qui sont premiers. » En utilisant une méthode analogue, Euler infirme l'unique conjecture fausse de Fermat, en prouvant que les nombres de Fermat ne sont pas tous premiers.

Ce théorème est aussi utilisé pour démontrer des résultats de théorie algébrique des nombres, comme le théorème de Herbrand-Ribet. Il dépasse le cadre strict de l'arithmétique, avec une utilisation pour l'étude des points fixes de l'endomorphisme de Frobenius par exemple.

Cryptographie asymétrique[modifier | modifier le code]

La cryptographie à clé publique correspond à un code s'attachant à assurer la confidentialité des messages à l'aide de deux clés de chiffrement. L'une, permettant de chiffrer le message, est publique. L'autre ayant pour objectif le déchiffrement est gardée secrète.

Une famille importante de systèmes asymétriques utilise l'algorithme de chiffrement RSA. La clé secrète est la décomposition d'un grand nombre entier, souvent de plusieurs centaines de chiffres. Il contient deux facteurs premiers. L'essentiel des techniques industrielles du début du XXIe siècle se fonde sur le petit théorème de Fermat pour générer des grands nombres premiers ou pour tester la primalité d'un nombre.

Test de primalité[modifier | modifier le code]

Le petit théorème de Fermat donne une condition nécessaire pour qu'un nombre p soit premier. Il faut en effet que, pour tout a plus petit que p, a p – 1 soit congru à 1 modulo p. Ce principe est la base du test de primalité de Fermat. Il existe de nombreuses variantes algorithmiques de ce test. Les plus connues sont le test de primalité de Solovay-Strassen et surtout le test de primalité de Miller-Rabin.

Nombre pseudo-premier[modifier | modifier le code]

Les tests précédents utilisent une condition nécessaire mais non suffisante. Ainsi, il existe des entiers p non premiers tels que pour tout a premier avec p, a p – 1 soit toujours congru à 1 modulo p. Le nombre 1 729 est un exemple. De tels entiers p sont appelés nombres de Carmichael.

Les tests indiqués au paragraphe précédent sont tous statistiques, au sens où il existe toujours une probabilité, parfois très faible, pour que le nombre ayant passé le test ne soit néanmoins pas premier. Ces nombres sont appelés pseudopremiers et sont attachés à des tests particuliers.

Démonstrations[modifier | modifier le code]

Carl Friedrich Gauss reprend plusieurs démonstrations de ce « théorème remarquable, tant par son élégance que par sa grande utilité »[8] dans ses Disquisitiones Arithmeticae de 1801.

Par le théorème de Lagrange[modifier | modifier le code]

La seconde preuve d'Euler du premier énoncé, telle que reprise par Gauss[7], reformulée en termes modernes, consiste à démontrer que l'ordre t de a dans le groupe multiplicatif (ℤ/pℤ)* est un diviseur de l'ordre p – 1 de ce groupe (il démontre donc le théorème de Lagrange dans le cas particulier du sous-groupe engendré par a). Il en déduit immédiatement le petit théorème de Fermat, en élevant les deux membres de l'équation at ≡ 1 (mod p) à la puissance : l'entier (p – 1)/t. Le résultat et sa démonstration valent pour n'importe quel groupe fini (ici le groupe multiplicatif (ℤ/pℤ)* d'ordre p - 1).

Démonstration d'Euler et de Leibniz[modifier | modifier le code]

La démonstration d'Euler et de Leibniz du second énoncé utilise la formule du binôme de Newton et un raisonnement par récurrence sur la valeur a. Leur raisonnement (reformulé ici dans le langage des congruences introduit ultérieurement par Gauss), est le suivant :

  • La proposition ap ≡ a (mod p) est vraie pour a = 1.
  • Tout entier k vérifie : (k + 1)pkp + 1 (mod p).
Il suffit, pour cela, de développer l'expression (k + 1)p et de remarquer que tous les coefficients binomiaux à l'exception du premier et du dernier sont des multiples de p car p est premier. La démonstration est donnée dans le paragraphe Diviseurs et coefficients binomiaux de l'article Coefficient binomial.
  • Enfin, si la proposition est vraie pour a = k alors elle l'est aussi pour a = k + 1. En effet, grâce au point précédent, il est prouvé que (k + 1)pkp + 1 (mod p). Si de plus kpk (mod p), alors (k + 1)pk + 1 (mod p).

Équivalence des deux énoncés[modifier | modifier le code]

Si le premier énoncé est vrai alors le second aussi : ap – a est égal au produit a (ap–1 – 1) donc est toujours divisible par p, car si le premier facteur, a, ne l'est pas, alors le second l'est.

Réciproquement, le premier énoncé se déduit du second en utilisant le lemme d'Euclide : si a (ap–1 – 1) est divisible par p et si a ne l'est pas, alors ap–1 – 1 l'est.

Une démonstration arithmétique élémentaire[modifier | modifier le code]

Une autre démonstration du premier énoncé est analogue (en plus simple) à une preuve du lemme de Gauss : l'astuce ici est d'évaluer modulo p, de deux façons, le produit

N=a \cdot 2a \cdot 3a\ldots(p-1)a.

La preuve est très rapide en effectuant les calculs dans l'anneau ℤ/p, mais on peut aussi la détailler en utilisant seulement la division euclidienne, le lemme d'Euclide, et une propriété algébrique de la congruence sur les entiers.

Une démonstration par double dénombrement[modifier | modifier le code]

On peut démontrer le petit théorème de Fermat en comptant de deux manières différentes le nombre de mots de p symboles dans un alphabet à a symboles comportant au moins deux symboles différents.

Généralisations[modifier | modifier le code]

Une légère généralisation du théorème s'énonce de la manière suivante : si p est un nombre premier et si m et n sont des entiers strictement positifs tels que mn (mod p – 1) alors, pour tout entier a :

a^m \equiv a^n \pmod p.

En effet, modulo p, les deux membres sont congrus à 0 si a est divisible par p, et s'il ne l'est pas, alors an – m = (ap – 1)(n – m)/(p – 1) ≡ 1(n – m)/(p – 1) = 1. Sous cette forme, le théorème fonde l'algorithme de chiffrement RSA.

Le petit théorème de Fermat est généralisé par le théorème d'Euler : pour tout entier naturel non nul n et tout entier a premier avec n, on a

a^{\varphi(n)}\equiv1\pmod n.

où φ(n) désigne l'indicatrice d'Euler de n, égale à l'ordre du groupe des unités de l'anneau ℤ/n. Si n est un nombre premier, alors φ(n) = n – 1 et l'on retrouve le petit théorème de Fermat.

Il se généralise de même à tout corps fini.

Notes et références[modifier | modifier le code]

  1. Tannery et Henry 1894, p. 209, Lettre de Fermat à Frénicle du 18 octobre 1640, note 1.
  2. Fermat 1679, p. 163 ; les publications successives des œuvres de Fermat sont étudiées dans l'avertissement préliminaire de Tannery et Henry 1891, voir aussi la table de concordance p 440.
  3. a et b Tannery et Henry 1894, p. 209, Lettre de Fermat à Frénicle du 18 octobre 1640.
  4. M. Bülher et A. Pichel-Pajus, Une démonstration du théorème de Fermat par Leibniz, Mnemosyne n° 19, Bonnes vieilles pages (2), 2007, p. 61-66.
  5. (la) L. Euler, « Theorematum quorundam ad numeros primos spectantium demonstratio », Comment. acad. sc. Petrop., vol. 8,‎ 1741, p. 141-146, disponible sur le site Euler Archives sous le numéro E54, avec traduction en anglais.
  6. Euler, Comm. nov. Petrop. T. VIII, p. 70, cité d'après F. Gauss, Recherches arithmétiques (trad. Poullet-Delisle), p 35, n° 50.
  7. a et b C. F. Gauss, Recherches arithmétiques, 1801, traduit par A.-C.-M. Poullet-Delisle en 1807, éd. Courcier, p. 31-32, n° 45 à 49.
  8. a, b et c Ouvrage cité n° 50.
  9. Ouvrage cité n° 51.
  10. Hensel donne sous ce nom l'énoncé généralisé à un groupe fini commutatif, (de) Kurt Hensel, Zahlentheorie, Göschen, Berlin/Leipzig, 1913 numérisé sur le projet Gutenberg, § V.6, p 128 de la version du projet Gutenberg.
  11. (en) Leonard Eugene Dickson, History of the theory of numbers. Vol. I: Divisibility and primality.,‎ 1919 (lire en ligne), p 59, cité d'après Needham 1959, voir note suivante.
  12. (en) Joseph Needham (éd.), Mathematics and the Sciences of the Heavens and the Earth, Science and Civilisation in China, vol. 3, Cambridge University Press, 1959, chap. 19, p 54, note d.
  13. P. de Fermat, Lettre à Marin Mersenne du 7 avril 1643 lire.

Bibliographie[modifier | modifier le code]

Mathématiques[modifier | modifier le code]

Cryptographie[modifier | modifier le code]

Histoire des mathématiques[modifier | modifier le code]

Œuvres de Fermat[modifier | modifier le code]

  • Pierre de Fermat, Varia Opera mathematica : accesserunt selectae quaedam ejusdem Epistolae, vel ad ipsum a plerisque doctissimis viris gallice, latine vel italice, de rebus ad mathematicas disciplinas, aut physicam pertinentibus scriptae., Toulouse, Apud Joannem Pech,‎ 1679 (lire en ligne), lettre de Monsieur de Fermat au Révérend Père Mersenne de l'Ordre des Minimes, à Paris (XL de l'édition Tannery-Henry) p 177, A Monsieur de ****, du 18 octobre 1640 (XLIV de l'édition Tannery-Henry) p 163.
  • Paul Tannery et Charles Henry, Œuvres de Fermat, tome premier, Paris, Gauthier-Villars et cie,‎ 1891 (lire en ligne), Avertissement p IX-XXXVII.
  • Paul Tannery et Charles Henry, Œuvres de Fermat, tome deuxième, correspondance, Paris, Gauthier-Villars et cie,‎ 1894 (lire en ligne), XL, Fermat à Mersenne, juin ? 1640, p 198, et XLIV, Fermat à Frenicle, jeudi 18 octobre 1640, p 208.

Liens externes[modifier | modifier le code]