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.

Recherchez sur le site (cours, livres, Agregation, etc.)

Liens mathématiques divers

Février 2025

D L M M J V S
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
Syndicate this site (rss)
Syndicate this site (XML)

Catégories

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