vignette|upright=2|Fonction de Carmichael : pour (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, . 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 divise . Les deux fonctions coïncident en 1, 2, 4, les puissances d'un nombre premier impair et leurs doubles, mais diffèrent partout ailleurs.

Définitions et première propriétés Les entiers 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 et , le reste de la division euclidienne de l'un par l'autre également. La définition peut donc être reformulée. : est l'unique entier tel que pour tout entier premier avec n, si pour tout entier premier avec n, , alors divise . On déduit alors du théorème d'Euler que : divise . 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 est le plus petit commun multiple de et . La définition peut être reformulée en utilisant la théorie des groupes. Un entier premier avec n est exactement un entier dont la classe modulo n est un élément inversible de l'anneau ℤ/nℤ, c'est-à-dire un élément du groupe multiplicatif (ℤ/nℤ)*. Par définition, le plus petit entier m vérifiant pour tout élément α d'un groupe est appelé exposant de ce groupe, et donc : est l'exposant du groupe multiplicatif (ℤ/nℤ)* des éléments inversibles de l'anneau ℤ/nℤ. Une autre caractérisation de l'exposant donne est le plus petit commun multiple des ordres des éléments de (ℤ/nℤ)*. On retrouve ainsi que divise qui est le cardinal, ou ordre, du groupe (ℤ/nℤ)* et donc un multiple commun des ordres de ses éléments (par le théorème de Lagrange).

Dans un groupe commutatif fini, comme (ℤ/nℤ)*, il existe un élément d'ordre l'exposant, c'est-à-dire que : il existe un élément de (ℤ/nℤ)* d'ordre . On en déduit immédiatement que : si et seulement si le groupe (ℤ/nℤ)* est un groupe cyclique. Quand p est premier, ℤ/pℤ est un corps fini (premier), et son groupe multiplicatif (ℤ/pℤ)* est alors cyclique. Donc : si p est premier, .

Exemples On n'a pas toujours : le groupe multiplicatif (ℤ/8ℤ)* est le groupe de Klein, d'ordre 4 et d'exposant 2, on a donc mais .

Il n'y a pas que les nombres premiers pour lesquels les fonctions φ et λ prennent la même valeur : on vérifie que (ℤ/4ℤ)* et (ℤ/6ℤ)* sont d'ordre 2, donc et , (ℤ/9ℤ)* est d'ordre , et 2 est un élément d'ordre 6 de (ℤ/9ℤ)* donc (les cas où sont précisés au paragraphe suivant).

La suite oeis:A002322 donne les premières valeurs de la fonction λ de Carmichael (et en propose d'autres dans les références). Les 36 premières valeurs de la fonction sont données dans le tableau ci-dessous, avec celles de l'indicatrice d'Euler correspondantes.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 1 1 2 2 4 2 6 2 6 4 10 2 12 6 4 4 16 6 18 4 6 10 22 2 20 12 18 6 28 4 30 8 10 16 12 6 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18 8 12 10 22 8 20 12 18 12 28 8 30 16 20 16 24 12

Calcul de λ(n) On sait calculer connaissant et quand m et n sont premiers entre eux. On pourra donc calculer à partir de la décomposition en facteurs premiers de n, si on sait calculer pour p un nombre premier, ce que l'on obtient en étudiant les groupes multiplicatifs correspondant : si p est un nombre premier impair, et r ≥ 1 un entier, alors le groupe multiplicatif (ℤ/pr ℤ)* est le groupe cyclique d'ordre ; si r ≥ 2, le groupe multiplicatif (ℤ/2r ℤ)*, est un groupe de cardinal , produit d'un groupe d'ordre 2 et d'un groupe cyclique d'ordre 2r – 2, soit, si r > 2, un groupe d'exposant , si r = 2 le groupe est de cardinal et d'exposant 2.

On obtient alors une caractérisation plus calculatoire de la fonction indicatrice de Carmichael (prise d'ailleurs parfois pour définition, en particulier dans l'article original de Carmichael.).

La fonction indicatrice de Carmichael prend la même valeur que la fonction indicatrice d'Euler en si et seulement si le groupe (ℤ/nℤ)* est cyclique, c'est-à-dire si et seulement si :

ou ; ou , une puissance non nulle (r > 0) d'un entier premier impair p ou le double d'une telle puissance ; (la suite oeis:A034380 énumère les premières valeurs du quotient , et propose d'autres données en références).

Autres propriétés On déduit, soit de la définition, soit de la forme plus explicite donnée par le théorème, que : si divise , alors divise ; en particulier : si est divisible par premier, alors est divisible par ; si , alors est un nombre pair (conséquence du précédent) ; si est divisible par où est premier, alors est divisible par . Quand est un nombre sans facteur carré, c'est-à-dire que est le produit de nombres premiers distincts :

pour tout entier , .

Nombres de Carmichael

Les nombres de Carmichael sont des nombres entiers naturels qui ne sont pas premiers mais qui vérifient pourtant la conclusion du petit théorème de Fermat, soit : pour tout entier premier avec n, . Carmichael les étudie dans le même article où il introduit sa fonction indicatrice et donne en particulier cette caractérisation., qui suit immédiatement de la définition adoptée plus haut : un nombre qui n'est pas premier est de Carmichael si et seulement si divise . Par conséquent : un nombre de Carmichael est forcément impair, car est divisible par pair (on a , et voir section précédente) ; un nombre de Carmichael est premier avec , donc sans facteur carré (voir section précédente), soit produit de nombres premiers tous distincts. En tirant parti de ces propriétés, et de l'expression dans ce cas de (voir section précédente), la caractérisation de Carmichael devient :

Ce résultat, démontré dans l'article de Carmichaël., est parfois appelé théorème de Korselt (voir l'article détaillé nombre de Carmichael).

Notes et références

Bibliographie

(p 90-94).

Catégorie:Arithmétique