Petit théorème de Fermat

Modèle:Homon 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 Modèle:Mvar est un nombre premier et si Modèle:Mvar est un entier non divisible par Modèle:Mvar, alors Modèle:Math est un multiple de Modèle:Mvar », autrement dit (sous les mêmes conditions sur Modèle:Mvar et Modèle:Mvar), Modèle:Math est [[Congruence sur les entiers|congru à 1 modulo Modèle:Mvar]] :

$a^{p-1}\equiv 1(\mathrm{mod}p)$.

Un énoncé équivalent est : « si Modèle:Mvar est un nombre premier et si Modèle:Mvar est un entier quelconque, alors Modèle:Mvar est un multiple de Modèle:Mvar » :

$a^p\equiv a(\mathrm{mod}p)$.

Il doit son nom à Pierre de Fermat, qui l'énonce pour la première fois en Modèle:Date-.

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

Pierre de Fermat propose en 1640 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

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'Modèle:Date-, qui a été publiée par son fils Samuel en 1679 dans les Varia Opera. On peut y lire ceci : Modèle:Citation, soit en termes modernes, pour tout nombre premier Modèle:Mvar et tout nombre Modèle:Mvar (premier avec Modèle:Mvar), il existe un entier Modèle:Mvar tel que Modèle:Mvar divise Modèle:Math, et, Modèle:Mvar étant le plus petit entier vérifiant ceci, Modèle:Mvar divise Modèle:Math et tous les multiples Modèle:Mvar de Modèle:Mvar vérifient que Modèle:Mvar divise Modèle:Math.

On en déduit immédiatement l'énoncé donné en introduction, et réciproquement on déduit de celui-ci l'énoncé plus précis que donne Fermat. Comme habituellement dans sa correspondance, il 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 : Modèle:Citation

À cette époque, il est d'usage de ne pas publier les preuves des théorèmes. Ainsi Leibniz rédige une démonstration vers 1683 mais ne la publie pas. En 1741, 1750 et 1761, Euler en publie deux qui procèdent par récurrence et utilisent le développement du binôme, et une qui étudie la répartition des restes modulo le nombre premier considéré. On trouve cette dernière en 1801 dans les Modèle:Lang de Gauss. Il y résume également la première démonstration d'Euler, et en donne une version plus rapide utilisant le développement du multinôme.

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 ». On trouve la dénomination « petit théorème de Fermat » (Modèle:Lang) dans un ouvrage de Kurt Hensel de 1913.

Un étudiant américain, cité entre autres par Dickson, avait avancé que le théorème était déjà connu en Chine Modèle:Unité avant Fermat, dans le cas particulier Modèle:Math, accompagné d'une réciproque — trivialement fausse. Cette « hypothèse chinoise » n'est qu'une légende urbaine, due à une erreur de traduction qui s'est amplifiée et déformée au fil des citationsModèle:,.

Exemples

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

• 5³ − 5 = 120 est divisible par 3
• 7² − 7 = 42 est divisible par 2.
• 2⁵ − 2 = 30 est divisible par 5.
• (−3)⁷ + 3 = −2 184 est divisible par 7.
• 2⁹⁷ − 2 = 158 456 325 028 528 675 187 087 900 670 est divisible par 97.

Applications

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

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 à 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

Modèle:Article détaillé 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. Modèle:Référence nécessaire

Test de primalité

Modèle:Article détaillé Le petit théorème de Fermat donne une condition nécessaire pour qu'un nombre Modèle:Mvar soit premier. Il faut en effet que, pour tout Modèle:Mvar plus petit que Modèle:Mvar, Modèle:Math 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

Modèle:Article détaillé Les tests précédents utilisent une condition nécessaire mais non suffisante. Ainsi, il existe des entiers Modèle:Mvar non premiers tels que pour tout Modèle:Mvar premier avec Modèle:Mvar, Modèle:Math soit toujours congru à 1 modulo Modèle:Mvar. Le nombre 1 729 est un exemple. De tels entiers Modèle:Mvar 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 pseudo-premiers et sont attachés à des tests particuliers.

