Un entier composé n tel que, pour tout entier a premier avec n, a^{n−1} ≡ 1 (mod n) ; n se comporte donc comme un nombre premier pour la congruence de Fermat pour toutes les bases premières avec lui.

Principe

Désigne des modules composés qui réussissent le test de primalité de Fermat pour toute base première avec eux ; caractérisation équivalente par des conditions de type Korselt (sans carré et tout diviseur premier p vérifie p−1 | n−1).

Démonstration

Le plus petit exemple est 561 = 3·11·17 ; pour tout a premier avec 561, a^{560} ≡ 1 (mod 561), donc 561 est un nombre de Carmichael et tromperait systématiquement un test de Fermat simple.

Mauvaise application

Qualifier tout pseudopremier de Fermat (qui peut vérifier la congruence pour certaines bases mais pas toutes) de nombre de Carmichael, ou supposer qu'un entier satisfaisant la congruence pour plusieurs petites bases est Carmichael sans vérifier toutes les bases premières avec lui.

Conséquence

Illustre les limites des tests de primalité naïfs : l'existence de nombres de Carmichael impose d'utiliser des tests déterministes ou probabilistes plus robustes ; leur distribution affecte le seuil de confiance des tests basés sur des bases fixes.

Inversion

Les nombres premiers constituent l'inverse : ils satisfont la même congruence mais sont effectivement premiers ; l'inverse peut aussi être des composés qui échouent la congruence pour certaines bases et sont donc facilement détectables par Fermat.

Limite

Défini uniquement pour les entiers composés ; exige que la congruence tienne pour tout entier premier avec n. Exclut les pseudopremiers de Fermat qui vérifient la congruence seulement pour un sous-ensemble de bases et exclut les nombres premiers.

Tension sémantique

En tension avec les notions de pseudopremier de Fermat, pseudopremier d'Euler et pseudopremier fort ; la tension porte sur la différence entre tromperie pour toutes les bases (Carmichael) et tromperie pour des bases particulières (pseudopremiers).

Synthèse

Un nombre de Carmichael est un entier composé et sans carré dont la structure multiplicative force la congruence de Fermat pour toute base première avec lui : un pseudopremier universel qui révèle les limites des contrôles de primalité simples.