Chapitre 2 : Le groupe (Z=nZ)�.

Dans tout ce chapitre, n désigne un entier supérieur ou égal à 2.

I Quelques résultats sur les groupes.

a) Dé�nitions, premières propriétés

Dé�nition I.1 Soit E un ensemble, une loi de composition interne (ou l.c.i.) sur E est une application:

E � E �! E(a; b) �! a � b

Lorsque il existe une loi de composition interne � sur E on dit qu�il est muni d�une l.c.i. et on le note(E; �)

Dé�nition I.2 Soit (G; �) un ensemble muni d�une lci, on dit que G est un groupe si les trois conditionssuivantes sont véri�ées :

1. La l.c.i. � est associative, c�est à dire :

8f; g; h 2 G; f � (g � h) = (f � g) � h

2. La l.c.i. � admet un élément neutre, c�est à dire

9e 2 G tel que 8g 2 G; g � e = e � g = g

3. Tout élément g de G admet un élément symétrique pour la loi �, c�est à dire

8g 2 G;9g0 2 G; tel que g � g0 = g0 � g = e

Si de plus la loi � est commutative c�est à dire

8g; h 2 G; g � h = h � g

on dit alors que (G; �) est un groupe commutatif (ou abélien).

Exemple I.1 1. (Z;+) est un groupe mais pas (N;+).

2. (Q;+), (Q�;�), (R;+) et (R�;�) sont des groupes. Notons que pour la loi + l�élément neutre est 0 etque le symétrique s�apelle l�opposé alors que pour la loi � l�élément neutre est 1 et le symétrique s�appellel�inverse.

3. (R [X] ;+) : l�ensemble des polynômes à coe¢ cients dans R muni de la loi + est un groupe.

4. (Z;�) n�est pas un groupe, (R [X] ;�) non plus.

5. L�ensembles des vecteurs du plan (ou de l�espace) est un groupe pour la loi + dont l�élément neutre estle vecteur nul.

6. (f�1; 1g ;�) est un groupe.

7. L�ensemble F (R;R) des applications de R dans R muni de la loi + est un groupe dont l�élément neutreest la fonction nulle.

8. (Z=nZ;+) est un groupe dont l�élément neutre est _0.

9. ((Z=nZ)� ;�) est un groupe dont l�élément neutre est _1.

1

Tout les groupes donnés ci-dessus sont abéliens.

Proposition I.1 Soit (G; �) un groupe alors on a les propriétés suivantes :

1. G 6= ;

2. L�élément neutre est unique.

3. Tout élément de g a un symétrique unique.

Démonstration. Comme il existe au moins un élément neutre on a le premier point.Suposons qu�il existe e et e0 deux éléments neutres de G, alors

e � e0 = e car e0 est un élément neutre

e � e0 = e0 car e est un élément neutre

donc e = e0.Supposons qu�il existe un élément g ayant deux symétriques g0 et g00 donc g � g0 = e et g00 � g = e alors

g00 ��g � g0

�= g00 � e = g00

mais par associativité de � on a

g00 ��g � g0

�=�g00 � g

�� g0 = e � g0 = g0

et doncg0 = g00

Remarque I.1 Si la loi du groupe est notée + alors on note 0 l�élément neutre et �x le symétrique de xqu�on appelle alors l�opposé de x:

Si la loi du groupe est notée � alors on note 1 l�élément neutre et x�1 (ou 1x) le symétrique de x qu�on

appelle alors l�inverse de x:

Dé�nition I.3 Soient (G; �) et (H; �) deux groupes, une application f : F ! G est un morphisme degroupe si pour tout g et g0 2 G on a

f�g � g0

�= f (g) � f

�g0�

Si de plus f est bijective, alors on dit que f est un isomorphisme de groupes, et que les groupes G etH sont isomorphes.

On peut facilement véri�er que si f est un morphisme de groupe bijectif alors son application inverse f�1

est également un morphisme de groupe.

b) Sous-Groupes

Dé�nition I.4 Soit (G; �) un groupe et soit F � G une partie de G. On dit que F est un sous-groupe deG si et seulement si (F; �) est un groupe.

