Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Nombre de Carmichael
Résumé
vignette|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, est un nombre composé 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 a premier avec n, n est un diviseur de a – 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 a de 2 à n – 1 dans cette définition).
D'après le lemme de Gauss, cette propriété équivaut à que pour tout entier a premier avec n, n est un diviseur de a – a. Mais l'étude des nombres de Carmichael permet de montrer que ce sont aussi les nombres composés vérifiant :
pour tout entier a, n est un diviseur de a – a,
ce qui correspond, pour les nombres premiers, à un autre énoncé du petit théorème de Fermat.
En 1994, Alford, Granville et Pomerance démontrent qu'il existe une infinité de nombres de Carmichael.
Le petit théorème de Fermat énonce que les nombres premiers ont la propriété que pour tout entier a, n est un diviseur de a – 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 absolus, le test de primalité de Fermat échoue toujours à montrer qu'ils sont composés, quel que soit le choix du témoin 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 de Carmichael vaut 993 905 641 et il existe 105 212 nombres de Carmichael entre 1 et 10.
Une caractérisation des nombres de Carmichael est donnée par le théorème de Korselt :
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.