Petit théorème de Fermat

Infos
Pierre de Fermat propose le théorème sans apporter de démonstration. En mathématiques, le petit théorème de Fermat est un résultat de l'arithmétique modulaire. Il s'énonce comme suit. Si a est un entier quelconque et p un nombre premier, alors a p - a est un multiple de p. Il doit son nom à Pierre de Fermat (1601 - 1665) qui l'énonce la première fois le 18 octobre 1640. Il dispose de nombreuses applications, à la fois en arithméti
Petit théorème de Fermat

Pierre de Fermat propose le théorème sans apporter de démonstration. En mathématiques, le petit théorème de Fermat est un résultat de l'arithmétique modulaire. Il s'énonce comme suit. Si a est un entier quelconque et p un nombre premier, alors a p - a est un multiple de p. Il doit son nom à Pierre de Fermat (1601 - 1665) 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

Leonhard Euler, rédige en 1735 la première démonstration publiée du théorème. La Chine semble être la première culture à s'être intéressée à l'arithmétique modulaireSun Zi Sunzi suanjing Manuel de mathématiques de Sun Zi vers 300. Il existe une hypothèseJoseph Needham (Ed.) Mathematics and the Sciences of the Heavens and the Earth Science and Civilisation in China, Vol. 3 Ch. 19 Cambridge University Press, 1959, réfuté par Joseph Needham, selon laquelle des nombres de la forme 2p - 2 ont été étudiés par cette civilisation 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 (1605 - 1675). 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 ..."Pierre de Fermat Lettre de Fermat à Frénicle du 18 octobre 1640 . 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". A cette époque, il est d'usage de ne pas publier les preuves des théorèmes. Ainsi Gottfried Wilhelm von Leibniz (1646 - 1716) rédige une démonstrationM. BÜLHER et A. MICHEL-PAJUS Une démonstration du théorème de Fermat par Leibniz, MNEMOSYNE n°19, "Bonnes vieilles pages (2)p 61-66 2007 vers 1683 mais ne la publie pas. La preuveLeonhard Euler Démonstration de quelques théorèmes relatifs aux nombres premiers 1736 devient publique en 1736 suite aux travaux du mathématicien Leonhard Euler (1707 - 1783). Carl Friedrich Gauss (1777 - 1855) rédigeCarl Friedrich Gauss, Recherches arithmétiques, 1801 Traduction M. Poullet-Delisle Ed. Courcier p 34 1807 une nouvelle preuve plus rapide en 1801. Le terme communément utilisé jusqu'au est théorème de Fermat choisi par exemple par Gauss dans son livre Disquisitiones arithmeticae. Le théorème change de nomKurt Hensel Zahlentheorie Göschen, Berlin/Leipzig 1913 en 1913 pour prendre sa forme actuelle.

Exemples

Voici quelques exemples du théorème :
- 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

Les applications sont nombreuses, particulièrement en cryptographie. On trouve néanmoins des exemples classiques d'applications du théorèmes 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 écritPierre de Fermat Lettre à Marin Mersenne du 7 avril 1643 à Marin 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é. A 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écryptage 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 décimales. Il contient deux facteurs premiers. L'essentiel des techniques industriels du début du 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 connus 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 tel que pour tout a compris entre un et p - 1, a p - 1 est toujours congru à un modulo p. Le nombre 1729 est un exemple. De tels nombres sont appelés nombre de Carmichaël. 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 le nombre ayant passé le test ne soit néanmoins pas premiers. Ces nombres sont appelés pseudopremiers et sont attachés à des tests particuliers.

Généralisations

Une légère généralisation du théorème, qui découle immédiatement de celui-ci, 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 tous entiers a, aman (mod p). Sous cette forme, le théorème est utilisé pour justifier l'algorithme de chiffrage RSA à clé publique. 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) \equiv 1 \pmod où φ(n) désigne la fonction φ d'Euler comptant les entiers entre 1 et n qui sont premiers avec n. Si n est un nombre premier, alors φ(p) = p - 1, on retrouve le petit théorème de Fermat. La démonstration se fonde sur le fait que le groupe des unités de l'anneau Z/nZ est d'ordre φ(n).

Démonstrations

Arithmétique modulaire

Carl Friedrich Gauss fondateur de l'arithmétique modulaire. La connaissance de la structure et particulièrement du groupe des unités de l'anneau Z/pZ, permet une démonstration simple du théorème. Si p est un nombre premier, le groupe des unités Z/pZ
- est un groupe cyclique d'ordre p - 1, donc isomorphe à Z/(p - 1)Z. Une première approche consiste à considérer φ cet isomorphisme. L'image de φ(ap-1) est égal à (p - 1)φ(a), correspondant à l'élément neutre du groupe. On en déduit que ap-1 est l'élément neutre de Z/pZ
-, c'est à dire la classe de l'unité, ce qui termine la démonstration. Une deuxième approche est l'application du théorème de Lagrange, l'ordre de tout élément d'un groupe fini est un diviseur de l'ordre du groupe. En conséquence, si θ est l'ordre de a, alors il existe un entier μ tel que θ.μ = p - 1. L'entier a θ est un élément de la classe de l'unité par définition de l'ordre d'un élément (cf le paragraphe Définitions de l'article Groupe cyclique) et donc a p - 1= a θ.μ est aussi élément de la classe de l'unité. Ces approches correspondent à la fois au travail de Gauss et aux démonstrations modernes, ce sont en effet les plus concises.

