Nombre de Carmichael

Robert Daniel Carmichael

En théorie des nombres, un nombre de Carmichael (portant le nom du mathématicien américain Robert Daniel Carmichael), ou nombre absolument pseudo-premier, ou encore nombre pseudo-premier absolu[1], est un nombre composé ${\displaystyle n}$ qui vérifie la propriété suivante, satisfaite par tous les nombres premiers d'après le petit théorème de Fermat :

pour tout entier ${\displaystyle a}$ premier avec ${\displaystyle n}$, ${\displaystyle n}$ est un diviseur de ${\displaystyle a^{n-1}-1}$.

C'est donc un nombre pseudo-premier de Fermat en toute base première avec lui (on peut d'ailleurs se restreindre aux entiers ${\displaystyle a}$ de 2 à ${\displaystyle n-1}$ dans cette définition).

D'après le lemme de Gauss, cette propriété équivaut à que pour tout entier ${\displaystyle a}$ premier avec ${\displaystyle n}$, ${\displaystyle n}$ soit un diviseur de ${\displaystyle a^{n}-a}$. Mais l'étude des nombres de Carmichael permet de montrer que ce sont aussi les nombres composés vérifiant :

pour tout entier ${\displaystyle a}$, ${\displaystyle n}$ est un diviseur de ${\displaystyle a^{n}-a}$,

ce qui correspond, pour les nombres premiers ${\displaystyle n}$, à un autre énoncé du petit théorème de Fermat.

Le plus petit nombre de Carmichael est 561, et en 1994, Alford, Granville et Pomerance démontrent qu'il existe une infinité de nombres de Carmichael[2]; voir la suite A002997 de l'OEIS.

Contexte

Le petit théorème de Fermat énonce que les nombres premiers ont la propriété que pour tout entier ${\displaystyle a}$, ${\displaystyle n}$ est un diviseur de ${\displaystyle a^{n}-a}$. Sa réciproque est fausse et les nombres de Carmichael sont les nombres positifs qui satisfont cette propriété sans être premiers : ce sont des menteurs de Fermat. Pour de tels nombres, dits pseudo-premiers, le test de primalité de Fermat échoue toujours à montrer qu'ils sont composés[3], quel que soit le choix du témoin ${\displaystyle a}$, ce qui ne peut pas arriver pour d'autres tests de primalité comme le test de primalité de Solovay-Strassen ou le test de primalité de Miller-Rabin.

Cependant, plus les nombres deviennent grands, plus les nombres de Carmichael deviennent rares, ce qui fait que le test de primalité de Fermat reste probabilistiquement relativement pertinent. Par exemple, le 646^e nombre de Carmichael vaut 993 905 641 et il existe 105 212 nombres de Carmichael entre 1 et 10^15.

Appellation

L'appellation "nombre absolument pseudo-premier" (ou "nombre pseudo-premier absolu") devrait être précisée par : "pour le test de Fermat", car il existe d'autres nombres absolument pseudo-premiers, par exemple les nombres absolument pseudo-premiers d'Euler.

Caractérisation

Une caractérisation des nombres de Carmichael est donnée par le théorème de Korselt :

Théorème — Un entier positif composé ${\displaystyle n}$ est un nombre de Carmichael si et seulement si aucun carré de nombre premier ne divise ${\displaystyle n}$ (on dit que ${\displaystyle n}$ est sans facteur carré) et pour chaque diviseur premier ${\displaystyle p}$ de ${\displaystyle n}$, le nombre ${\displaystyle p-1}$ divise ${\displaystyle n-1}$. De plus, un tel ${\displaystyle n}$ divise tous les ${\displaystyle a^{n}-a}$ (même pour ${\displaystyle a}$ non premier avec ${\displaystyle n}$).

Il découle de ce théorème que tous les nombres de Carmichael sont des produits d'au moins trois nombres premiers différents.

Korselt mentionne cette caractérisation (sans l'accompagner d'exemples) dans une courte réponse à une question de Gaston Tarry[4], à propos, dirions nous aujourd'hui, de l'existence de nombres pseudo-premiers en base 2, caractérisation passée semble-t-il alors inaperçue[5]. En 1910, Robert Daniel Carmichael énonce indépendamment[5] et démontre un critère voisin, dont la formulation utilise sa fonction indicatrice, et donne 4 de ces nombres dont 561 et 1105, les deux plus petits d'entre eux[6], résultats qu'il reprend et développe dans un article paru en 1912[7]. C'est à la suite de ces articles que ces nombres sont appelés nombres de Carmichael[5].

