![]() Anneau quotient Z/nZ des classes résiduelles modulo n |
Un groupe est dit fini si le nombre de ses éléments, appelé alors ordre du groupe, est fini. L'étude des groupes finis, principalement leur classification, fut un sujet ardu d'étude jusqu'en 1982.
Dans C, ensemble des nombres complexes, i désignant considérons G = {1, i, -1, -i} muni de la multiplication usuelle des nombres complexes : (G, × ) est un groupe fini, sous-groupe commutatif de (C*,×). C'est le groupe cyclique engendré par i. Il peut aussi être engendré par -i. On peut établir sa table de Pythagore :
Un résultat fondamental sur les groupes finis (théorème de Lagrange) :
Ce théorème dit de Lagrange, mais aussi de Cauchy, voire de Cayley (mais ce dernier est plutôt attaché à ce résultat là), fut également énoncé auparavant par Euler dans une formulation équivalente sans le secours de la notion algébrique de groupe :
Dans un groupe fini E d'ordre n (ayant n éléments), si k est l'ordre d'un sous-groupe F de E, alors k divise n.
Preuve : utilisons la notation additive pour simplifier les écritures. Soit R la relation définie dans E par : a R b ⇔ a - b ∈F. Il est clair que R est une relation d'équivalence dont les classes sont en nombre fini (puisque E est fini). Dans E, b est en relation avec a si et seulement si b = a + u , u∈F. Par suite, le cardinal de toute classe est le cardinal k de F. Et puisque les classes forment une partition de E, il s'ensuit que si p est le nombre de classes, alors n = pk.
Théorème 1 :
Si (G,*) est un groupe fini
d'élément neutre e et a un élément de G distinct de e tel que le
sous-groupe
monogène H engendré par a soit fini d'ordre p (groupe cyclique),
alors a(p) = e.
en désignant par a(p) le
composé de p éléments égaux à a avec la convention a(o) = e, a(1)
= a.
∗∗∗ Preuve en
exercice :
a) Tant que a(k)
≠ e,
considérons la suite d'éléments a(1) = a, a(2), ..., a(k). Montrer que l'on obtient ainsi k éléments distincts.
Indic. :
raisonner par l'absurde en supposant qu'il
existe i et j dans [1,k] tels que a(i) = a(j).
b) Soit k le plus petit entier naturel
tel que a(k+1) = e. Montrer que k existe effectivement.
Indic. :
H est le sous-groupe monogène engendré par a,
il admet donc un symétrique dans H...
c)
On pose Hk = {e,a, a(2),
..., a(k)}. Montrer que Hk
est un sous-groupe de H.
Indic. :
Stabilité :
Pour tout a(m) et a(m') de Hk, on a a(m)*a(m')
= a(m+m').
On peut écrire m+m' = q(k+1)+r avec 0
≤ r
≤ k.
Existence du symétrique :
Pour tout a(m), 1 ≤ m ≤ k, on a a(m)*a(k+1-m) = a(k+1) = e avec
-k ≤ -m ≤ 1, donc 1 ≤ k+1-m ≤ k.
d)
En utilisant le théorème de Lagrange,
justifier que p est un multiple de k+1, puis que a(p) = e.
Théorème 2 :
Si (G,*) est un groupe fini
d'ordre n d'élément neutre e, alors pour tout élément a de G : a(n) =
e
en désignant par a(n) le
composé de n éléments égaux à a avec la convention a(o) = e, a(1)
= a.
Preuve : soit H est le sous-groupe monogène de G engendré par a. D'après le théorème de Lagrange son ordre divise n. Utiliser alors le théorème précédent.
∗∗∗
Soit A une partie non vide d'un groupe (G,*)
On appelle sous-groupe engendré par A, et on note H, le plus petit des sous-groupes de G contenant A.
a) Montrer que cette définition a un sens (H existe).
b) Montrer que le sous-groupe engendré par un unique élément g de G est l'ensemble des éléments de la forme :
gn = g*g*...g* (n termes égaux à g)
c) Montrer que toute intersection de sous-groupes de G est un sous-groupe de G.
d) Montrer que le sous-groupe engendré par A est l'intersection des sous-groupes contenant A.
!
Par
définition, un
groupe cyclique
est fini mais un groupe fini n'est pas nécessairement
cyclique
!
considérer le cas du groupe
symétrique étudié ci-après ou encore
le groupe de Klein.
Groupe et anneau des classes résiduelles modulo n, groupe et anneau quotient : |
Un cas fondamental de groupe fini, car nombreux sont les groupes finis qui lui sont isomorphes (et les propriétés de l'un se transposent à l'autre), est le groupe des classes résiduelles modulo n, où Z désigne l'anneau des entiers relatifs :
Il est d'abord clair que si n est un entier que l'on peut supposer positif et non nul, l'ensemble nZ des entiers relatifs de la forme nk, k décrivant Z, est un sous-groupe additif de (Z,+) : ensemble des multiples de n, sous-groupe monogène (engendré par n) .
Un résultat intéressant :
Tout sous-groupe de (Z,+) est de la forme nZ : groupe monogène engendré par n
Preuve : soit S un sous-groupe de Z autre que {0} et Z. S ne contient donc pas 1. L'ensemble des entiers positifs de S, noté S+, admet un plus petit élément n au moins égal à 2 (ensemble dénombrable, borné inférieurement). Tout élément de Z de la forme kn, k entier naturel, est un élément de S (évident par récurrence car kn = n + n + ... + n). Donc S contient nZ. Par division euclidienne, tout entier de S+ qui n'est pas de la forme kn s'écrit a = kn + r, 0 < r < n. On a alors r = a - kn > 0. Mais a et kn sont dans S+, donc r aussi. Voilà un entier de S strictement plus petit que son plus petit élément... Pas possible, donc r = 0. Ce qui montre que S = nZ.
Le groupe et l'anneau Z/nZ :
On montre très facilement que la relation de congruence modulo n, n∈N, due à Gauss notée ≡ :
est une relation d'équivalence définie dans (Z ,+) compatible avec l'addition de ce groupe.
On peut écrire x - y∈nZ ⇔ ∃ k∈N / y = x - nk. La classe de x, notée ici x est l'ensemble des entiers relatifs y qui différent de x d'un multiple de n. Par division euclidienne de x par n, on sait qu'il existe un unique entier naturel x' tel que x = nq + r avec 0 ≤ r ≤ n - 1 : r est le reste de la division euclidienne de x par n.
Ainsi r = x - nq est l'unique entier équivalent à x dans l'intervalle d'entiers [0, n - 1]. On choisit d'exprimer les classes d'équivalences au moyen de ces restes. L'ensemble quotient est fini et peut ainsi s'écrire:
Z/nZ = {0, 1, 2 ... n-1}
Lorsque n = 2, les restes de la division sont 0 et 1. On a Z/2Z = {0, 1}. Lorsque n = 4, Z/4Z = {0,1,2,3},
On parle de l'ensemble des classes résiduelles modulo n ou encore des classes de congruence modulo n, constitué des entiers donnant le même reste dans la division euclidienne par n.
♦ Muni de l'addition quotient induite par celle de Z , à savoir :
x + y = x + y
l'ensemble (Z/nZ ,+) est un groupe additif commutatif, groupe quotient de Z par la relation de congruence.
♦ Muni en outre de la multiplication quotient induite par celle de Z , à savoir :
x × y = x × y
(Z/nZ ,+, ×) est aussi un anneau commutatif unitaire (d'élément unité la classe de 1) : anneau quotient de Z par la relation de congruence ≡.
Théorème 3 :
L'anneau Z/nZ est intègre si et seulement si n est premier
Autrement dit, dans le cas n premier, Z/nZ n'admet aucun diviseur de zéro, c'est à dire d'éléments x' et y' tels que x' × y' = 0'.
Preuve : soit n premier; supposons x' × y' = 0. Si x et y sont des représentants de x' et y', on a x × y multiple de p : xy = kn. L'entier n étant premier, il divise nécessairement x ou y. Par suite, on a x' = 0 ou y' = 0 : Z/nZ est intègre. Si n n'est pas premier, on peut écrire n = xy, donc 0 = x' × y' avec x' et y' non nuls. Z/nZ possède des diviseurs de 0, il n'est pas intègre : la condition n premier est donc nécessaire et suffisante.
Dans Z/5Z = {0,1,2,3,4}, l'inverse de 1 est 1, 2 et 3 sont inverses l'un de l'autre car 2 × 3 = 6 = 5 + 1 ≡ 1 [5], donc 2 × 3 = 1. Quant à 4, il est son propre inverse (élément involutif) car 4 × 4 = 16 = 15 + 1 ≡ 1 [5]. C'est ainsi que (Z/nZ ,+, ×) est un corps fini.
Dans Z/4Z = {0,1,2,3}, 2 × 2 = 0 : 2 est un diviseur de 2, donc pas d'inverse. 3 est inversible : il est son propre inverse car 3 × 3 = 9 = 8 + 1 ≡ 1 [4].
Tables de Pythagore des anneaux Z/3Z et Z/4Z : »
♦ Dans Z/nZ, 1 est un élément générateur en ce sens que tout élément de ce groupe est un multiple de 1.
∗∗∗
Lorsque n > 2, justifier que n-1 est premier
avec n et que n-1 est
un générateur de Z/nZ autre que
1.
(on montrera que {0,
n-1,
2(n-1),
3(n-1),
, ..., (n-1)(n-1)}
coïncide avec Z/nZ
On dit que la classe g de Z/nZ est un générateur de cet anneau ou que g engendre Z/nZ lorsque tout élément de ce groupe est un multiple de g.
Théorème 4.1 :
Les éléments générateurs de
Z/nZ
sont les classes
g avec g et n premiers entre eux.
Pour de tels éléments Z/nZ
= {0,
g,
2g,
3g,
, ..., (n-1)g}.
Preuve : soit g un élément générateur de Z/nZ et considérons la suite des multiples de g dans Z/nZ : 0, g, 2g, 3g, , ..., (n-1)g, ng, (n+1)g, ... L'élément ng est nul, puis (n+1)g = ng + g = g, etc. L'ensemble des multiples de g se réduit à l'ensemble G = {0, g, 2g, 3g, , ..., (n-1)g} ⊂ Z/nZ. Et ces deux ensembles finis de cardinal n sont en fait égaux puisque g est générateur. Cela signifie qu'il n'existe aucun couple (k,k') d'entiers distincts non nuls au plus égaux à n-1 tels que kg = k'g. Une telle égalité signifierait (k-k')g = 0 avec |k - k'| ≤ n-1. Autrement dit (k-k')g serait un multiple de n dans la liste [g, 2g, 3g, , ..., (n-1)g], ce qui ne se produit que lorsque g et n ont un diviseur commun d autre que 1. En effet si n = d × m et g = d × p, m figure dans la liste [1, 2, ..., m ..., n-1] et par conséquent dans la liste [g, 2g, 3g, , ..., (n-1)g] = [dp, 2dp, ..., , dpm, ..., (n-1)g]. Or dpm = pn = 0 [n].
Théorème 4.2 :
Les éléments générateurs de
Z/nZ
sont les éléments inversibles de
(Z/nZ, ×)
(c'est à dire les
classes
g avec g et n premiers entre eux).
Preuve : Soit g générateur, on a alors Z/nZ = {0, g, 2g, 3g, , ..., (n-1)g}. Parmi les n éléments du groupe figure l'élément unité 1 qui est donc de la forme kg = k × g, 1 ≤ k ≤ n-1. g est donc inversible et son inverse est k. Inversement si x est inversible dans (Z/nZ, ×), alors x est non nul et il existe un unique y non nul dans Z/nZ tel que x × y =1 et on peut écrire tout élément k de Z/nZ sous la forme k × (x × y) = (k × y) × x , ce qui montre que x est générateur.
En conclusion :
Dans l'anneau (Z/nZ ,+, ×), un élément z admet un inverse si et seulement si z et n sont premiers entre eux. L'ensemble des éléments inversibles (unités du groupe) sont les générateurs de l'anneau et constituent un groupe pour la multiplication noté (Z/nZ)*. De plus, son ordre (cardinal) est φ(n), indicateur d'Euler ou totient d'Euler.
Corollaire :
L'anneau Z/nZ est un corps si et seulement si n est premier ☼
Théorème de E. H. Moore : »
Théorème 5 :
à un isomorphisme près, (Z,+) est le seul groupe monogène infini et (Z/nZ ,+) est le seul groupe monogène fini.
Théorème 6, Élément primitif (ou racine primitive modulo n) :
p désignant un nombre premier et k un entier naturel non nul, le groupe (Z/nZ)* est cyclique si et seulement si n = 1 ou 4, ou bien n = p, pk ou 2pk. Tout générateur est alors dit primitif; on parle aussi de racine primitive modulo n.
» Preuve : on pourra se référer au cours d'Arithmétique & combinatoire d'Emmanuel Fricain (univ. Lille 1), ch. 2
∗∗∗
1. Montrer que si n est premier, le groupe Z/nZ
des entiers modulo n n'a aucun sous-groupe propre (autre que lui-même).
2. Quels sont les sous-groupes de Z/6Z ?
3. Exercices
d'arithmétique élémentaire (Bernhard Keller, Université Paris 7) :
http://www.math.jussieu.fr/~keller/mt282/ExArithZ.pdf
Théorème 7 :
Les groupes multiplicatifs d'éléments Z/mnZ et Z/mZ × Z/nZ sont isomorphes si pgcd(m,n) = 1
Preuve : voir anneau produit sur la page consacrée à la structure d'anneau.
Groupe de Klein : » Problème des mots : » » Artin
Groupe symétrique ou groupe des permutations d'un ensemble fini : |
Muni de la loi de composition des applications (loi o), l'ensemble des bijections d'un ensemble E dans lui-même, est un groupe, non commutatif si E possède plus de 2 éléments. L'application identique i est l'élément neutre du groupe. Lorsque E est fini et possède n éléments, ces bijections s'appellent des permutations (autrefois appelées substitutions) et leur groupe en possède n! (factorielle n) : c'est un groupe fini, appelé groupe symétrique de E souvent noté Sn (S comme substitution). Il n'est pas cyclique.
Lorsque E = {a, b, c}, le groupe symétrique de E, soit S3, possède donc 6 éléments. Décidons de désigner par xyz la permutation a → x , b → y , c → z, on peut alors les écrire :
abc = i, acb , bac, bca, cab, cba
Par exemple, par composition (loi
o), on voit que bca
est la permutation inverse de cab (symétrique de cab pour
la loi o) :
cab : a
→
c , b
→
a , c
→
b
bca : a
→
b , b
→
c , c
→
a
bca o
cab
: a
→
a , b
→
b , c
→
c
C'est dire que bca o
cab = i
, soit bca-1 = cab.
acb, bac et cba étant leur propre symétrique, ils ne
peuvent engendrer le groupe.
On vérifiera que bca(3) = cab(3)
= e : le groupe n'est donc pas cyclique.
Mais on peut noter que H ={abc, cab, bca} est un sous-groupe cyclique de S3. à un isomorphisme près, H est le seul groupe fini d'ordre 3; on peut l'identifier à Z/3Z.
Un théorème de Cayley : |
Tout groupe fini d'ordre n est isomorphe à un sous-groupe du groupe symétrique Sn d'ordre n! = 1 × 2 × ... × n
La preuve de ce théorème utilise le concept de groupe opérant sur un ensemble. On la trouvera sur cette page.
Permutation circulaire et groupe alterné : |
Une permutation opérant sur (x, y, z, ...,t,u) est dite circulaire pour signifier que (x, y, z, ...,t) est transformé en (y, z,...,u,x) : tout est décalé d'un rang et le dernier terme prend la place du premier.
Ci-dessous, une représentation du groupe symétrique S4 (24 = 4! éléments). On remarque à chaque niveau le passage d'une permutation à l'autre par circularité :
Lorsqu'on procède à une permutation, on échange au moins un couple d'éléments : on fait ainsi au moins une inversion, plutôt appelée transposition. Toute permutation apparaît alors comme composé de transpositions.
Lorsqu'on considère les permutations de Sn correspondant à un nombre pair de transpositions, on obtient un sous-ensemble de Sn, noté généralement An , appelé groupe alterné.
On démontre que An est distingué dans Sn. Le cardinal de Sn étant n! (factorielle n), il est clair que celui de An est n!/2. Ci-dessus, on trouve les éléments de A4 alternativement à partir du centre (vu qu'il y a 4 éléments, toute permutation circulaire engendre 4 transpositions).
∗∗∗
1.
Montrer que, muni de la loi de
composition des applications, le sous-ensemble des permutations
circulaires est un sous-groupe de Sn (sous-groupe
cyclique).
2. Montrer que An
est un sous-groupe distingué de Sn.
3. Un
exercice sur les
permutations circulaires.