Proposition I.2 Soit (G; �) un groupe et soit F � G une partie de G. F est un sous-groupe de G si etseulement si les conditions suivantes sont satisfaites :

� e 2 F (F contient l�élément neutre)

� 8x; y 2 F; x � y 2 F (F est stable par la loi �)

� 8x 2 F le symétrique de x par � est dans F .

2

Exemple I.2 1. L�ensemble des nombres pairs est un sous groupe de (Z;+) ; mais pas l�ensemble desnombres impairs.

2. Plus généralement nZ : l�ensemble des multiples de n est un sous-groupe de (Z;+).

3. Z [X] : polynômes à coe�cients dans Z est un sous-groupe de (R [X] ;+).

4. Soit ~u un vecteur (du plan ou de l�espace) alors l�ensemble des vecteurs colinéaires à ~u :

f~v tel que 9k 2 Z; ~v = k~ug

est un sous-groupe du groupe des vecteurs (du plan ou de l�espace).

c) Ordre d�un élément - groupes cycliques

Proposition I.3 Soit (G;�) un groupe �ni, soit H un sous-groupe de G alors le cardinal de H divise lecardinal de G.

Démonstration. Soit la relation binaire R dé�nie sur G par

xRy () xy�1 2 H

Cette relation est ré�exive car xx�1 = 1 2 HCette relation est symétrique car si xy�1 2 H alors

�xy�1

��1 2 H (car c�est un sous groupe) et�xy�1

��1=

yx�1

Cette relation est transitive car si xy�1 2 H et yz�1 2 H alors le produit xy�1yz�1 = xz�1 2 H.Donc R est une relation d�équivalence et les classes d�équivalence de la relation R forment une partition

de G (elles sont non-vides, deux à deux disjointes et leur réunion est G).On note xH = fxh pour h 2 Hg ; on a yRx () y 2 xH donc xH est la classe d�équivalence de x, en

particulier la classe de 1 est H . On va montrer que toutes les classes d�équivalences ont le même cardinal(égal au cardinal de H) ce qui prouvera le résultat. On a card(xH) � card(H) mais si xh = xh0 alors onobtient en multipliant par x�1 chaque membre de cette équation h = h0 donc card(xH) = card(H).

On va maintenant donner quelques dé�nitions :

Dé�nition I.5 Soit (G;�) un groupe, et soit g 2 G, on note hgi le sous-groupe engendré par g; donchgi =

�g�2; g�1; 1; g; g2; g3; :::

Proposition I.4 Si (G;�) est un groupe �ni, pour tout g 2 G il existe un entier positif k minimal tel quegk = 1 et alors hgi =

�1; g; g2; :::; gk�1

k s�appelle l�ordre de g et est noté ord(g). On a de plus ord(g) = card hgi

Démonstration. Si G est �ni, hgi est �ni donc il existe a et b 2 Z tel que ga = gb donc gja�bj = 1 doncfx 2 N; gx = 1g est non vide donc il admet un élément minimal : k.

On a évidemment�1; g; g2; :::; gk�1

� hgi, réciproquement soit gx un élément de hgi, e¤ectuons la division

euclidienne de x par k, on obtient x = kd + r où 0 � r < k et donc gx = gkd+r =�gk�dgr = gr donc

gx 2�1; g; g2; :::; gk�1

. Il reste à montrer que card hgi = k et donc que tous les éléments de

�1; g; g2; :::; gk�1

sont distincts, mais si on avait gx = gy avec 0 � x < y � k � 1 alors on aurait gy�x = 1 où 0 < y � x � k � 1or ceci est impossible par dé�nition de k:

Exemple I.3 Dans (Z=20Z;+) on a ord(12) = 5.

Comme on a ord(g) = card hgi, et la proposition précédente nous permet d�énoncer :

Corollaire I.1 Soit (G;�) un groupe �ni, et soit g 2 G, l�ordre de g divise le cardinal de G.

3

Corollaire I.2 Soit (G;�) un groupe �ni de cardinal n, et soit g 2 G, on a gn = 1. En particulier six 2 (Z=nZ)� on a x'(n) = 1, c�est l�identité d�Euler.

Démonstration. D�après le résultat précédent il existe k 2 N tel que n = k�ord(g) dong gn =�gord(g)