Démonstration d'Euler et de Leibniz

Il existe une autre démonstration, utilisant la formule du binôme de Newton. Cette démonstration correspond à celle d'Euler et de Leibniz. Elle utilise un raisonnement par récurrence sur la valeur a. Pour une raison de simplicité, les notations utilisées ici sont celle de Gauss, utilisant les congruences. Si ces notations ne correspondent pas à celles de l'époque, le raisonnement est néanmoins identique.

Une démonstration limitée au savoir de Fermat

Il est possible d'imaginer une démonstration ne faisant qu'appel aux connaissances de Fermat. Elle est conséquence plus longue et demande une démarche plus astucieuse pour aboutir. Elle utilise essentiellement le lemme d'Euclide, la division euclidienne et l'identité de Bézout. boîte déroulante|align=left|titre=Démonstration fondée sur le savoir de Fermat|contenu= :
- Si a n'est pas premier avec p, alors a p - a est un multiple de p. D'après le lemme d'Euclide a est un multiple de p, il en est de même de a p et de a et donc de leur différence. Pour la suite de la démonstration, a est supposé être premier avec p. Pour étudier ce cas, il est nécessaire d'établir un lemme : :
- L'application φ de dans lui même, qui à k associe le reste de la division euclidienne de a.k par p est une bijection. Remarquons tout d'abord que p est premier avec a et k, le reste de la division de a.k par p n'est donc jamais égal à zéro et l'ensemble d'arrivé est bien celui de la fonction φ. Montrons alors l'injectivité de φ. Soit k1 et k2 deux entiers de l'intervalle , ayant même image par φ et tel que k1 est supérieur ou égal à k2. On remarque de p divise a.(
k1 - k2). Comme p est premier avec a, il divise k1 - k2 d'après le lemme d'Euclide. Comme k1 - k2 est élément de l'intervalle et que p est premier, k1 est égal à k2. La surjectivité de φ est une conséquence du fait que toute application injective d'un ensemble fini dans lui-même est surjective. :
- Le reste de la division euclidienne de (
p - 1)!a p-1 par p est égal au reste de la division euclidienne de (p - 1)! par p. Ici, le symbole ! désigne l'application factorielle. Cette proposition utilise le fait que si r1 et r2 désignent les restes de la division euclidienne de deux entiers n1 et n2 par p, alors les produits n1.n2 et r1.rr ont même reste pour la division euclidienne par p. Cette propriété est étudiée dans l'article Congruence sur les entiers. Une simple récurrence permet alors d'établir que la division euclidienne de (p - 1)! par p possède le même reste que la division euclidienne du produit des φ(k) si k parcourt l'intervalle d'après la proposition précédente. Elle montre aussi que le reste que la division euclidienne du produit des φ(k) si k parcourt l'intervalle par p est égal au reste de la division euclidienne de (p - 1)!a p-1 par p. Ce qui démontre la proposition. :
- La valeur a p - a est un multiple de p. Comme p est un nombre premier, le lemme d'Euclide montre qu'il est premier avec (
p - 1)!, l'identité de Bézout montre l'existence de deux entiers m et n tel que : (1)\quad m (p - 1)! + np \ = \ 1 On en déduit que m.(p - 1)! possède pour reste de la division euclidienne par p, la valeur un. L'égalité (1) montre que : m (p - 1)!a^ + npa^ \ = \ a^ Le reste de la division euclidienne de a p-1 par p est donc égal à celui de la division euclidienne de m.(p - 1)!a p-1. La proposition précédente montre que ce reste est égal au reste de la division euclidinne de m.(p'' - 1)!, qui est égal à un. Ce qui montre que a p-1 - 1 est un multiple de p et une multiplication par a termine la démonstration.

Notes et références

Notes

===
Sujets connexes
Anneau Z/nZ   Arithmétique   Arithmétique modulaire   Bernard Frénicle de Bessy   Carl Friedrich Gauss   Chiffrement   Civilisation chinoise   Clé de chiffrement   Coefficient binomial   Confidentialité   Congruence sur les entiers   Cryptographie   Disquisitiones arithmeticae   Division euclidienne   Décomposition en produit de facteurs premiers   Endomorphisme de Frobenius   Factorielle   Formule du binôme de Newton   Gottfried Wilhelm von Leibniz   Groupe cyclique   Groupe des unités   Identité de Bézout   Indicatrice d'Euler   Injection (mathématiques)   Isomorphisme   Joseph Needham   Kurt Hensel   Lemme d'Euclide   Leonhard Euler   Marin Mersenne   Mathématiques   Mathématiques pures   Nombre de Carmichaël   Nombre de Fermat   Nombre premier   Pierre de Fermat   Raisonnement par récurrence   Rivest Shamir Adleman   Sun Zi (mathématicien)   Surjection   Test de primalité de Fermat   Test de primalité de Miller-Rabin   Test de primalité de Solovay-Strassen   Théorie algébrique des nombres   Théorème d'Euler   Théorème de Herbrand-Ribet   Théorème fondamental de l'arithmétique  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^