Page d'accueil
encyclopedie-enligne.com en page d'accueil| Page d'accueil |
encyclopedie-enligne.com en page d'accueil |
|||||
| Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées | ||||||
En théorie des nombres, un nombre de
Carmichaël est un entier composé positif n qui vérifie la propriété 
suivante :
(voir arithmétique modulaire).
| Sommaire |
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, 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 et impair 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 premiers p de n, on a que p − 1 divises n − 1.
Il découle de ce théorème que tous les nombres de Carmichaël sont impairs.
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 :
La suite des nombres de Carmichaël en ordre croissant est la suite n°A002997 de l'Encyclopédie électronique des suites entières (OEIS).
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.
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.
Les nombres de Carmichaël peuvent être généralisés en utilisant les concepts de l'algèbre abstraite.
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.
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.