On vérifie facilement que 561 = 3 × 11 × 17 est un nombre de Carmichael à l'aide du théorème de Korselt : la décomposition en facteurs premiers ne comporte pas de facteur multiple et 3 – 1 = 2, 11 – 1 = 10 et 17 – 1 = 16 sont tous trois des diviseurs de 560.

Les sept premiers[8] nombres de Carmichael sont :

561 = 3 × 11 × 17

1105 = 5 × 13 × 17

1729 = 7 × 13 × 19

2465 = 5 × 17 × 29

2821 = 7 × 13 × 31

6601 = 7 × 23 × 41

8911 = 7 × 19 × 67.

J. Chernick démontre un théorème en 1939[9] qui peut être utilisé pour construire un sous-ensemble de nombres de Carmichael. Le nombre ${\displaystyle (6k+1)(12k+1)(18k+1)}$ est un nombre de Carmichael si ses trois facteurs sont tous premiers. On ne sait pas si cette formule, ou d'autres similaires, engendre une infinité de nombres de Carmichael lorsque ${\displaystyle k}$ décrit l'ensemble des entiers. Tout nombre de Chernick est aussi un nombre de Zeisel avec ${\displaystyle a=1}$ et ${\displaystyle b=6k}$.

Nombre de nombres de Carmichael

En 1956, Paul Erdős démontre[10] l'existence d'une constante ${\displaystyle K}$ telle que le nombre ${\displaystyle C(n)}$ de nombres de Carmichael inférieurs ou égaux à ${\displaystyle n}$ est majoré par ${\displaystyle n\exp \left({\frac {-K\ln n\ln \ln \ln n}{\ln \ln n}}\right)}$.

Le tableau suivant donne les valeurs minimales approximatives de cette constante, pour ${\displaystyle n\leqslant 10^{m}}$:

${\displaystyle m}$	4	6	8	10	12	14	16	18	20
${\displaystyle K}$	2,19547	1,97946	1,90495	1,86870	1,86377	1,86293	1,86406	1,86522	1,86598

Dans le même article, Erdős donne des arguments heuristiques en faveur de l'hypothèse selon laquelle pour tout ${\displaystyle \varepsilon >0,C(n)>n^{1-\varepsilon }}$pour ${\displaystyle n}$ assez grand, hypothèse qui a pour conséquence l'existence d'une infinité de nombres de Carmichael conjecturée par celui-ci.

La conjecture de Carmichael est démontrée en 1994 par William Alford (en), Andrew Granville et Carl Pomerance[2], qui démontrent même plus précisément que ${\displaystyle C(n)>n^{2/7}}$ pour ${\displaystyle n}$ assez grand[11].

En 2013, Thomas Wright démontre qu'il existe une infinité de nombres de Carmichael dans toute suite arithmétique ${\displaystyle (an+b)}$ où ${\displaystyle {\text{pgcd}}(a,b)=1}$[12].

Propriétés

Tout nombre de Carmichael est impair. En effet, pour tout entier composé pair ${\displaystyle n}$, ${\displaystyle (-1)^{n}-(-1)=2}$ n'est pas divisible par ${\displaystyle n}$.

Les nombres de Carmichael ont au moins trois facteurs premiers.

