Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
137 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 
L'indicatrice de Carmichael next up previous contents
suivant: Résidus quadratiques monter: bad précédent: Structure du groupe des   Table des matières

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 Carmichael l'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^m\equiv 1\;(n)$ pour tout entier $ a$ premier à $ n$, alors $ m$ est multiple de $ \lambda(n)$.


Démonstration. Soit $ a\in({\mbox{\bf Z}}/n{\mbox{\bf Z}})^*$ un élément d'ordre $ u=\lambda(n)$ et $ b\in({\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 $ k\geq 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$$ 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(3\times 11\times 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$ $ 3\times11\times17$ $ 80$
$ 2$ $ 1105$ $ 5\times13\times17$ $ 48$
$ 3$ $ 1729$ $ 7\times13\times19$ $ 36$
$ 4$ $ 2465$ $ 5\times17\times29$ $ 112$
$ 5$ $ 2821$ $ 7\times13\times31$ $ 60$
$ 6$ $ 6601$ $ 7\times23\times41$ $ 1320$
$ 7$ $ 8911$ $ 7\times19\times67$ $ 198$
$ 8$ $ 10585$ $ 5\times29\times73$ $ 504$
$ 9$ $ 15841$ $ 7\times31\times73$ $ 360$
$ 10$ $ 29341$ $ 13\times37\times61$ $ 180$
$ 11$ $ 41041$ $ 7\times11\times13\times41$ $ 120$
$ 12$ $ 46657$ $ 13\times37\times97$ $ 288$
$ 13$ $ 52633$ $ 7\times73\times103$ $ 1224$
$ 14$ $ 62745$ $ 3\times5\times47\times89$ $ 2024$
$ 15$ $ 63973$ $ 7\times13\times19\times37$ $ 36$
$ 16$ $ 75361$ $ 11\times13\times17\times31$ $ 240$
$ 17$ $ 101101$ $ 7\times11\times13\times101$ $ 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
 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page