�k= 1.

Dé�nition I.6 Soit (G;�) un groupe �ni, G est dit cyclique si il existe un élément g de G tel que G = hgi.On dit que g est un générateur de G.

Exemple I.4 Le groupe (Z=nZ;+) est cyclique, en e¤et Z=nZ = h1i.

Il faut remarquer que dans un groupe cyclique tous les éléments ne sont pas des générateurs par exempledans Z=10Z, h5i = f0; 5g et h2i = f0; 2; 4; 6; 8g alors que h3i = h7i = Z=10Z. On va maintenant donner lenombre de générateurs d�un groupe cyclique.

Proposition I.5 Soit (G;�) un groupe cyclique de cardinal n. Le nombre de générateurs de G est ' (n).

Démonstration. Soit g un générateur de G et soit h un élément de G il existe donc un entier positif k � n�1tel que h = gk, on va montrer que

G = hhi () k ^ n = 1

ce qui donnera le résultat puisque ' (n) est le nombre d�entiers positifs inférieurs à n qui sont premiers avecn.

Si k ^ n = 1 d�après le théorème de Bézout, il existe deux entiers u et v tels que ku + nv = 1 doncg = gku+nv = hu1v = hu, par conséquent pour tout entier d on a hud = gd et donc G = hhi. Réciproquementsi G = hhi alors il existe un entier u tel que hu = g donc gku�1 = 1 donc ku�1 est multiple de n donc il existeun entier r tel que ku� 1 = rn et on a donc ku� rn = 1 et donc d�après le théorème de Bézout k ^ n = 1.

Proposition I.6 Soit (G;�) un groupe cyclique de cardinal n, G est isomorphe à (Z=nZ;+).

Démonstration. Soit g un générateur de G et soit

: Z=nZ!G: _x! gx

Si _x = _y alors 9k 2 Z tel que x = y+ kn donc gx = gy+kn = gy (gn)k = gy1k = gy donc l�application estbien dé�nie.

( _x+ _y) = gx+y = gx � gy = ( _x)� ( _y) donc est un morphisme de groupe. est évidemment surjective et comme Card(G) = n = Card(Z=nZ) ; est bijective donc c�est un isomor-

phisme.

Proposition I.7 Soit (G;�) un groupe cyclique, tout sous-groupe de G est cyclique.

Démonstration. Soit H un sous groupe de G et soit g un générateur de G. Soit m = min fk 2 N�; gm 2 Hg.Si H 6= f1g alors l�ensemble précédent est non vide et donc m existe.

On a donc gm 2 H, donc hgmi � H et si 0 < k < m alors gk =2 H. On va montrer que H � hgmi soith 2 H, il existe x tel que h = gx. E¤ectuons la division euclidienne de x par m, on obtient x = dm+ r avec

0 � r < m et donc h = gdm+r = (gm)d � gr donc h��(gm)d

��1= gr 2 H donc r = 0 et gr = 1 et h = (gm)d

donc h 2 hgmi.On va maintenant étudier la structure du groupe (Z=nZ)� en commençant par un cas particulier.

4

II Structure de (Z=pZ)�

Comme précédemment p désigne un nombre premier et donc Z=pZ est un corps. Par conséquent l�équationXd = 1 admet au plus d solutions dans Z=pZ (voir la proposition ??) donc dans (Z=pZ)�, on va donc pouvoirappliquer la proposition suivante :

Proposition II.1 Soit (G;�) un groupe �ni d�ordre n, si pour tout d 2 N si le nombre d�éléments g véri�antgd = 1 est inférieur ou égal à d alors G est cyclique. En particulier (Z=pZ)� est cyclique.

Démonstration. Soit g un élément de G, notons d = ord(g), tous les éléments x de hgi véri�ent xd = 1comme card(hgi) = d l�hypothèse nous permet d�a¢ rmer que tous les éléments d�ordre d sont dans hgi, deplus ce sont les générateurs du groupe cyclique hgi donc d�après la proposition I.5 il y a ' (d) éléments d�ordred.

