Petit théorème de Fermat
Le petit théorème de Fermat affirme que si p est un nombre premier, alors pour tout entier a,
Cela signifie que si vous considérez un entier a, et que vous le multipliez par lui-même p fois et que vous lui soustrayez 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 ap-1 - 1 lorsque p est premier et a est premier avec p. Le cas a = 2 était connu des anciens chinois.
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.
Voir les démonstrations du petit théorème de Fermat.
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, am ≡ an (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, nous avons
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.
Pseudo-premiers
Si a et p sont premiers entre eux, il arrive que ap-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, ap − 1 − 1 est divisible par p, alors p est premier.