Petit théorème de Fermat

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

En mathématiques, le petit théorème de Fermat affirme que si p est un nombre premier, alors pour tout entier a,

$a^p \equiv a \pmod{p}$

Cela signifie que si on considère un entier a, et qu'on le multiplie par lui-même p fois et qu'on lui soustrait a, le résultat est divisible par p (voir arithmétique modulaire). Il s'appelle le petit théorème de Fermat pour le différencier du dernier théorème de Fermat. Pierre de Fermat trouva le théorème en 1636 ; il apparut dans l'une de ses lettres, envoyée le 18 octobre 1640 à son confident Bernard Frénicle de Bessy sous la forme équivalente suivante : p divise a^p-1 - 1 lorsque p est premier et a est premier avec p. Le cas a = 2 était connu des anciens chinois.

Le petit théorème de Fermat est à la base du test de primalité de Fermat.

Voici quelques exemples du théorème :

4³ − 4 = 60 est divisible par 3.
7² − 7 = 42 est divisible par 2.
6³ − 6 = 210 est divisible par 3.
(−3)⁷ − (−3) = −(2 184) est divisible par 7.
2⁹⁷ − 2 = 158 456 325 028 528 675 187 087 900 670 est divisible par 97.

Sommaire

1 Démonstrations
- 1.1 Davantage d'histoire
2 Généralisations
3 Pseudo-premiers

[modifier] Démonstrations

Fermat expliqua son théorème sans preuve. Le premier qui donna une démonstration fut Gottfried Wilhelm Leibniz dans un manuscrit non daté, dans lequel il écrivit aussi qu'il connaissait déjà une preuve avant 1683 :

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.

Voir l’article Démonstrations du petit théorème de Fermat.

La locution "Petit théorème de Fermat" a été utilisée la première fois en 1913 dans l'ouvrage de Kurt Hensel Zahlentheorie :

Für jede endliche Gruppe besteht nun ein Fundamentalsatz, welcher der kleine Fermatsche Satz genannt zu werden pflegt, weil ein ganz spezieller Teil desselben zuerst von Fermat bewiesen worden ist."

(Il existe un théorème fondamental qui est valable dans chaque groupe fini, habituellement appelé le Petit théorème de Fermat parceque Fermat a été le premier a démontrer une partie très particulière de celui-ci).

Elle fut utilisée en anglais en premier dans un article d'Irving Kaplansky, Lucas's Tests for Mersenne Numbers, American Mathematical Monthly, 52 (Avril 1945).

[modifier] Davantage d'histoire

Les mathématiciens chinois ont, de manière indépendante, fait l'hypothèse reliée (quelquefois appelée l'hypothèse chinoise) que p est un nombre premier si et seulement si $2^p \equiv 2 \pmod{p}\,$ . Ceci est vrai si p est premier, alors $2^p \equiv 2 \pmod{p}\,$ (c'est un cas particulier du petit théorème de Fermat). Par contre, la réciproque (si $\,2^p \equiv 2 \pmod{p}$ alors p est premier), et par conséquent l'hypothèse dans son entier, est fausse (par ex. 341=11×31 est un pseudopremier, voir ci-dessous).

[modifier] 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. Cette proposition représente vraiment une généralisation, parce que si n = p est un nombre premier, alors φ(p) = p - 1. Cela peut encore être généralisé en le théorème de Carmichaël.

Voir la démonstration dans l'article groupe cyclique et anneau.

[modifier] Pseudo-premiers

Si a et p sont premiers entre eux, il arrive que a^p-1 - 1 soit divisible par p, sans pour autant que p soit premier. Si c'est le cas, alors p est appelé un nombre pseudo-premier de base a. Si, pour tout entier a, premier avec p, tel que 1 < a < p, l'entier p est pseudo-premier de base a, alors l'entier p est appelé un nombre de Carmichaël ou nombre absolument pseudo-premier.

Attention, la condition « a premier avec p » est nécessaire : si p est pseudo-premier dans toute base a tel que 1 < a < p, c'est-à-dire, si pour tout a tel que 1 < a < p, $a p - 1 - 1$ est divisible par p, alors p est premier.