Démonstrations

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

Par le théorème de Lagrange

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

Démonstration d'Euler et de Leibniz

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 l'entier Modèle:Mvar, supposé positif sans perte de généralité. Leur raisonnement (reformulé ici dans le langage des congruences introduit ultérieurement par Gauss), est le suivant :

• La proposition Modèle:Math est vraie pour Modèle:Math.
• Tout entier Modèle:Mvar vérifie : $(k+1{)}^p\equiv k^p+1(\mathrm{mod}p)$.
  Il suffit, pour cela, de développer l'expression Modèle:Math et de remarquer que tous les coefficients binomiaux à l'exception du premier et du dernier sont des multiples de Modèle:Mvar car Modèle:Mvar est premier (une démonstration est donnée dans le paragraphe « Diviseurs et coefficients binomiaux » de l'article « Coefficient binomial »).
• Enfin, si la proposition est vraie pour Modèle:Math alors elle l'est aussi pour Modèle:Math. En effet, grâce au point précédent, il est prouvé que $(k+1{)}^p\equiv k^p+1(\mathrm{mod}p)$. Si de plus $k^p\equiv k(\mathrm{mod}p)$, alors $(k+1{)}^p\equiv k+1(\mathrm{mod}p)$.

Équivalence des deux énoncés

Si le premier énoncé est vrai alors le second aussi : Pour Modèle:Mvar quelconque, comme Modèle:Math est égal au produit Modèle:Math, on sait que ce produit est toujours divisible par Modèle:Mvar, car ou bien Modèle:Mvar est multiple de Modèle:Mvar, ou bien il ne l'est pas mais le premier énoncé assure alors que Modèle:Math est divisible par Modèle:Mvar.

Réciproquement, le premier énoncé se déduit du second en utilisant le lemme d'Euclide : si Modèle:Math est divisible par Modèle:Mvar et si Modèle:Mvar ne l'est pas, alors Modèle:Math l'est.

Une démonstration arithmétique élémentaire

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 Modèle:Mvar, de deux façons, le produit

$N=a\times 2a\times 3a\times \dots (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

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

Généralisations

Une légère généralisation du théorème s'énonce de la manière suivante : si Modèle:Mvar est un nombre premier et si Modèle:Mvar et Modèle:Mvar sont des entiers strictement positifs tels que Modèle:Math alors, pour tout entier Modèle:Mvar :

$a^m\equiv a^n(\mathrm{mod}p)$

En effet, modulo Modèle:Mvar, les deux membres sont congrus à 0 si Modèle:Mvar est divisible par Modèle:Mvar, et s'il ne l'est pas, alors Modèle:Math. 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 Modèle:Mvar et tout entier Modèle:Mvar premier avec Modèle:Mvar, on a

$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$

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

Il se généralise de même à tout corps fini donc à tout quotient de l'anneau des entiers d'un corps de nombres par un idéal premier.

Annexes

Bibliographie

Mathématiques

• Modèle:HardyWright
• Modèle:Samuel1
• Modèle:Ouvrage

Histoire des mathématiques

• Modèle:Ouvrage, 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 Modèle:Date- (XLIV de l'édition Tannery-Henry) p 163.
• Modèle:Ouvrage, Avertissement p IX-XXXVII.
• Modèle:Ouvrage, XL, Fermat à Mersenne, juin ? 1640, p 198, et XLIV, Fermat à Frenicle, jeudi Modèle:Date-, p 208.
• Modèle:Weil1 (chap. II. Fermat and his correspondents).

Liens externes

• Modèle:Lien archive
• Le petit théorème de Fermat sur le site de G. Villemin
• Fermat revisité par M. Gouy, G. Huvent et A. Ladureau