Test de primalité de Fermat

En algorithmique, le test de primalité de Fermat est un test de primalité basé sur le petit théorème de Fermat.

Base arithmétique

Le petit théorème de Fermat affirme que si p est un nombre premier et si a est premier avec p, alors ap-1-1 est divisible par p. C'est-à-dire, en termes de congruence sur les entiers :

La réciproque de ce théorème est fausse, par exemple : 561=3×11×17 n'est pas premier et pourtant pour tout entier a premier avec 561, on a . Les nombres qui font échouer la réciproque sont appelés nombres de Carmichaël, et forment un ensemble infini.