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.

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. »

Un énoncé équivalent est : « si p est un nombre premier et si a est un entier quelconque, alors a ^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

Il existe une hypothèse^[1], réfutée par Joseph Needham, selon laquelle des nombres de la forme 2^p - 2 ont été étudiés par les peuples asiatiques depuis 2 500 ans.

La première apparition connue de l'énoncé de ce théorème provient d'une lettre de Fermat à Frénicle de Bessy en 1640. 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 »^[2]. Cette formulation est l'exact équivalent de la formulation moderne donnée en introduction. Fermat ne donne aucune démonstration de ce résultat, mais précise 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 Leibniz rédige une démonstration^[3] vers 1683 mais ne la publie pas. Euler en présente une en 1736 à l'Académie des sciences de Saint-Pétersbourg, qui la publie en 1741^[4]. Gauss publie^[5] une nouvelle preuve plus rapide dans ses Disquisitiones arithmeticae de 1801.

Le terme communément utilisé jusqu'au XX^e siècle est théorème de Fermat choisi par exemple par Gauss. Le théorème change de nom^[6] en 1913 pour prendre sa forme actuelle.

Exemples

Voici quelques exemples (basé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^[7] à 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

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 XXI^e 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 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

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.

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 m ≡ n (mod p-1), alors pour tous entiers a, a^m ≡ aⁿ (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) 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 φ(n) = n - 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

Carl Friedrich Gauss, fondateur de l'arithmétique modulaire.

Arithmétique modulaire

L'essentiel de la preuve par Gauss du premier énoncé^[5], reformulé en termes modernes, consiste à démontrer que l'ordre t de a dans dans le groupe multiplicatif Z/pZ* 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 a^t ≡ 1 (mod p) à la puissance : l'entier (p - 1)/t.

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 la valeur a. Leur raisonnement (reformulé ici dans le langage des congruences introduit ultérieurement par Gauss), est le suivant :

• La proposition a^p ≡ a (mod p) est vraie pour a = 1.
• Tout entier k vérifie : (k + 1)^p ≡ k^p + 1 (mod p).

Il suffit 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.

• Si la proposition est vraie pour a = k alors elle l'est aussi pour a = k + 1.

Ce dernier point est une conséquence directe du précédent.

Équivalence des deux énoncés

Si le premier énoncé est vrai alors le second aussi : a^p-a est égal au produit a (a^p-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 second énoncé se déduit du premier en utilisant le lemme d'Euclide : si a(a^p-1-1) est divisible par p et si a ne l'est pas, alors a^p-1-1 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 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 Z/pZ, 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.

Démonstration

Supposons que a n'est pas divisible par p et notons

N le produit a.2a.3a.….(p-1)a

r_k le reste de la division euclidienne de ka par p, pour tout entier k de 1 à p-1. Alors

• En réordonnant les facteurs, N = 1.2. … .(p - 1).a^p-1 = (p-1)!a^p-1.
• Par ailleurs, N ≡ r₁.r₂. … .r_p-1 (mod p). En effet, si dans un produit on remplace un facteur par un entier qui lui est congru modulo p alors le nouveau produit est congru modulo p à l'ancien. En remplaçant dans N, un par un, chaque ka par r_k, le résultat est donc congru à N modulo p.
• Or r₁.r₂. … .r_p-1 = (p-1)! car (r₁, r₂, … , r_p-1) est une permutation de (1, 2, … , p - 1). En effet, 0 ≤ r_k ≤ p - 1 et

aucun r_k n'est nul, car (d'après le lemme d'Euclide) aucun ka n'est divisible par p ;

les r_k sont distincts deux à deux, car si r_i = r_j alors (i - j)a est divisible par p, donc (à nouveau par le lemme d'Euclide) i - j aussi, donc (comme -p < i - j < p) i = j.

• Des trois points précédents on déduit : (p-1)!a^p-1 ≡ (p-1)! (mod p), autrement dit (p-1)!(a^p-1-1) est divisible par p. Par application répétée du lemme d'Euclide, on obtient la conclusion : a^p-1-1 est divisible par p.

Notes et références

Notes

1. ↑ (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
2. ↑ P. de Fermat, Lettre de Fermat à Frénicle du 18 octobre 1640, lire
3. ↑ 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
4. ↑ (la) L. Euler, « Theorematum quorundam ad numeros primos spectantium demonstratio », dans Comment. acad. sc. Petrop., vol. 8, 1741, p. 141-146 , disponible sur le site du Dartmouth College sous le numéro E54, avec traduction en anglais
5. ↑ ^{a et b} C. F. Gauss, Recherches arithmétiques, 1801, traduit par A.-C.-M. Poullet-Delisle en 1807, éd. Courcier, p. 34
6. ↑ (de) Kurt Hensel, Zahlentheorie, Göschen, Berlin/Leipzig, 1913
7. ↑ P. de Fermat, Lettre à Marin Mersenne du 7 avril 1643 lire

Références

• Pierre Samuel, Théorie algébrique des nombres [détail des éditions]
• (en) G. H. Hardy et E. M. Wright (en), An Introduction to the Theory of Numbers [détail des éditions]
• Gilles Zémor, Cours de cryptographie, Cassini, 2000 (ISBN 2-8422-5020-6) 
• E. Brassinne, Précis des œuvres mathématiques de P Fermat et de l'Arithmétique de Diophante, Mallet-Bachelier, 1853, rééd. J. Gabay, 1989 (ISBN 9782876470552)

Liens externes

• Une présentation sans la notion de congruence de la démontration d'Euler et Leibniz ci-dessus, par Michel Hort
• Le petit théorème de Fermat sur le site de G. Villemin
• Fermat revisité par M. Gouy, G. Huvent et A. Ladureau, sur le site de CultureMATH