Nombre de Carmichael

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des nombres, un nombre de Carmichael est un entier composé positif n qui vérifie la propriété \mathcal P suivante :

pour tout entier a premier avec n, n est un diviseur de an – a

ou, ce qui est équivalent :

pour tout entier a premier avec n, n est un diviseur de an – 1 – 1.

C'est donc un nombre pseudo-premier de Fermat en toute base première avec lui.

Il est remarquable que, d'une part, dans les définitions ci-dessus, on peut se restreindre aux a allant de 2 à n-1, et que d'autre part, on montre qu'un tel nombre n est un diviseur de an – a pour toute base a, et qu'il est donc faiblement pseudo premier en toute base.

Il n'a été montré qu'en 1994 qu'il en existe une infinité.

Tour d'horizon[modifier | modifier le code]

Le petit théorème de Fermat énonce que les nombres premiers ont la propriété \mathcal P. Sa réciproque est fausse, les nombres de Carmichael sont les nombres positifs qui satisfont à \mathcal P sans être premiers, ce sont des menteurs de Fermat ; l'existence de tels nombres pseudo-premiers absolus est ce qui empêche d'utiliser le test de primalité de Fermat pour prouver qu'un nombre est premier.

Plus les nombres deviennent grands et plus les nombres de Carmichael deviennent rares, la majorité d'entre eux rendent le test de primalité de Fermat largement inutile comparé aux autres tests de primalité comme le test de primalité de Solovay-Strassen. Par exemple, le 646e nombre de Carmichael vaut 993 905 641 et il existe 105 212 nombres de Carmichael entre 1 et 1015.

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

Théorème (Korselt, 1899[1]) — Un entier positif composé n est un nombre de Carmichael si et seulement si aucun carré de nombre premier ne divise n (on dit que n est quadratfrei (sans carré)) et pour chaque diviseur premier p de n, le nombre p − 1 divise n − 1. De plus, un tel n divise tous les an – a (même pour a non premier à 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 fut le premier à observer ces propriétés, mais il n'a pas pu trouver d'exemples de nombre de Carmichael[réf. nécessaire]. En 1909, Robert Daniel Carmichael trouva le plus petit de ces nombres, 561, et ceux-ci furent nommés en son honneur.

Ce nombre de Carmichael 561 peut être vérifié avec le théorème de Korselt. Effectivement, 561 = 3 · 11 · 17 n'est pas divisible par un carré de nombre premier, et 3 - 1 = 2, 11 - 1 = 10 et 17 - 1 = 16 sont tous trois des diviseurs de 560.

Les premiers nombres de Carmichael sont :

561 = 3 · 11 · 17
1 105 = 5 · 13 · 17
1 729 = 7 · 13 · 19
2 465 = 5 · 17 · 29
2 821 = 7 · 13 · 31
6 601 = 7 · 23 · 41
8 911 = 7 · 19 · 67

La suite des 33 premiers nombres de Carmichael en ordre croissant est donnée par la suite A002997 de l'OEIS, et la suite des 8241 premiers nombres de Carmichael (classés par ordre croissant et décomposés en leurs facteurs premiers) est donnée ici.

J. Chernick démontra un théorème en 1939[2] qui peut être utilisé pour construire un sous-ensemble de nombres de Carmichael. Le nombre (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 k décrit l'ensemble des entiers. Tout nombre de Chernick est aussi un nombre de Zeisel avec a=1 et b=6k.

En 1956, Paul Erdős a démontré[3] l'existence d'une constante K tel que le nombre C(n) de nombres de Carmichael inférieurs ou égaux à n est majoré par 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 n ≤ 10m :

m 4 6 8 10 12 14 16 18 20
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 a donné des arguments heuristiques en faveur de l'hypothèse selon laquelle pour tout ε > 0, C(n) > n1 – ε pour n assez grand. Son hypothèse entraînait la conjecture de l'existence d'une infinité de nombres de Carmichael.

Cette conjecture a été démontrée en 1994 par William Alford (en), Andrew Granville et Carl Pomerance, et même, plus précisément, C(n) > n2/7 pour n assez grand[4].

C(1021) = 20 138 200[5].

En 2013, il a été démontré qu'il existe une infinité de nombres de Carmichael dans toute suite arithmétique {an+b} où pgcd(a,b)=1 [6].

Propriétés[modifier | modifier le code]

Tout nombre de Carmichael est impair. En effet, pour tout entier composé pair n, (–1)n – (–1) = 2 n'est pas divisible par 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, n'est autre que 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 = 103 + 93 = 123 + 13). 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. Pour clôturer la séquence, le premier nombre de Carmichael 561 peut (comme n'importe quel entier naturel) s'écrire comme somme de puissances unaires d'entiers positifs de plus de façons que n'importe quel entier positif plus petit.

Démonstration du théorème de Korselt[modifier | modifier le code]

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

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

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

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

Un nombre de Carmichael ne peut être le produit de deux nombres premiers p et q, car alors chacun des deux nombres p – 1 et 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[modifier | modifier le code]

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é n est un nombre de Carmichael précisément lorsque la fonction nième puissance pn de l'anneau commutatif Zn des entiers modulo n dans lui-même est la fonction identité. L'identité est le seul Zn-endomorphisme d'algèbre sur Zn donc nous pouvons rétablir la définition en demandant que pn soit un endomorphisme d'algèbre de Zn. Comme ci-dessus, pn satisfait à la même propriétés quand n est premier.

La fonction nième puissance pn est aussi définie sur n'importe quel Zn-algèbre A. Un théorème énonce que n est premier si et seulement si toutes les fonctions telles que pn sont des endomorphismes d'algèbres.

Entre ces deux conditions se trouve la définition du nombre de Carmichael d'ordre m pour n'importe quel entier positif m comme n'importe quel nombre composé n tel que pn est un endomorphisme sur chaque Zn-algèbre qui peut être générée comme un Zn-module par m éléments. Les nombres de Carmichael d'ordre 1 sont simplement les nombres de Carmichael ordinaires.

Propriétés[modifier | modifier le code]

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

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

Notes et références[modifier | modifier le code]

(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. A. R. Korselt, « Problème chinois », L'intermédiaire des mathématiciens, vol. 6,‎ 1899, p. 142-143 (lire en ligne)
  2. (en) J. Chernick, « On Fermat's simple theorem », Bull. Amer. Math. Soc., vol. 45,‎ 1939, p. 269–274 (lire en ligne)
  3. (en) P. Erdős, « On pseudoprimes and Carmichael numbers », Publ. Math. Debrecen, vol. 4,‎ 1956, p. 201-206 (lire en ligne)
  4. (en) W. R. Alford, Andrew Granville et Carl Pomerance, « There are infinitely many Carmichael numbers », Ann. of Math., vol. 140, no 3,‎ 1994, p. 703–722 (lire en ligne)
  5. (en) Richard G. E. Pinch, The Carmichael numbers up to 10 to the 21, sur sa page personnelle
  6. Wright, Infinitely many Carmichael numbers in arithmetic progressions, Bull. London Math. Soc. 45 (2013) 943–952.
  7. a et b (en) Everett W. Howe, « Higher-order Carmichael numbers », dans Mathematics of Computation, vol. 69, 2000, p. 1711–1719 Texte en accès libre sur arXiv : math.NT/9812089.

Liens externes[modifier | modifier le code]