Ê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
Indicatrice de Carmichael
Résumé
vignette|upright=2|Fonction λ de Carmichael : λ(n) pour 1 ≤ n ≤ 1000 (avec les valeurs de la fonction φ d'Euler en comparaison)
La fonction indicatrice de Carmichael, ou indicateur de Carmichael ou encore fonction de Carmichael, notée λ, est définie sur les entiers naturels strictement positifs ; elle associe à un entier n le plus petit entier m vérifiant, pour tout entier a premier avec n, am ≡ 1 mod n. Elle est introduite par Robert Daniel Carmichael dans un article de 1910.
L'indicatrice de Carmichael λ entretient des rapports étroits avec la fonction indicatrice d'Euler φ, en particulier λ(n) divise φ(n). Les deux fonctions coïncident en 1, 2, 4, les puissances d'un nombre premier impair et leurs doubles, mais diffèrent partout ailleurs.
Les entiers a premiers avec n sont exactement ceux qui sont inversibles modulo n (par le théorème de Bachet-Bézout et sa réciproque). Donc si deux entiers m et k vérifient am ≡ 1 mod n et ak ≡ 1 mod n, le reste de la division euclidienne de l'un par l'autre également. La définition peut donc être reformulée :
λ(n) est l'unique entier tel que
pour tout entier a premier avec n, aλ(n) ≡ 1 mod n
si pour tout entier a premier avec n, am ≡ 1 mod n, alors λ(n) divise m.
On déduit alors du théorème d'Euler que :
λ(n) divise φ(n).
La définition a également pour conséquence, par le théorème des restes chinois que :
si m et n sont premiers entre eux, alors λ(m×n) est le plus petit commun multiple de λ(m) et λ(n).
La définition peut être reformulée en utilisant la théorie des groupes. Un entier a premier avec n est exactement un entier dont la classe modulo n est un élément inversible de l'anneau Z/nZ, c'est-à-dire un élément du groupe multiplicatif (Z/nZ). Par définition, le plus petit entier m vérifiant αm = 1 pour tout élément α d'un groupe est appelé exposant de ce groupe, et donc :
λ(n) est l'exposant du groupe multiplicatif (Z/nZ) des éléments inversibles de l'anneau Z/nZ.
Une autre caractérisation de l'exposant donne
λ(n) est le plus petit commun multiple des ordres des éléments de (Z/nZ)*.
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.