conjecture de Carmichael

Prenons 561 : il se décompose en 3 × 11 × 17, donc il n’est pas premier. Pourtant, lorsqu’on lui applique le calcul modulaire du petit théorème de Fermat avec une base qui n’a aucun facteur commun avec lui, il se comporte comme un nombre premier.

Un tel entier composé est un nombre de Carmichael. L’ancienne conjecture affirmait qu’il en existe une infinité. Depuis sa démonstration en 1994, il s’agit donc d’un théorème, même si son nom historique est resté.

Un nombre de Carmichael est un entier composé, noté n, qui satisfait la congruence du petit théorème de Fermat pour toute base admissible. Une base admissible est un entier a premier avec n, c’est-à-dire sans diviseur commun avec n autre que 1. La condition s’écrit $a^n\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}n)a^n\; \backslash equiv\; a\; \backslash pmod\; n$. Comme a est inversible modulo n, elle équivaut à $a^{n-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)a^\{n-1\}\; \backslash equiv\; 1\; \backslash pmod\; n$.

Ces entiers sont aussi appelés pseudopremiers absolus : ils passent le test de Fermat pour toutes les bases premières avec eux, bien qu’ils soient composés. La propriété ne dit pas qu’ils passent tous les tests de primalité. Elle révèle précisément la limite des tests qui concluent à partir de cette seule congruence.

La conjecture de Carmichael affirmait que ces nombres sont en quantité infinie. Alford, Granville et Pomerance l’ont démontré en 1994. Ils ont même établi que, pour toute valeur réelle x suffisamment grande, le nombre de nombres de Carmichael inférieurs à x dépasse x^2/7.

Soit x une borne réelle positive, et soit C(x) le nombre de nombres de Carmichael inférieurs à x. Si x est suffisamment grand, alors le résultat d’Alford, Granville et Pomerance donne :

La borne de droite grandit sans limite avec x. Il existe donc une infinité de nombres de Carmichael, ce qui démontre l’ancienne conjecture.

La définition s’applique à un entier n qui doit d’abord être composé. La congruence est ensuite exigée pour chaque entier a premier avec n, et non pour une seule base choisie. Pour vérifier un candidat sans parcourir toutes les bases, le critère de Korselt donne deux conditions équivalentes : n ne contient aucun carré de nombre premier et, pour chaque diviseur premier p de n, le nombre p − 1 divise n − 1.

Le nombre 15 fournit un contre-cas concret. Il est composé, mais avec la base 2, première avec 15, on obtient 2¹⁵ ≡ 8 modulo 15, et non 2. Le test échoue : 15 n’est pas un nombre de Carmichael. Pour décider si 15 est premier, il faut donc employer un véritable test de primalité, pas seulement lui attribuer ou lui refuser cette propriété.

Déterminons si 561 est un nombre de Carmichael. Les données sont sa décomposition 561 = 3 × 11 × 17 et la valeur 560 pour 561 − 1. Les trois facteurs premiers sont distincts.

1. Le nombre 561 est composé puisqu’il possède trois facteurs premiers.
2. Aucun facteur n’est répété : 561 ne contient donc aucun carré premier.
3. Pour p = 3, on a p − 1 = 2, qui divise 560.
4. Pour p = 11, on a p − 1 = 10, qui divise 560.
5. Pour p = 17, on a p − 1 = 16, qui divise 560.

Toutes les conditions du critère de Korselt sont satisfaites. Ainsi, 561 est un nombre de Carmichael : pour tout entier a premier avec 561, a⁵⁶¹ ≡ a modulo 561.

Un contrôle refaisable avec a = 2 utilise les trois facteurs. Les exposants 10 et 8 ramènent respectivement le calcul modulo 11 et modulo 17, tandis que la parité suffit modulo 3. On trouve 2⁵⁶¹ ≡ 2 pour chacun des modules 3, 11 et 17, donc modulo leur produit 561.

Dans un test de Fermat, on choisit une base et l’on contrôle une congruence. Si elle échoue, le nombre testé est composé. Si elle réussit, un nombre de Carmichael comme 561 montre que la primalité n’est pas encore acquise.

Pour certifier qu’un entier est premier, on préfère un test de primalité dont les garanties correspondent au besoin : probabilistes avec plusieurs contrôles indépendants, ou déterministes lorsqu’une preuve est requise. Le critère observable est le niveau de certitude attendu, pas la seule réussite au test de Fermat.

Pour étudier un entier composé déjà factorisé, le critère de Korselt évite de tester toutes les bases. On vérifie l’absence de facteur premier répété, puis que, pour chaque facteur premier p de n, p − 1 divise n − 1.

Nombre premier. Un nombre premier possède exactement deux diviseurs positifs, tandis qu’un nombre de Carmichael est composé. Ainsi, 561 = 3 × 11 × 17 tranche immédiatement malgré son comportement au test de Fermat.

Pseudopremier pour une base. Un entier composé peut satisfaire le test de Fermat pour une base particulière seulement. Un nombre de Carmichael le satisfait pour toute base première avec lui. Tester une seule base ne permet donc pas de distinguer les deux cas.

Fonction de Carmichael. Cette fonction arithmétique porte le même nom, mais elle associe à un entier un exposant lié aux inversibles modulo cet entier. La conjecture étudiée ici porte sur l’infinité d’une famille d’entiers composés.

Une base ne suffit pas. Observer aⁿ ≡ a modulo n pour une seule valeur de a signale seulement un pseudopremier possible pour cette base. Il faut vérifier toutes les bases premières avec n ou utiliser un critère équivalent.

Les bases non premières avec n demandent de la précision. La forme aⁿ⁻¹ ≡ 1 modulo n n’est équivalente à la définition que lorsque a est premier avec n. La forme aⁿ ≡ a modulo n reste, elle, valable pour tout entier a lorsque n est un nombre de Carmichael.

« Conjecture » est un nom historique. L’infinité n’est plus une question ouverte depuis la démonstration de 1994. Le seuil exact à partir duquel C(x) > x^2/7 est garanti n’est pas fourni par l’énoncé source ; la borne ne doit donc pas être appliquée à une petite valeur de x.

Le test de Fermat a une portée limitée. Les nombres de Carmichael peuvent le tromper, mais cela ne signifie pas qu’ils trompent tout test probabiliste. Face à une réussite, il faut recourir à un test plus robuste avant de conclure.

Les nombres de Carmichael présente plus largement cette famille d’entiers et le phénomène des composés qui imitent les nombres premiers.

Le petit théorème de Fermat donne la congruence dont les nombres de Carmichael révèlent la limite comme critère de primalité.

Un test de primalité replace le test de Fermat parmi les méthodes servant à décider si un entier est premier.