nombre de Carmichael

Prenez 561 et soumettez-le au critère de Fermat. Bien qu’il soit composé, ce nombre se comporte comme un nombre premier pour tout entier choisi sans facteur commun avec lui. Le test reçoit donc toujours la réponse attendue d’un nombre premier.

Ce faux-semblant explique le surnom de « menteur de Fermat ». Les nombres de Carmichael ne sont pourtant pas premiers : 561, par exemple, se factorise en 3 × 11 × 17.

Un nombre de Carmichael est un entier positif composé, noté n. Pour chaque entier a premier avec n, c’est-à-dire sans diviseur commun autre que 1, il vérifie $n\mid a^n-an\; \backslash mid\; a^n-a$. La même condition s’écrit $n\mid a^{n-1}-1n\; \backslash mid\; a^\{n-1\}-1$, puisque a est premier avec n.

Le petit théorème de Fermat garantit une propriété analogue lorsque n est premier. Un nombre de Carmichael montre que la réciproque est fausse : satisfaire ce critère ne suffit pas à établir la primalité. Il s’agit donc d’un pseudo-premier au sens de Fermat.

Le théorème de Korselt, formulé en 1899, caractérise complètement ces entiers. Il entraîne notamment qu’un nombre de Carmichael possède au moins trois facteurs premiers distincts. Carmichael a identifié le premier exemple en 1910. Les trois plus petits sont 561, 1105 et 1729.

Vérifions sur 561 pourquoi le critère de Fermat ne révèle pas sa nature composée. Les données sont 561 = 3 × 11 × 17 et 561 − 1 = 560. On choisit un entier a premier avec 561. Il n’est donc divisible ni par 3, ni par 11, ni par 17.

1. Pour le facteur premier 3, le petit théorème de Fermat donne $a^2\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}3)a^2\; \backslash equiv\; 1\; \backslash pmod\{3\}$. Or 560 = 2 × 280, donc $a^{560}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}3)a^\{560\}\; \backslash equiv\; 1\; \backslash pmod\{3\}$.

2. Pour 11, le même théorème donne $a^{10}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}11)a^\{10\}\; \backslash equiv\; 1\; \backslash pmod\{11\}$. Comme 560 = 10 × 56, le reste de a⁵⁶⁰ est encore 1 modulo 11.

3. Pour 17, on obtient $a^{16}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}17)a^\{16\}\; \backslash equiv\; 1\; \backslash pmod\{17\}$. Puisque 560 = 16 × 35, le reste de a⁵⁶⁰ vaut aussi 1 modulo 17.

Les trois facteurs 3, 11 et 17 sont distincts. Leur produit 561 divise donc a⁵⁶⁰ − 1. Ainsi, chaque entier a premier avec 561 passe le critère, alors que la factorisation prouve que 561 est composé.

Le contrôle se refait en vérifiant les trois divisions exactes : 560 ÷ 2 = 280, 560 ÷ 10 = 56 et 560 ÷ 16 = 35.

Dans un test de primalité fondé sur le petit théorème de Fermat, un échec prouve que le nombre testé est composé. En revanche, une réussite ne prouve pas qu’il est premier : un nombre de Carmichael réussit pour toutes les bases qui lui sont premières.

Pour décider si 561 est premier, la factorisation tranche immédiatement : 561 = 3 × 11 × 17. Le critère de Fermat indique seulement une propriété modulaire ; il ne remplace pas une preuve de primalité.

Le bon réflexe est donc de traiter une réussite au test de Fermat comme un filtre, puis d’employer un autre test de primalité ou une factorisation lorsque la conclusion doit être certaine.

Nombre premier. Un nombre premier n’a que 1 et lui-même comme diviseurs positifs. Un nombre de Carmichael est composé : 561 a les facteurs 3, 11 et 17, même s’il satisfait le critère de Fermat.

Pseudo-premier de Fermat pour une base donnée. Une seule congruence réussie concerne un choix précis de a. Pour être un nombre de Carmichael, l’entier composé doit réussir pour tout a premier avec lui.

Test de primalité. Le critère de Fermat est une condition nécessaire pour les nombres premiers, mais sa réussite n’est pas une certification. Le cas 561 suffit à séparer les deux idées.

La base doit être première avec le nombre. La définition ne porte pas sur un entier a partageant un facteur avec n. Avec 561, une base divisible par 3, 11 ou 17 sort de cette condition.

Une réussite isolée ne suffit pas. Vérifier la congruence pour a = 2 ne prouve pas que l’entier est un nombre de Carmichael. La propriété doit valoir pour chaque entier premier avec n.

La primalité est exclue par définition. Un entier premier satisfait le petit théorème de Fermat, mais ce n’est pas un nombre de Carmichael. Le nombre recherché doit être positif et composé.

Deux facteurs premiers distincts ne peuvent pas suffire. Le théorème de Korselt impose au moins trois facteurs premiers distincts. Le seuil est atteint par 561 = 3 × 11 × 17.

Le petit théorème de Fermat précise la propriété des nombres premiers dont les nombres de Carmichael imitent le résultat.

La fiche test de primalité replace le critère de Fermat parmi les méthodes qui cherchent à décider si un entier est premier.

L’arithmétique modulaire donne le langage des restes et des congruences utilisé dans la définition et le calcul sur 561.