Ok

En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Ces derniers assurent le bon fonctionnement de nos services. En savoir plus.

11/12/2010

L'indicatrice de Carmichael

L'indicatrice de Carmichael

Définition Soit $ n$ un entier $ geq 2$. On définit $ lambda(n)$ comme le maximum des ordres des éléments du groupe $ ({mbox{bf Z}}/n{mbox{bf Z}})^*$. On appelle indicatrice de Carmichaell'expression $ lambda(n)$.

Exemple 55   Si $ p$ est premier, on a $ lambda(p)=phi(p)=p-1$ car le groupe $ ({mbox{bf Z}}/p{mbox{bf Z}})^*$ est cyclique d'ordre $ p-1$.

Lemme [Théorème de Carmichael] On a $ a^{lambda(n)}equiv 1; (n)$ pour tout entier $ a$ premier à $ n$. Réciproquement, si $ m$ vérifie $ a^mequiv 1;(n)$ pour tout entier $ a$ premier à $ n$, alors $ m$ est multiple de $ lambda(n)$.


Démonstration. Soit $ ain({mbox{bf Z}}/n{mbox{bf Z}})^*$ un élément d'ordre $ u=lambda(n)$ et $ bin({mbox{bf Z}}/n{mbox{bf Z}})^*$ un élément d'ordre $ v$. Nous allons montrer que $ ({mbox{bf Z}}/n{mbox{bf Z}})^*$ contient un élément dont l'ordre est PPCM $ (u,v)$. Il s'ensuivra que $ lambda(n)=$PPCM $ (u,v)$ et donc que $ v$ divise $ lambda(n)$.

Pour cela, écrivons PPCM $ (u,v)=u'v'$, où $ u'$ divise $ u$$ v'$ divise $ v$ et $ u'$$ v'$ sont premiers entre eux. Alors $ a^{u/u'}$ est d'ordre $ u'$$ b^{v/v'}$ est d'ordre $ v'$ et donc leur produit est d'ordre $ u'v'=$PPCM $ (u,v)$ d'après le lemme [*].

La deuxième affirmation est claire.$ surd$

Lemme

a)
On a $ lambda(2)=1$$ lambda(4)=2$ et $ lambda(2^k)=2^{k-2}$ pour tout $ kgeq 3$.
b)
Si $ p$ est un nombre premier impair, on a $ lambda(p^k)= phi(p^k)= (p-1)p^{k-1}$.
c)
Si $ n=rs$ où $ r$ et $ s$ sont premiers entre eux, on a $ lambda(n)=$PPCM $ (lambda(r),lambda(s))$.
Remarque 56   Ce lemme permet de calculer l'indicatrice de Carmichael de tout nombre dont on connaît la décomposition en facteurs premiers. Par exemple, on a
$displaystyle lambda(561)= lambda(3times 11times 17) =$   PPCM $displaystyle (2, 10, 16 )= 80. $
En particulier, comme $ 80$ divise $ 560$, nous avons
$displaystyle a^{560}equiv 1 ; (561) $
pour tout $ a$ premier à 561 (comme dans le petit théorème de Fermat). Un nombre $ n$ tel que $ a^{n-1} equiv 1;(n)$ pour tout entier $ a$ premier à $ p$ s'appelle un nombre de Carmichael. Voici le tableau des premiers $ 17$ nombres de Carmichael non premiers.

$ i$ $ n$ décomposition $ lambda(n)$
$ 1$ $ 561$ $ 3times11times17$ $ 80$
$ 2$ $ 1105$ $ 5times13times17$ $ 48$
$ 3$ $ 1729$ $ 7times13times19$ $ 36$
$ 4$ $ 2465$ $ 5times17times29$ $ 112$
$ 5$ $ 2821$ $ 7times13times31$ $ 60$
$ 6$ $ 6601$ $ 7times23times41$ $ 1320$
$ 7$ $ 8911$ $ 7times19times67$ $ 198$
$ 8$ $ 10585$ $ 5times29times73$ $ 504$
$ 9$ $ 15841$ $ 7times31times73$ $ 360$
$ 10$ $ 29341$ $ 13times37times61$ $ 180$
$ 11$ $ 41041$ $ 7times11times13times41$ $ 120$
$ 12$ $ 46657$ $ 13times37times97$ $ 288$
$ 13$ $ 52633$ $ 7times73times103$ $ 1224$
$ 14$ $ 62745$ $ 3times5times47times89$ $ 2024$
$ 15$ $ 63973$ $ 7times13times19times37$ $ 36$
$ 16$ $ 75361$ $ 11times13times17times31$ $ 240$
$ 17$ $ 101101$ $ 7times11times13times101$ $ 300$


Démonstration. Les parties a) et b) résultent du théorème [*]. Pour c), nous avons l'isomorphisme de groupes

$displaystyle ({mbox{bf Z}}/n{mbox{bf Z}})^* stackrel{_sim}{rightarrow}({mbox{bf Z}}/r{mbox{bf Z}})^* times ({mbox{bf Z}}/s{mbox{bf Z}})^* $
donné par le lemme chinois. L'ordre d'un couple $ (a,b)in({mbox{bf Z}}/r{mbox{bf Z}})^*times({mbox{bf Z}}/s{mbox{bf Z}})^*$ est clairement égal au PPCM  des ordres des deux composantes. Ceci implique que l'ordre maximal d'un couple sera le PPCM  des ordres maximaux atteints dans chaque composante. $ surd$
next up previous contents 
suivant: Résidus quadratiques monter: bad précédent: Structure du groupe des   Table des matières
Bernhard_Keller

Source : http://www.les-mathematiques.net/b/a/d/node21.php3

11:55 Publié dans L'indicatrice de Carmichael | Lien permanent | Commentaires (0) | |  del.icio.us | | Digg! Digg |  Facebook