Nombre de Carmichael

Un nombre de Carmichael est un nombre entier $ n $ qui est composé (donc pas un nombre premier) tel que pour tout entier $ a $ la formule suivante est vraie : $$ a^{{n-1}} \equiv 1 \mod{n} \iff a^{{n}} \equiv a \mod{n} $$

Donc, pour tout entier $ p $ premier avec $ n $, la propriété $ n \mid p^n-p $ est vérifiée (qui se lit $ n $ divise $ p^n-p $) donc $ p^n-p $ est un multiple de $ n $

Parfois, l'expression est réécrite $ n \mid p^{n–1}–1 $ ce qui permet de se rendre compte qu'un nombre de Carmichael satisfait le petit théorème de Fermat : $$ p^{n-1}-1 \equiv 0 \mod{n} $$

Les nombres de Carmichael sont aussi appelé nombres absolument pseudo-premiers ou nombre pseudo-premiers d'Euler-Jacobi.

Il n'existe pas de formule pour trouver rapidement tous les nombres de Carmichael mais il est possible d'utiliser un algorithme qui est conditionné par un test de primalité et de la vérification de $ a^{{n-1}} \equiv 1 \mod{n} $

Les nombres de Carmichael ne sont jamais divisibles par un carré (leur décomposition en nombres premiers possède au moins 3 facteurs).

Le plus petit nombre de Carmichael est $ 561 $ qui a pour décomposition en facteurs premiers $ 561 = 3 \times 11 \times 17 $

Voici la liste des nombres de Carmichael jusque 1 million : 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461, 530881, 552721, 656601, 658801, 670033, 748657, 825265, 838201, 852841, 997633, etc.

Suite de l'OEIS A002997 ici

Robert Daniel Carmichael était un mathématicien américain qui a publié une étude sur ces nombres en 1912.