Nombre de Carmichaël
Un article de Wikipédia, l'encyclopédie libre.
En théorie des nombres, un nombre de Carmichaël est un entier composé positif n qui vérifie la propriété 
suivante :
- pour tout entier a, on a la congruence
(voir arithmétique modulaire).
Sommaire |
[modifier] Tour d'horizon
D'après le petit théorème de Fermat, tous les nombres premiers vérifient la propriété . Dans ce sens, les nombres de Carmichaël sont similaires aux nombres premiers et sont ainsi appelés pseudopremiers. Les nombres de Carmichaël sont aussi appelés quelquefois pseudopremiers absolus.
Les nombres de Carmichaël sont importants car ils mettent en échec le test de primalité de Fermat ; ainsi, ce sont des menteurs de Fermat. Si les nombres de Carmichaël n'existaient pas, ce test de primalité pourrait toujours être utilisé pour prouver qu'un nombre est composé.
Plus les nombres deviennent grands et plus les nombres de Carmichaël 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 646-ème nombre de Carmichaël vaut 993 905 641 et il existe 105 212 nombres de Carmichaël entre 1 et 1015.
Une définition alternative et équivalente des nombres de Carmichaël est donnée par le théorème de Korselt en 1899.
Théorème (Korselt 1899) : Un entier positif composé n est un nombre de Carmichaël si et seulement si aucun carré de nombre premier ne divise n (on dit que n est quadratfrei) et pour chaque diviseur premier p de n, le nombre p − 1 divise n − 1.
Il découle de ce théorème que tous les nombres de Carmichaël sont des produits d'au moins trois nombres premiers impairs différents.
Korselt fut le premier à observer ces propriétés, mais il n'a pas pu trouver d'exemples de nombre de Carmichaël. En 1910, Robert Daniel Carmichaël trouva le plus petit de ces nombres, 561, et ceux-ci furent nommés en son honneur.
Ce nombre de Carmichaël 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 Carmichaël 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 Carmichaël en ordre croissant est donnée par la suite n°A002997 de l'Encyclopédie électronique des suites entières (OEIS), et la suite des 19 279 premiers nombres de Carmichaël (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 qui peut être utilisé pour construire un sous-ensemble de nombres de Carmichaël. Le nombre (6k + 1)(12k + 1)(18k + 1) est un nombre de Carmichaël si ses trois facteurs sont tous premiers.
Paul Erdős soutint de manière heuristique qu'il devrait y exister une infinité de nombres de Carmichaël. Cette conjecture a été démontrée en 1994 par William Alford, Andrew Granville et Carl Pomerance.
Il a aussi été montré que pour un n suffisamment grand, il existe au moins n2/7 nombres de Carmichaël compris entre 1 et n.
[modifier] Propriétés
Les nombres de Carmichaël ont au moins trois facteurs premiers.
Les premiers nombres de Carmichaël 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 Carmichaël 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 Carmichaël, 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 = 103 + 93 = 123 + 13). Dans la même veine, le deuxième nombre de Carmichaël, 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 Carmichaël 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.
[modifier] Démonstration du théorème de Korselt
Soit p un nombre premier qui divise un nombre de Carmichaël n. On a (p+1)n=1+np+Cn2p2+...≡1 (mod p2). D'autre part (p+1)n≡p+1 (mod n). Si p2 divisait n, on aurait 1≡(p+1)n≡p+1 (mod p2) ce qui est impossible. Cela montre que le carré de p ne divise pas n.
Le groupe Zp* est un groupe cyclique d'ordre p-1. Cela signifie que l'on peut trouver un entier a tel que la suite des (ak mod p) est périodique de période p-1 et les p-1 termes d'une période sont tous différents et contiennent tous les entiers de 1 à p-1. De plus an est congru à a modulo n et donc aussi modulo p. Les deux termes an mod p et a1 mod p sont égaux. Donc n-1 est un multiple de p-1.
Réciproquement, supposons que n soit un produit de nombres premiers tous distincts, p1, p2, ... pk et que les nombres p1-1, p2-1, ... divisent tous n-1. Alors pour tout entier a et tout pi on a n≡1 (mod pi-1) et donc a≡api ≡a2pi-1 ≡a3pi-2≡...≡an (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, donc n est un nombre de Carmichaël.
Ceci achève la démonstration du théorème de Korselt.
Conséquences du théorème de Korselt :
Soit n un nombre de Carmichaël. Il est divisible par plusieurs nombres premiers disctints, donc l'un d'eux au moins est différent de deux. Appelons p ce diviseur premier impair de n. Puisque p-1 est pair, son multiple n-1 l'est aussi. Cela montre que tout nombre de Carmichaël est impair.
Si p est un facteur premier d'un nombre de Carmichaël n, alors modulo p-1 on a p≡1≡n et donc 1≡(n/p)p≡(n/p)1=n/p. Autrement dit, si p est un facteur premier d'un nombre de Carmichaël, alors le produit des autres facteurs premiers est congru à 1 modulo p-1.
Un nombre de Carmichaël 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 Carmichaël est donc le produit d'au moins trois nombres premiers impairs distincts.
[modifier] Ordres plus élevés des nombres de Carmichaël
Les nombres de Carmichaël 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 Carmichaël précisément lorsque la fonction nième puissance pn de l'anneau 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 Carmichaël 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 Carmichaël d'ordre 1 sont simplement les nombres de Carmichaël ordinaires.
[modifier] Propriétés
Le critère de Korselt peut être généralisé aux nombres de Carmichaël d'ordres élevés, voir l'article de Howe ci-dessous.
Un argument heuristique, donné dans le même article, semble suggérer qu'il existe une infinité de nombres de Carmichaël d'ordre m, quel que soit m. Néanmoins, aucun nombre de Carmichaël unique d'ordre 3 ou au-dessus n'est connu.
[modifier] Références
- Chernick, J. (1935). On Fermat's simple theorem. Bull. Amer. Math. Soc. 45, 269–274.
- Howe, Everett W. (2000). Higher-order Carmichael numbers. Mathematics of Computation 69, 1711–1719. (online version)
