Petit théorème de Fermat - Définition
La liste des auteurs de cet article est disponible ici.
Introduction
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 a est un entier non divisible par p tel que p est un nombre premier, alors a p-1 - 1 est un multiple de p. Le corollaire de ce théorème est que, pour tout a entier et p nombre premier, alors a p - a est un multiple de p. »
Il doit son nom à Pierre de Fermat qui l'énonce la première fois le 18 octobre 1640.
Il dispose de nombreuses applications, à la fois en arithmétique modulaire et en cryptographie.
Histoire
Il existe une hypothèse, réfutée par Joseph Needham, selon laquelle des nombres de la forme 2p - 2 ont été étudiés par les peuples asiatiques depuis 2 500 ans.
La première apparition connue de ce théorème provient d'une lettre de Fermat à Bernard Frénicle de Bessy . 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 ...". Cette formulation est l'exact équivalent de la formulation moderne donnée en introduction. Fermat avait probablement démontré ce résultat, il précise en effet dans sa lettre: "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".
À cette époque, il est d'usage de ne pas publier les preuves des théorèmes. Ainsi Gottfried Wilhelm von Leibniz rédige une démonstration vers 1683 mais ne la publie pas. La preuve devient publique en 1736 suite aux travaux du mathématicien Leonhard Euler . Carl Friedrich Gauss rédige une nouvelle preuve plus rapide en 1801.
Le terme communément utilisé jusqu'au XXe siècle est théorème de Fermat choisi par exemple par Gauss dans son livre Disquisitiones arithmeticae. Le théorème change de nom en 1913 pour prendre sa forme actuelle.
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 à Marin Mersenne : "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, à savoir 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
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 codes asymétrique utilise la technologie appelée Rivest Shamir Adleman. La clé secrète est la donnée 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é
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 à un modulo p. Ce principe est la base du test de primalité de Fermat. Il existe de nombreuses variantes algorithmique 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
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 à un modulo p. Le nombre 1729 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 ou 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.