Les premiers nombres de Carmichael avec respectivement au moins k = 3, 4, 5,... facteurs premiers sont (suite A006931 de l'OEIS) :

k
3	561 = 3 · 11 · 17
4	41041 = 7 · 11 · 13 · 41
5	825265 = 5 · 7 · 17 · 19 · 73
6	321197185 = 5 · 19 · 23 · 29 · 37 · 137
7	5394826801 = 7 · 13 · 17 · 23 · 31 · 67 · 73
8	232250619601 = 7 · 11 · 13 · 17 · 31 · 37 · 73 · 163
9	9746347772161 = 7 · 11 · 13 · 17 · 19 · 31 · 37 · 41 · 641

Les premiers nombres de Carmichael avec quatre facteurs premiers sont (suite A074379 de l'OEIS) :

i
1	41041 = 7 · 11 · 13 · 41
2	62745 = 3 · 5 · 47 · 89
3	63973 = 7 · 13 · 19 · 37
4	75361 = 11 · 13 · 17 · 31
5	101101 = 7 · 11 · 13 · 101
6	126217 = 7 · 13 · 19 · 73
7	172081 = 7 · 13 · 31 · 61
8	188461 = 7 · 13 · 19 · 109
9	278545 = 5 · 17 · 29 · 113
10	340561 = 13 · 17 · 23 · 67

Une coïncidence amusante est la suivante : le troisième nombre de Carmichael et premier nombre de Chernick , 1729, est le nombre de Hardy-Ramanujan, c'est-à-dire le plus petit entier positif qui peut être écrit de deux façons différentes comme la somme de deux cubes (1729 = 7 × 13 × 19 = 10^3 + 9^3 = 12^3 + 1^3). Dans la même veine, le deuxième nombre de Carmichael, 1105, peut être écrit comme somme de deux carrés de plus de façons que n'importe quel entier qui lui est inférieur.

Le nombre 101 101 est le plus petit nombre de Carmichael palindrome. L'astéroïde numéroté 101 101 a été baptisé du nom de Carmichael[13].

Démonstration du théorème de Korselt

• Soient ${\displaystyle n}$ un nombre de Carmichael (donc impair), ${\displaystyle p}$ l'un de ses facteurs premiers, ${\displaystyle r}$ l'exposant de ${\displaystyle p}$ dans ${\displaystyle n}$, et ${\displaystyle a}$ un entier à la fois générateur du groupe cyclique des unités de ℤ/p^rℤ et premier avec ${\displaystyle n}$ (il en existe, d'après le théorème chinois). Alors ${\displaystyle a^{n-1}-1}$ est divisible par ${\displaystyle n}$ donc par ${\displaystyle p^{r}}$, donc ${\displaystyle n-1}$ est un multiple de l'ordre multiplicatif de ${\displaystyle a}$ modulo ${\displaystyle p^{r}}$, c'est-à-dire de ${\displaystyle p^{r-1}(p-1)}$. Il en résulte que ${\displaystyle r=1}$ (puisque ${\displaystyle p^{r-1}}$ divise ${\displaystyle n-1}$ et ${\displaystyle n}$) et que ${\displaystyle p-1}$ divise ${\displaystyle n-1}$.
• Réciproquement, supposons que ${\displaystyle n}$ soit un produit de nombres premiers distincts p₁, p₂, … , p_k et que les nombres p₁ – 1, p₂ – 1, … divisent tous ${\displaystyle n-1}$. Alors, pour tout entier ${\displaystyle a}$ et tout i, on a ${\displaystyle n\equiv 1\mod {(p_{i}-1)}}$ et donc (d'après le petit théorème de Fermat) ${\displaystyle a^{n}\equiv a\mod {(p_{i}-1)}}$. Le nombre ${\displaystyle a^{n}}$ est congru à ${\displaystyle a}$ modulo chacun des ${\displaystyle p_{i}}$, donc aussi modulo leur produit ${\displaystyle n}$. C'est vrai pour tout entier ${\displaystyle a}$ (même non premier avec ${\displaystyle n}$), en particulier ${\displaystyle n}$ est un nombre de Carmichael dès que ${\displaystyle k>1}$.

Cela achève la démonstration du théorème de Korselt.

Conséquences du théorème de Korselt :

Si ${\displaystyle p}$ est un facteur premier d'un nombre de Carmichael ${\displaystyle n}$ alors, modulo ${\displaystyle p-1}$, on a n/p = (n/p)1 ≡ (n/p)p = n ≡ 1. Autrement dit, si ${\displaystyle p}$ est un facteur premier d'un nombre de Carmichael, alors le produit des autres facteurs premiers est congru à 1 modulo ${\displaystyle p-1}$.

Un nombre de Carmichael ne peut être le produit de deux nombres premiers ${\displaystyle p}$ et ${\displaystyle q}$, car alors chacun des deux nombres ${\displaystyle p-1}$et ${\displaystyle q-1}$ diviserait l'autre et ils seraient égaux.

Tout nombre de Carmichael est donc le produit d'au moins trois nombres premiers (impairs) distincts.

Nombres de Carmichael d'ordre supérieur

Les nombres de Carmichael peuvent être généralisés en utilisant les concepts de l'algèbre générale.

La définition ci-dessus énonce qu'un entier composé ${\displaystyle n}$ est un nombre de Carmichael précisément lorsque la fonction puissance ${\displaystyle n}$-ième ${\displaystyle p_{n}}$ de l'anneau commutatif ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ des entiers modulo ${\displaystyle n}$ dans lui-même est la fonction identité. L'identité est le seul ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$-endomorphisme d'algèbre sur ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ donc nous pouvons retrouver la même définition en demandant que ${\displaystyle p_{n}}$ soit un endomorphisme d'algèbre de ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$. Comme ci-dessus, ${\displaystyle p_{n}}$ satisfait à cette propriété quand ${\displaystyle n}$ est premier.

La fonction puissance ${\displaystyle n}$-ième ${\displaystyle p_{n}}$ peut se définir sur n'importe quelle ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$-algèbre A. Un théorème énonce que ${\displaystyle n}$ est premier si et seulement si toutes les fonctions ${\displaystyle p_{n}}$ sont des endomorphismes d'algèbres.

Entre ces deux conditions se trouve la définition des nombres de Carmichael d'ordre ${\displaystyle m}$ pour un entier positif ${\displaystyle m}$ comme étant les nombres composés ${\displaystyle n}$ tel que ${\displaystyle p_{n}}$ est un endomorphisme de chaque ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$-algèbre pouvant être générée comme ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$-module par ${\displaystyle m}$ éléments. Les nombres de Carmichael d'ordre 1 sont alors les nombres de Carmichael ordinaires.

Propriétés

Le critère de Korselt peut être généralisé aux nombres de Carmichael d'ordre supérieur[14].

Un argument heuristique[14] semble suggérer qu'il existe une infinité de nombres de Carmichael d'ordre ${\displaystyle m}$, quel que soit ${\displaystyle m}$. Néanmoins, on ne connaît aucun nombre de Carmichael d'ordre 3 ou plus.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Carmichael number » (voir la liste des auteurs).

1. Michel BALAZARD, Abdelhakim SMATI, « Travaux de Pomerance sur la fonction phi d'Euler », publications mathématiques d'Orsay,‎ 1989-1990, p. 9 (lire en ligne)
2. (en) William Alford, Andrew Granville et Carl Pomerance, « There are infinitely many Carmichael numbers », Ann. of Math., vol. 140, n^o 3,‎ 1994, p. 703-722 (lire en ligne).
3. Plus exactement, il s'agit de la variante testant la divisibilité de ${\displaystyle a^{n}-a}$ par ${\displaystyle n}$, car le test de primalité de Fermat réussit pour tous les diviseurs de ${\displaystyle n}$. Ainsi, ${\displaystyle 2^{8-1}-1}$ n'est pas divisible par 8, alors que ${\displaystyle 2^{8}-8}$ est bien divisible par 8.
4. A. R. Korselt, « Problème chinois [réponse à une question de G. Tarry] », L'Intermédiaire des mathématiciens, vol. 6,‎ 1899, p. 143 (lire en ligne), lire également (volumes 5 et 6 complets). La question est posée par Tarry dans le même périodique en 1988, voir volume 5 p 266, les réponses, parmi lesquelles celle de Korselt, vont de la page 142 à la page 144 du volume 6.
5. Ribenboim 1996, p. 118.
6. (en) R. D. Carmichael, « Note on a new number theory function », Bull. Amer. Math. Soc., vol. 16, n^o 5,‎ 1910, p. 232–238 (DOI 10.1090/s0002-9904-1910-01892-9, lire en ligne), p. 237-238.
7. (en) Carmichael, R. D., « On composite numbers P which satisfy the Fermat congruence a^P-1 ≡ 1 mod P », Amer. Math. Monthly, vol. 19, n^o 2,‎ 1912, p. 22–27 (DOI 10.2307/2972687).
8. Pour les 10 000 premiers, voir ce lien de la suite A002997 de l'OEIS. La décomposition en facteurs premiers des 8 241 premiers est donnée ici.
9. (en) J. Chernick, « On Fermat's simple theorem », Bull. Amer. Math. Soc., vol. 45,‎ 1939, p. 269-274 (lire en ligne).
10. (en) P. Erdős, « On pseudoprimes and Carmichael numbers », Publ. Math. Debrecen, vol. 4,‎ 1956, p. 201-206 (lire en ligne).
11. Une expérimentation numérique donne C(10^21) = 20 138 200 ((en) Richard G. E. Pinch, The Carmichael numbers up to 10 to the 21, sur sa page personnelle), nettement supérieur à 10^6.
12. (en) Thomas Wright, « Infinitely many Carmichael numbers in arithmetic progressions », Bull. London Math. Soc., vol. 45, 2013, p. 943-952 « 1212.5850 », texte en accès libre, sur arXiv..
13. « (101101) Carmichael = 1998 RO₄₁ », WGSBN Bulletin, vol. 4, n^o 13,‎ 23 septembre 2024, p. 19 (lire en ligne).
14. (en) Everett W. Howe, « Higher-order Carmichael numbers », Math. Comp., vol. 69, 2000, p. 1711-1719 « math.NT/9812089 », texte en accès libre, sur arXiv..

Bibliographie

(en) Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, 541 p. (ISBN 0-387-94457-5), chap. IX

Voir aussi

Article connexe

Nombre de Knödel (en)

Liens externes

• (en) The Dullness of 1729 sur mathpages.com
• (en) Richard Guy, Unsolved Problems in Number Theory, 3^e éd., Springer Verlag, 2004, section A13
• (en) G. Ander Steele, « Carmichael numbers in number rings », J. Number Theor., vol. 128, n^o 4,‎ 2008, p. 910-917 (DOI 10.1016/j.jnt.2007.08.009, lire en ligne)