Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger
[
Le forum
|
Le serveur d'exercices
|
Apprendre Latex en ligne
|
Le livre d'or
|
Le formulaire
|
Collaborateurs
|
Mathématiciens
|
Visiteurs
|
Sommaire
]

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
225 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
 
 
 
 
 
Notion d'ordre d'un élément d'un groupe next up previous contents
suivant: Algorithme de calcul rapide monter: bad précédent: Anneaux, groupes et lemme   Table des matières

Notion d'ordre d'un élément d'un groupe

Lemme Soit $ (G, \star)$ un groupe et $ g$ un élément de $ G$. Alors il existe une application

$\displaystyle \exp_g : {\mbox{\bf Z}}\rightarrow G $

et une seule telle que
$\displaystyle \exp_g(1)$ $\displaystyle =$ $\displaystyle g$  
$\displaystyle \exp_g(k+l)$ $\displaystyle =$ $\displaystyle \exp_g(k) \star \exp_g(l)$  

quels que soient $ k,l \in{\mbox{\bf Z}}$.


Démonstration. Nous admettons ce résultat.$ \surd$

Exemple 36   La seconde condition de la définition signifie que $ \exp_g$ est un homomorphisme de groupes de $ {\mbox{\bf Z}}$ vers $ G$. Supposons que $ (G,\cdot)$ est un groupe dont la loi est notée multiplicativement. Alors pour tout $ n$ entier positif, nous avons
$\displaystyle \exp_g(n)$ $\displaystyle =$ $\displaystyle \underbrace{g\cdot g \cdots g}_{n}= g^n$  
$\displaystyle \exp_g(-n)$ $\displaystyle =$ $\displaystyle \exp_g(n)^{-1}= (g^{-1})^n.$  

Nous écrirons $ g^n$ pour $ exp_g(n)$ pour tout $ n$ entier.

Supposons que $ (A,+)$ est un groupe dont la loi est notée additivement. Alors pour tout $ n$ entier positif, nous avons

$\displaystyle \exp_a(n)$ $\displaystyle =$ $\displaystyle \underbrace{a + a +\cdots + a}_{n} = n a$  
$\displaystyle \exp_a(-n)$ $\displaystyle =$ $\displaystyle - \exp_a(n) = -n a.$  

Nous écrirons $ n a$ pour $ \exp_a(n)$ pour tout $ n$ entier.

Corollaire

a)
Soit $ (G,\cdot)$ un groupe dont la loi est notée multiplicativement et $ g$ un élément de $ G$. Pour $ k,l \in{\mbox{\bf Z}}$, on a les égalités suivantes
$\displaystyle g^1$ $\displaystyle =$ $\displaystyle g$  
$\displaystyle g^{k+l}$ $\displaystyle =$ $\displaystyle g^k \star g^l$  
$\displaystyle g^0$ $\displaystyle =$ $\displaystyle e_G$  
$\displaystyle (g^k)^l$ $\displaystyle =$ $\displaystyle g^{kl}$  

b)
Soit $ (A,+)$ un groupe commutatif dont la loi est notée additivement et $ a$ un élément de $ A$. Pour $ k,l \in{\mbox{\bf Z}}$ on a les égalités suivantes
$\displaystyle 1 a$ $\displaystyle =$ $\displaystyle a$  
$\displaystyle (k+l) a$ $\displaystyle =$ $\displaystyle k a + l a$  
$\displaystyle 0 a$ $\displaystyle =$ $\displaystyle 0_A$  
$\displaystyle k (l a)$ $\displaystyle =$ $\displaystyle (kl) a$  



Démonstration. Les deux parties sont des traductions dans la nouvelle notation de certaines propriétés de la fonction $ \exp$. Montrons-les dans les notations de a). Les premières deux égalités ne font que traduire dans la nouvelle notation les propriétés de la définition de $ \exp_g$. La troisième propriété résulte du fait que $ \exp_g$ est un homomorphisme. Pour la dernière propriété, fixons $ k\in{\mbox{\bf Z}}$ et considérons l'application

$\displaystyle f: {\mbox{\bf Z}}\rightarrow G, \: , \;l \mapsto g^{kl}. $

Nous avons clairement $ f(1)=g^k$ et

$\displaystyle f(l+l')=g^{k(l+l')}= g^{kl+kl'} = g^{kl} \star g^{kl'} = f(l)\star f(l'). $

Par l'unicité de l'application $ \exp_{g^k}$ nous pouvons conclure que $ f(l)=\exp_{g^k}(l)$ pour tout $ l\in{\mbox{\bf Z}}$ et donc que $ f(l)=(g^k)^l$ pour tout $ l\in{\mbox{\bf Z}}$.$ \surd$

Définition Soit $ (G, \star)$ un groupe et $ g$ un élément de $ G$. L'ordre de $ g$ est le plus petit entier $ n\geq 1$ tel que $ \exp_g(n)=e_G$ s'il existe un tel entier. Sinon, l'ordre de $ g$ est infini. On note ord$ _G(g)$ ou ord$ (g)$ l'ordre de $ g$ dans $ G$.

Exemple 37   Supposons que $ (G,\cdot)$ est un groupe dont la loi est notée multiplicativement et soit $ g\in G$. Alors nous avons

   ord$\displaystyle _G (g)=\inf\{ n\in{\mbox{\bf N}}\; \vert \; n\geq 1\mbox{ et } g^n=e\}. $

Supposons que $ (A,+)$ est un groupe commutatif dont la loi est notée additivement et soit $ a\in A$. Alors nous avons

   ord$\displaystyle _G (a)=\inf\{ n\in{\mbox{\bf N}}\; \vert \; n\geq 1\mbox{ et } n a = 0_A\}. $

Soit $ (G,\cdot)$ un groupe dont la loi est notée multiplicativement (pour alléger les notations). Supposons que $ g\in G$ est d'ordre fini $ n$. Alors nous avons

$\displaystyle g^{k+n}= g^k\cdot g^n = g^k \cdot e = g^k $

pour tout entier $ k$ et $ n$ est le plus petit entier $ \geq 1$ avec cette propriété. Autrement dit, la suite des puissances de $ g$

$\displaystyle g^0=e\: , \;g \: , \;g^2 \: , \;\ldots, g^k, \ldots $

est périodique de période $ n$. Nous avons aussi

$\displaystyle g^{a+kn}= g^a g^{kn}= g^a (g^n)^k = g^a e^k = g^a $

pour tout entier $ a\in{\mbox{\bf Z}}$ et tout entier $ k\in{\mbox{\bf Z}}$. Autrement dit la valeur de $ g^{a}$ ne dépend que de la classe de congruence de $ a$ modulo $ n$.

Lemme Soit $ n$ un entier $ \geq 2$ et soit $ \overline {a}$ une classe modulo $ n$ considérée comme élément du groupe $ (A,+)=({\mbox{\bf Z}}/n{\mbox{\bf Z}}, +)$. Alors

   ord$\displaystyle _{{\mbox{\bf\scriptsize Z}}/n{\mbox{\bf\scriptsize Z}}} (\overline {a}) = \frac{\mbox{PPCM }(a,n)}{a} = \frac{n}{\mbox{PGCD }(a,n)}. $


Démonstration. Nous avons $ k\overline {a}=\overline {0}$ ssi $ ka$ est un multiple de $ n$, c'est-à-dire un multiple commun à $ a$ et $ n$. Donc $ ka$ doit être un multiple de PPCM $ (a,n)$ et $ k$ un multiple de PPCM $ (a,n)/a$. Compte tenu de l'égalité

   PPCM $\displaystyle (a,n) = \frac{a n}{\mbox{PGCD }(a,n)} $

nous obtenons aussi la seconde égalité.$ \surd$

Remarque 38   Il n'existe pas de formule analogue pour l'ordre d'un élément $ \overline {x}$ dans le groupe multiplicatif $ ({\mbox{\bf Z}}/n{\mbox{\bf Z}})^*$. Cependant nous verrons que cet ordre est toujours un diviseur de $ \phi(n)$, l'ordre du groupe $ ({\mbox{\bf Z}}/n{\mbox{\bf Z}})^*$.

Lemme Soit $ (G, \star)$ un groupe et $ g$ élément de $ G$. Alors $ g$ est d'ordre infini ssi l'application

$\displaystyle \exp_g : {\mbox{\bf Z}}\rightarrow G $

est injective. En particulier, tous les éléments d'un groupe fini sont d'ordre fini.


Démonstration. Si l'application $ \exp_g$ est injective nous avons $ \exp_g(n)\neq \exp_g(0)$ pour tout $ n>0$. Puisque $ \exp_g(0)=e$, nous avons donc $ \exp_g(n)\neq e$ pour tout $ n>0$ et $ g$ est d'ordre infini.

Réciproquement supposons $ g$ d'ordre infini. Soient $ k\leq l$ des entiers tels que $ \exp_g(k)=\exp_g(l)$. Alors nous avons $ \exp_g(l-k)=e$. Puisque $ l-k\geq 0$ et que $ g$ est d'ordre infini, il s'ensuit que $ k=l$ et donc que $ \exp_g$ est injective. $ \surd$

Lemme Soit $ (G,*)$ un groupe et $ g\in G$ un élément d'ordre fini $ n$. Alors l'application

$\displaystyle {\mbox{\bf Z}}/n{\mbox{\bf Z}}\rightarrow G\: , \;\overline {a} \mapsto \exp_g(a) $

est bien définie et injective. En particulier, l'ensemble des éléments de la forme $ \exp_g(a)$, $ a\in{\mbox{\bf Z}}$, est de cardinal $ n$.


Démonstration. Supposons pour alléger les notations que la loi de $ G$ est notée multiplicativement. Nous avons donc

$\displaystyle exp_g(a)=g^a$    et $\displaystyle g^n=e $

pour tout $ a\in{\mbox{\bf Z}}$. Donc

$\displaystyle exp_g(a+kn)= g^{a+kn} = g^a g^{kn} = g^a (g^n)^k = g^a e^k = g^a. $

L'application est donc bien définie. Supposons que $ a\leq b$ sont deux entiers dont les classes ont même image. Alors nous avons $ g^a=g^b$ et donc $ g^{b-a}=e$. Pour montrer que $ n$ divise $ b-a$, effectuons la division euclidienne $ b-a=qn+r$ de $ b-a$ par $ n$. Par définition, nous avons $ 0 \leq r \leq (n-1)$. De l'autre côté, nous avons $ e=g^{b-a}= g^r$. Puisque $ g$ est d'ordre $ n$, il s'ensuit que $ n$ divise $ b-a$ et donc que $ \overline {a}=\overline {b}$. $ \surd$

Théorème [Lagrange] Soit $ (G,*)$ un groupe fini. L'ordre de tout élément de $ G$ divise l'ordre de $ G$.

Exemple 39   Considérons le groupe $ G=({\mbox{\bf Z}}/11{\mbox{\bf Z}})^*$. L'ordre de $ G$ est de $ 10$. Voici les ordres des éléments de $ G$ :
$ g$ $ \overline {1}$ $ \overline {2}$ $ \overline {3}$ $ \overline {4}$ $ \overline {5}$ $ \overline {6}$ $ \overline {7}$ $ \overline {8}$ $ \overline {9}$ $ \overline {10}$
ord$ (g)$ $ 1$ $ 10$ $ 5$ $ 5$ $ 5$ $ 10$ $ 10$ $ 10$ $ 5$ $ 2$
Notons que le nombre d'éléments d'ordre $ 10$ est de $ 4=\phi(10)$, le nombre d'éléments d'ordre $ 5$ est de $ 4=\phi(5)$ et le nombre d'élments d'ordre $ 2$ est de $ 1=\phi(2)$. Nous verrons que ce n'est pas un hasard ([*]). Nous verrons aussi comment calculer facilement ce tableau (exemples [*])


Démonstration. Pour alléger les notations, supposons que la loi de $ G$ est notée multiplicativement. Soit $ g\in G$. La démonstration se fait en plusieurs étapes :

Première étape : la relation définie par

$\displaystyle x \equiv x' \; (g) \Longleftrightarrow x = x' g^k$    pour un $\displaystyle k\in{\mbox{\bf Z}}\: , \; $

est une relation d'équivalence. Nous laissons cette vérification au lecteur. Notons $ \overline {x}$ la classe d'équivalence d'un élément $ x$. Par définition, la classe de $ x$ est formée de tous les éléments de la forme $ x g^k$, $ k\in{\mbox{\bf Z}}$.

Seconde étape : le cardinal de la classe de $ e$ est l'ordre de $ g$. En effet, la classe de $ e$ est formée de tous les éléments de la forme $ g^k$, $ k\in{\mbox{\bf Z}}$. C'est donc l'image de l'application $ \exp_g: {\mbox{\bf Z}}\rightarrow G$. Nous avons vu au lemme ([*]) qu'elle est en bijection avec $ {\mbox{\bf Z}}/n{\mbox{\bf Z}}$ où $ n$ est l'ordre de $ g$.

Troisième étape : toutes les classes d'équivalence ont même cardinal que la classe de $ e$. En effet, si $ x$ est un élément de $ G$, nous avons des bijections inverses l'une de l'autre entre $ \overline {e}$ et $ \overline {x}$ données par les applications $ y \mapsto xy$ resp. $ z \mapsto x^{-1} z$.

Quatrième étape : le cardinal de la classe de $ e$ divise l'ordre de $ G$. En effet, nous savons que $ G$ est la réunion disjointe des classes d'équivalence. L'ordre de $ G$ est donc la somme des cardinaux des classes. Or toutes les classes ont même cardinal que $ \overline {e}$. L'ordre de $ G$ est donc égal au cardinal de la classe de $ e$ multiplié par le nombre de classes d'équivalence.

Conclusion : l'ordre de $ g$, qui est égal au cardinal de la classe de $ e$ (seconde étape), divise l'ordre de $ G$ (troisième étape). $ \surd$

Corollaire [Théorème d'Euler] Soit $ n$ un entier $ \geq 2$ et $ a$ un entier premier avec $ n$. Alors on a

$\displaystyle a^{\phi(n)} \equiv 1 \; (n), $

où $ \phi$ est l'indicatrice d'Euler.


Démonstration. Comme $ a$ est premier avec $ n$, la classe $ g=\overline {a}$ appartient au groupe $ G=({\mbox{\bf Z}}/n{\mbox{\bf Z}})^*$. L'affirmation résulte du théorème de Lagrange car $ \phi(n)$ est l'ordre du groupe $ ({\mbox{\bf Z}}/n{\mbox{\bf Z}})^*$ par définition.$ \surd$

Corollaire [Petit Théorème de Fermat] Si $ p$ est un nombre premier et $ a$ un entier qui n'est pas divisible par $ p$, on a

$\displaystyle a^{p-1}\equiv 1\;(p). $



Démonstration. On applique le théorème d'Euler en utilisant que $ \phi(p)=p-1$ pour un nombre premier. $ \surd$

Remarque 40   Les théorèmes de Fermat (petit) et d'Euler permettent de calculer très rapidement certains restes de puissances. Dans les exemples suivants, on cherche le reste $ r$ de la division euclidienne de $ a$ par $ b$ :

Exemples 41   $ a=67^{100}$, $ b=101$ : le nombre $ 101$ est premier et $ 67$ n'est pas divisible par $ 101$. D'après le petit théorème de Fermat, on a $ 67^{100} \equiv 1 \;(101)$ et donc $ r=1$.

$ a=1995^{540}$, $ b=541$ : le nombre $ 541$ est premier et $ 1995$ n'est pas divisible par $ 541$. D'après le petit théorème de Fermat, on a $ 1995^{540}\equiv 1\; (541)$ et donc $ r=1$.

$ a=25^{24}$, $ b=72$ : nous avons $ \phi(72)= \phi(8\times 9) = \phi(8) \phi(9)= 4\times 6= 24$. Les nombres $ 72$ et $ 25$ sont premiers entre eux. Nous pouvons donc appliquer le théorème d'Euler pour conclure que $ 25^{24}\equiv 1\; (72)$. Donc $ r=1$.

$ a=51^{24}$, $ b=72$ : nous avons $ \phi(72)=24$ (voir le numéro précédent). Or, les nombres $ 51$ et $ 72$ ne sont pas premiers entre eux et nous ne pouvons pas appliquer le théorème d'Euler. Cependant, soit $ x = 51^{24}$. D'après le lemme chinois, pour connaître la classe de $ x$ modulo $ 72$, il suffit de connaître les restes de $ x$ modulo $ 8$ et modulo $ 9$. Or

$\displaystyle x$ $\displaystyle \equiv$ $\displaystyle 51^{24} \equiv 3^{24} \equiv 1 \;\;(8)$  
$\displaystyle x$ $\displaystyle \equiv$ $\displaystyle 51^{24} \equiv 6^{24} \equiv 0 \;\;(9).$  

Ici, nous avons appliqué le théorème d'Euler à $ 3$ et $ 8$ ($ \phi(8)=4$) et nous avons utilisé le fait que $ 6^2\equiv 0 \;(9)$. Le lemme chinois nous permet de conclure que $ x \equiv 9\;(72)$ et le reste recherché est donc $ r=9$.

next up previous contents
suivant: Algorithme de calcul rapide monter: bad précédent: Anneaux, groupes et lemme   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