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

Table of contents

1 Démonstrations
2 Généralisations
3 Pseudo-premiers

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, 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, 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 tels que a^p-1 - 1 soit divisible par p, alors p n'a nul besoin d'être premier. Si ce n'est pas le cas, alors p est appelé un nombre pseudo-premier de base a. Un nombre p qui est un nombre pseudo-premier dans une base a pour tout nombre a premier avec p est appelé un nombre de Carmichaël. Attention, si p est pseudo-premier dans toute base a tel que 1a, 1a^p-1 - 1 est divisible par p, alors il est premier.

Tous les textes sont disponibles sous les termes de la Wikipedia se publica bajo la Licencia de Documentación Libre GNU.

Legal - Contacto