Donc pour tout diviseur d de n il y a soit 0 soit ' (d) éléments d�ordre d. Notons (d) le nombre d�élémentsd�ordre d de G on a (d) � ' (d) comme (d) = 0 si d - n on aX

d2N� (d) =

Xdjn

(d) = n =Xdjn

' (d)

La dernière égalité est la formule ??. On en déduite que pour tout diviseur d de n on a (d) = ' (d), enparticulier (n) = ' (n) 6= 0 et donc il existe un élément d�ordre n.

En fait le résultat précédent montre que tout groupe multiplicatif �ni inclus dans un corps est cyclique !

III Structure de (Z=prZ)�

On s�intéresse de nouveau à un cas particulier, celui où n est une puissance d�un nombre premier p. Il vafalloir distinguer le cas où p = 2 du cas général comme le montrent les résultats suivants, qu�on ne va pasdémontrer, la preuve étant un peu technique et peu éclairante.

Proposition III.1 Soit p un nombre premier impair, (Z=prZ)� est cyclique pour tout r 2 N�:

Proposition III.2 Pour r 2 N�, le groupe (Z=2rZ)� est isomorphe à

f0g si r = 1

Z=2Z si r = 2

Z=2Z� Z=2r�2Z si r � 3

IV Structure de (Z=nZ)�

On va bien sûr utiliser la décomposition de n en facteurs premiers pour déduire la forme de (Z=nZ)� desrésultats précédents, grâce au théorème des restes chinois :

Théorème IV.1 Soit n = 2rpr11 � � � prkk sa décomposition en facteurs premiers (avec les pi distincts, impairs

et ri > 0). Pour r = 0 ou 1, le groupe (Z=nZ)� se décompose en produit de k groupes cycliques d�ordrerespectifs prk�1k (pk � 1). Pour r = 2, s�ajoute à ces k composantes un facteur isomorphe à Z=2Z. Pour r � 3s�ajoute aux k + 1 composantes déjà citées un facteur isomorphe à Z=2r�2Z.

La question que l�on se pose naturellement est dans quel cas est-ce que (Z=nZ)� est un groupe cyclique ?Pour répondre à cette question on va utiliser le lemme suivant :

Lemme IV.1 Soit G un groupe cyclique de cardinal n et soit H un groupe cyclique de cardinal m alors on a

G�H cyclique, m ^ n = 1

5

Démonstration. On peut supposer que G = (Z=nZ;+) et que H = (Z=mZ;+), si m et n sont premiersentre eux alors le théorème des restes chinois nous montre que G�H est cyclique. D�autre part soit (a; b) unélément de G�H et soit l = ppcm(m;n) on a la = 0 dans Z=nZ et lb = 0 dans Z=mZ donc l: (a; b) = (0; 0)donc l�ordre de (a; b) est un diviseur de l. Si G�H cyclique alors il existe un élément (a; b) de G�H d�ordremn = card(G�H) donc d�après la remarque précédente il faut que l = mn et donc que m ^ n = 1.

Si p et q sont deux nombres premiers, il faut remarquer le cardinal de (Z=prZ)� et le cardinal de (Z=qrZ)�

ne sont pas premiers entre eux, en e¤et ils sont tous les deux pairs sauf si pr = 2 ou qr = 2, et donc le résultatprécédent nous permet d�énoncer :

Proposition IV.1 Le groupe (Z=nZ)� est cyclique si et seulement si n vaut 2 ou 4 ou est de la forme pr ou2pr avec p premier impair et r � 1.

Dé�nition IV.1 Un élément a 2 Z=nZ est dit primitif si c�est un générateur de (Z=nZ)�.

V L�indicateur de Carmichael

Dé�nition V.1 Soit (G;�) un groupe, le plus petit entier e tel que on ait ge = 1 pour tout g 2 G est appelél�exposant de G et est noté � (G).

On applique cette dé�nition à (Z=nZ)� et on obtient

Dé�nition V.2 On appelle indicateur de Carmichael l�application � : N� ! N dé�nie par

� (n) = � ((Z=nZ)�)

Donc 8x 2 (Z=nZ)� ; on a x�(n) = 1 et � (n) est le plus petit entier véri�ant cette propriété.

Remarque V.1 Notons l = ppcmford (g) ; g 2 Gg alors on a évidemment gl = 1 pour tout g 2 G et donc� (G) � l. D�autre part, pour un élément h de G si he = 1 alors ord(h) divise e; donc pour tout h 2 G on aord(h) j � (G) donc on a ppcmford (g) ; g 2 Gg j � (G) donc l � � (G) et �nalement

� (G) = ppcm ford (g) ; g 2 Gg

Notons que l�on connait � (G) dans le cas où G est cyclique, c�est alors le cardinal de G. La propositionsuivante va nous permettre de calculer � (n) pour tout entier n dont on connait la décomposition en facteurspremiers.

Proposition V.1 On a � (2) = 1, � (4) = 2; � (2r) = 2r�2 pour r � 3.Pour p premier impair et r � 1 on a � (pr) = pr�1 (p� 1)Si m � 2 et n � 2 sont premiers entre eux on a � (mn) = ppcm(� (m) ; � (n))

Démonstration. Les deux premiers points sont une conséquence directe du fait que (Z=prZ)� et (Z=2sZ)�

sont cycliques pour r � 1 et s � 3.Montrons le dernier point, soit donc m et n premiers entre eux, on a donc

(Z=mnZ)� ' (Z=nZ)� � (Z=mZ)�

Soit (a; b) 2 (Z=nZ)� � (Z=mZ)� alors (a; b)k =�ak; bk

�donc (a; b)k = (1; 1), k multiple de ord(a) et de

ord(b), k multiple de ppcm() donc l�ordre de (a; b) est . donc on a

� (mn) = ppcm ford ((a; b)) ; (a; b) 2 (Z=nZ)� � (Z=mZ)�g= ppcm fppcm (ord (a) ; ord (b)) ; (a; b) 2 (Z=nZ)� � (Z=mZ)�g= ppcm (ppcm (ord (a) ; a 2 (Z=nZ)�) ;ppcm (ord (b) ; b 2 (Z=mZ)�))= ppcm (� (m) ; � (n))

6

Exemple V.1 � � (24) = ppcm(� (8) ; � (3)) = ppcm(4; 2) = 4. Donc pour tout entier x, x4 � 1 estmultiple de 24.

� � (561) = � (3� 11� 17) = ppcm(2; 10; 16) = 80 donc dans (Z=561Z)� on a x80 = 1 donc x560 = 1 etdonc bien que 561 ne soit pas premier, on a le petit théorème de Fermat dans Z=561Z.

Dé�nition V.3 Si pour tout x 2 (Z=nZ)� on a xn�1 = 1, alors n s�appelle un nombre de Carmichael.

D�après le petit théorème de Fermat, tout nombre premier est un nombre de Carmichael, mais il en existed�autre tel 561. Donnons une caractérisation de ces nombres "pathologiques".

Proposition V.2 Soit n = pr11 � � � prkk sa décomposition en facteurs premiers, alors n est un nombre de

Carmichael si et seulement si on a

ri = 1 pour tout ippcm (p1 � 1; p2 � 1; : : : ; pk � 1) j n� 1

Démonstration. Remarquons tout d�abord que n est de Carmichael si et seulement si � (n) j n�1. En e¤et,si n est de Carmichael n � 1 est multiple de tous les ordres des éléments de (Z=nZ)� donc c�est un multiplede leur ppcm, l�autre sens est évident.

Supposons que ri � 2 alors � (prii ) est multiple de pi donc � (n) également, mais n� 1 n�est pas multiplede pi donc � (n) - n� 1 et n n�est pas de Carmichael. Donc si n est de Carmichael on a n = p1 � � � pk et donc� (n) = ppcm(p1 � 1; p2 � 1; : : : ; pk � 1) d�ou le résultat annoncé.

Voici le tableau des 10 plus petits nombres de Carmichael non-premiers :

i n décomposition � (n)

1 561 3� 11� 17 802 1105 5� 13� 17 483 1729 7� 13� 19 364 2465 5� 17� 29 1125 2821 7� 13� 31 606 6601 7� 23� 41 13207 8911 7� 19� 67 1988 10585 5� 29� 73 5049 15841 7� 31� 73 36010 29341 13� 37� 61 180

7