Petit théorème 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.



Catégories :

Théorème d'algèbre - Équation diophantienne - Arithmétique élémentaire - Mathématiques élémentaires

Recherche sur Google Images :


Source image : mathovore.fr
Cette image est un résultat de recherche de Google Image. Elle est peut-être réduite par rapport à l'originale et/ou protégée par des droits d'auteur.

Page(s) en rapport avec ce sujet :

  • ... La démonstration du petit théorème de Fermat est une des démonstration les ... Démonstration : la totalité des nombres premiers est illimité... (source : diderot.ac)
  • Rappel : La propriété nommée " petit théorème de Fermat" est la suivante : " Soit p un nombre premier et a un entier naturel premer avc p, ... (source : forums.futura-sciences)
  • o quoique 341 soit composé, par conséquent p a s premier. o Montre que l a réciproque du petit théorème de Fermat est fausse. Génér a lis a tion. * Nombre pseudo-... (source : villemin.gerard.free)
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, 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 (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.

Il existe une hypothèse[1], 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 (1605 - 1675) . On peut y lire ceci : "Tout nombre premier mesure inévitablement 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... "[2]. Cette formulation est l'exact équivalent de la formulation moderne donnée en introduction. Fermat avait certainement démontré ce résultat, il précise en effet dans sa lettre : "Et cette proposition est le plus souvent 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 habituel de ne pas publier les preuves des théorèmes. Ainsi Gottfried Wilhelm von Leibniz (1646 - 1716) rédige une démonstration[3] vers 1683 mais ne la publie pas. La preuve[4] devient publique en 1736 suite aux travaux du mathématicien Leonhard Euler (1707 - 1783) . Carl Friedrich Gauss (1777 - 1855) rédige[5] une nouvelle preuve plus rapide en 1801.

Le terme couramment utilisé jusqu'au XXe siècle est théorème de Fermat choisi par exemple par Gauss dans son ouvrage Disquisitiones arithmeticæ. Le théorème change de nom[6] en 1913 pour prendre sa forme actuelle.

Exemples

Voici quelques exemples du théorème :

Applications

Les applications sont nombreuses, en particulier 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[7] à 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é. À 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

Article détaillé : Cryptographie asymétrique.

La cryptographie à clé publique correspond à un code s'attachant à assurer la confidentialité des messages avec deux clés de chiffrement. L'une, servant à 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 nommée Rivest Shamir Adleman. La clé secrète est la donnée décomposition d'un grand nombre entier, fréquemment de plusieurs centaines de chiffres. Il contient deux facteurs premiers. La majeure partie 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é

Article détaillé : test de primalité.

Le petit théorème de Fermat donne une condition indispensable 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 en particulier le test de primalité de Miller-Rabin.

Nombre pseudo-premier

Article détaillé : Nombre pseudopremier.

Les tests qui ont précédé utilisent une condition indispensable 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 nommés nombre de Carmichæl.

Les tests indiqués au paragraphe précédent sont tous statistiques, au sens ou il existe toujours une probabilité, quelquefois particulièrement faible pour le nombre ayant passé le test ne soit néanmoins pas premiers. Ces nombres sont nommés pseudopremiers et sont attachés à des tests spécifiques.

Généralisations

Une légère généralisation du théorème, qui découle immédiatement de ce dernier, 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{n}

où φ (n) sert à désigner 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

Article détaillé : Arithmétique modulaire.

La connaissance de la structure et spécifiquement 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, par conséquent isomorphe à Z/ (p - 1) Z.

Une première approche consiste à considérer φ cet isomorphisme. L'image φ (ap-1) de ap-1 est égale à (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 par conséquent a p - 1= a θ. μ est aussi élément de la classe de l'unité.

Ces approches correspondent à la fois au travail de Gauss ainsi qu'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 celles de Gauss, utilisant les congruences. Si ces notations ne correspondent pas à celles de l'époque, le raisonnement est néanmoins semblable.

Une démonstration arithmétique élémentaire

Il existe aussi une autre démonstration qui utilise principalement le lemme d'Euclide, la division euclidienne et l'identité de Bézout.

Notes et références

Notes

  1. Joseph 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
  2. Pierre de Fermat Lettre de Fermat à Frénicle du 18 octobre 1640 lire
  3. M. 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
  4. Leonhard Euler Démonstration de quelques théorèmes relatifs aux nombres premiers 1736
  5. Carl Friedrich Gauss, Recherches arithmétiques, 1801 Traduction M. Poullet-Delisle Ed. Courcier p 34 1807
  6. Kurt Hensel Zahlentheorie Göschen, Berlin/Leipzig 1913
  7. Pierre de Fermat Lettre à Marin Mersenne du 7 avril 1643 lire

Liens externes

Références

Recherche sur Amazone (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Petit_th%C3%A9or%C3%A8me_de_Fermat.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu