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
70 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
 
 
 
 
 
Calcul de l'ordre badm3 d'un élément next up previous contents
suivant: Groupes cycliques monter: bad précédent: Algorithme de calcul rapide   Table des matières

Calcul de l'ordre d'un élément


Soit $ n$ un entier. Un diviseur positif $ d$ de $ n$ est maximal s'il est de la forme $ n/p$$ p$ est un diviseur premier de $ n$. Soit $ G$ un groupe fini dont la loi est notée multiplicativement. Soit $ g$ un élément de $ G$. Soit $ n$ un entier positif.

Lemme

a)
On a $ g^n=e$ si et seulement si $ n$ est un multiple de l'ordre de $ g$.
b)
L'élément $ g$ est d'ordre $ n$ si et seulement si $ g^n=e$ et $ g^d\neq e$ pour tout diviseur maximal de $ n$.
c)
Si $ g$ est d'ordre $ n$ et $ d$ divise $ n$, alors $ g^d$ est d'ordre $ n/d$.
d)
Plus généralement, si $ g$ est d'ordre $ n$ et $ a$ un entier quelconque, alors $ g^a$ est d'ordre $ n/$PGCD $ (a,n)$.


Démonstration. a) Ceci est clair d'après le lemme [*] qui affirme que l'application $ {\mbox{\bf Z}}/\mbox{\rm ord}(g){\mbox{\bf Z}}\rightarrow G$, $ \overline {k} \mapsto g^k$ est injective.

b) La condition est clairement nécessaire. Supposons réciproquement qu'elle est vérifié. Alors $ n$ est multiple de l'ordre de $ g$ d'après a), mais aucun diviseur propre de $ n$ n'est multiple de l'ordre de $ g$. (tout diviseur propre divise un diviseur maximal de $ n$). Donc $ n=$ord$ (g)$.

c) Nous avons $ (g^d)^k=g^{dk}$ ce qui donne immédiatement l'affirmation.

d) D'après le lemme [*], nous avons $ g^k=e$ ssi $ \overline {k}=\overline {0}$ dans $ {\mbox{\bf Z}}/n{\mbox{\bf Z}}$. Donc l'ordre de $ g^a$ est égal à l'ordre de $ \overline {a}$ dans $ {\mbox{\bf Z}}/n{\mbox{\bf Z}}$. Ce dernier est égal à $ n/$PGCD $ (a,n)$ d'après le lemme [*]. $ \surd$

Remarque 43   Pour déterminer l'ordre de $ g$, on calcule les puissances $ g^d$ pour les diviseurs maximaux $ d$ de $ n$. Si on a $ g^d\neq e$ pour tout diviseur maximal, alors $ g$ est d'ordre $ n$ (et $ G$ est cyclique engendré par $ g$ voir ci-dessous). Sinon, on a $ g^d=e$ pour un diviseur maximal $ d$ de $ n$ et on recommence avec $ n$ remplacé par $ d$. Dans le calcul des puissances $ g^{d'}$ pour les diviseurs maximaux $ d'$ de $ d$ on pourra cependant omettre tous ceux qui divisent un diviseur maximal $ d''$ de $ n$ pour lequel $ g^{d''}\neq e$. Voir l'exemple suivant.

Exemples 44   Calculons l'ordre de $ 2$ dans $ ({\mbox{\bf Z}}/113{\mbox{\bf Z}})^*$. Ce groupe est d'ordre $ n=112=7\times 16$. Les diviseurs maximaux de $ n$ sont $ 16$ et $ 56$. Calculons donc $ 2^{56}$ et $ 2^{16}$.
$ x_k$ $ y_k$ $ q_k$ $ y_k$ $ q_k$
2 1 56 1 16
4 1 28 1 8
16 1 14 1 4
30 1 7 1 2
109 30 3 1 1
16 106 1    
  1   109  
Ainsi $ 2^{16}\neq e$ et $ 2^{56}=e$. Les diviseurs maximaux de $ 56$ sont $ 8$ et $ 28$. Puisque $ 2^{16}\neq e$ nous avons $ 2^8\neq e$ et il suffit de calculer $ 2^{28}$. On trouve $ 2^{28}=1$. Les diviseurs maximaux de $ 28$ sont $ 4$ et $ 14$. Puisque $ 2^{8}\neq 1$, nous avons $ 2^4\neq 1$ et il suffit de calculer $ 2^{14}$. On trouve $ 2^{14}=-1$ et l'ordre de $ 2$ dans $ ({\mbox{\bf Z}}/113{\mbox{\bf Z}})^*$ est donc de $ 28$.

Déterminons les ordres des éléments de $ ({\mbox{\bf Z}}/11{\mbox{\bf Z}})^*$. Calculons l'ordre de $ 2$. Nous avons $ 2^{10}\equiv 1\;(11)$ par le petit théorème de Fermat. Les diviseurs maximaux de $ 10$ sont $ 2$ et $ 5$. Nous avons

$\displaystyle 2^2=4\: , \;2^5 \equiv 2\times 4\times 4 \equiv -1 \;(11).
$

Donc $ 2$ est d'ordre $ 10$ et tout élément de $ ({\mbox{\bf Z}}/11{\mbox{\bf Z}})^*$ est une puissance de $ 2$ d'après le lemme ([*]). Calculons ces puissances
$ k$ 0 $ 1$ $ 2$ $ 3$ $ 4$ $ 5$ $ 6$ $ 7$ $ 8$ $ 9$
$ 2^k$ $ 1$ $ 2$ $ 4$ $ 8$ $ 5$ $ 10$ $ 9$ $ 7$ $ 3$ $ 6$
Maintenant, on calcule facilement les ordres de tous les éléments à l'aide des parties b) et c) du lemme. Par exemple, on a
ord$\displaystyle (3)$ $\displaystyle =$ ord$\displaystyle (2^8) = \frac{10}{\mbox{PGCD }(10,8)} = 5$  
ord$\displaystyle (4)$ $\displaystyle =$ ord$\displaystyle (2^2) = \frac{10}{2} = 5.$  

On trouve la table suivante (voir [*])
$ 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$


next up previous contents
suivant: Groupes cycliques monter: bad précédent: Algorithme de calcul rapide   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