Algµebrepourcommunicationsnum¶eriques Sections ... · siad=bc. Le symbole R d¶esigne les nombres r¶eels : sans ^etre rigoureux dans la d¶eﬂnition, on peut voir les nombres

ÉCOLE POLYTECHNIQUEFÉDÉRALE DE LAUSANNE

Algebre pour communications numeriques

Sections

Systemes de Communication & Physique

Prof. Eva Bayer FluckigerDr. Philippe Chabloz

octobre 2004

Table des matieres

1 Rappels d’arithmetique 11.1 Nombres et divisibilite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1.1 Definitions et notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.2 Divisibilite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 PGCD et algorithme d’Euclide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2.1 Notions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2.2 Algorithme d’Euclide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2.3 Identite de Bezout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Nombres premiers et factorisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3.1 Factorisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3.2 Infinite de nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3.3 Divisibilite et factorisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Congruences et classes de congruence 92.1 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.1.1 Definitions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.1.2 Changement de modulus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2 Classes de congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2.1 Unites dans Z/mZ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.2.2 Indicatrice d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.2.3 Le cas Z/6Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3 Anneaux et corps 173.1 Notions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.2 Exemple : calcul d’un inverse dans Z/mZ . . . . . . . . . . . . . . . . . . . . . . . . 203.3 Homomorphismes d’anneaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.4 Ideal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.5 Factorisation des homomorphismes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4 Theoremes d’Euler et de Fermat 27

5 Les groupes 295.1 Notions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295.2 Sous-groupe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

5.2.1 Groupe cyclique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305.3 Homomorphisme de groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325.4 Table de multiplication d’un groupe . . . . . . . . . . . . . . . . . . . . . . . . . . . 335.5 Exemple d’un groupe non abelien : S3 . . . . . . . . . . . . . . . . . . . . . . . . . . 33

6 Le theoreme des restes chinois 356.1 Bases theoriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356.2 Restes chinois : deux algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

6.2.1 Premiere methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366.2.2 Seconde methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376.2.3 Une application : la fonction indicatrice d’Euler . . . . . . . . . . . . . . . . . 38

iii

iv TABLE DES MATIERES

7 Anneau de polynomes et corps finis 417.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417.2 Anneau de polynomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

7.2.1 Division euclidienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417.2.2 Congruences modulo un polynome . . . . . . . . . . . . . . . . . . . . . . . . 447.2.3 Classes de congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

7.3 Theoreme des restes chinois . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467.4 Corps finis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

7.4.1 Existence et unicite des corps finis . . . . . . . . . . . . . . . . . . . . . . . . 477.4.2 Isomorphismes de Frobenius . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Bibliographie 51

Index 52

Index des notations 53

Glossaire 54

Chapitre 1

Rappels d’arithmetique

1.1 Nombres et divisibilite

1.1.1 Definitions et notations

Nous commencons par fixer quelques definitions et notations sans doute connues du lecteur.Nous noterons N l’ensemble des entiers naturels :

1, 2, 3, 4, 5, . . . ,

Nous designerons par Z l’ensemble des entiers (ou entiers relatifs)

. . . ,−3,−2,−1, 0, 1, 2, 3, 4, . . .

obtenus a partir de N en rajoutant le zero et les nombres negatifs.Les nombres rationnels seront notes Q. C’est l’ensemble des fractions

a

b

ou a et b sont des nombres entiers, b est non nul et deux fractions abet c

dsont egales si et seulement

si ad = bc.Le symbole R designe les nombres reels : sans etre rigoureux dans la definition, on peut voirles nombres reels comme les nombres dont le developpement decimal est infini et quelconque.Geometriquement, on peut se representer les nombres reels comme une droite. L’ensemble R contient,bien entendu, les nombres rationnels mais aussi

√2 ou π qui sont des nombres reels non rationnels.

Enfin, les nombres complexes seront notes C. Ce sont les nombres de la forme a + bi avec a, b ∈ Ret i2 = −1.On a les inclusions suivantes :

N ⊂ Z ⊂ Q ⊂ R ⊂ C.

1.1.2 Divisibilite

Definition 1.1 (Divisibilite). Soient a et b deux entiers naturels. On dit que b est divisible par as’il existe un entier naturel q tel que b = aq. On dira egalement que a est un diviseur de b ou encoreque b est un multiple de a. On le notera

a|b.

Exemple 1.2. Les diviseurs de 24 sont les entiers 1,2,3,4,6,8,12 et 24 alors que 23 n’a que deuxdiviseurs : 1 et 23.

Definition 1.3 (Nombre premier). Un entier naturel est dit premier s’il a exactement deuxdiviseurs, a savoir 1 et lui-meme.

1

2 CHAPITRE 1. RAPPELS D’ARITHMETIQUE

Exemple 1.4. Les entiers naturels 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 sont premiers et ce sont les seulsnombres premiers inferieurs ou egaux a 30. Nous verrons plus loin qu’il y a une infinite de nombrespremiers.

Remarque 1.5. Si n > 1 est un entier non premier, alors il possede au moins 3 diviseurs distincts.Il faut cependant preter attention au cas du nombre n = 1 qui n’est pas premier mais qui ne possedequ’un diviseur a savoir lui-meme.

Lorsque a n’est pas divisible par b, on peut neanmoins faire une division avec reste, appelee divisioneuclidienne :

Theoreme 1.6 (Division euclidienne). Soient a et b deux nombres entiers ≥ 0. Alors il existedeux nombres entiers q ≥ 0 et r avec 0 ≤ r < a tel que b = aq+r. Le nombre q est appele le quotientet le nombre r est le reste.

On remarque que b est divisible par a si et seulement si r = 0.

Demonstration : Considerons le sous-ensemble de N constitue des entiers b − ax avec x ≥ 0 etb− ax ≥ 0. C’est un sous-ensemble non vide car b en fait partie (b = b− a · 0). Il contient donc unplus petit element que nous notons r. On a alors r = b − aq pour un certain q. Il reste a montrerque r < a. Si ce n’est pas le cas, on a alors r − a ≥ 0 et donc

r − a = b− aq − a = b− (q + 1)a ≥ 0.

Mais alors r − a est encore dans le sous-ensemble considere ce qui contredit le fait que r en soitle plus petit element. On a donc trouve deux entiers naturels q et r qui satisfont les conditions dutheoreme.

1.2 PGCD et algorithme d’Euclide

1.2.1 Notions de base

Etant donnes deux nombres entiers a et b, nous pouvons nous demander quels sont les nombres quisont diviseurs de a et de b. On les appelle les diviseurs communs de a et b. Par exemple, si l’on prenda = 24 et b = 18, on constate que les diviseurs communs sont 2, 3 et 6.

Le plus grand des diviseurs communs joue un role important :

Definition 1.7 (Pgcd de deux nombres entiers). Soient a et b des entiers naturels. L’entiernaturel d est appele le plus grand commun diviseur (pgcd) de a et b s’il satisfait les deux proprietessuivantes :

(i) d|a et d|b ;(ii) si d′|a et d′|b alors d′ ≤ d pour tout d′ ∈ N.

Le pgcd de a et b est note (a, b).

Dans l’exemple ci-dessus, on a (18, 24) = 6.On peut definir de la meme maniere le pgcd de n nombres a1, a2, . . . , an qui sera note (a1, a2, . . . , an).Par exemple, on a (15, 18, 24) = 3 et (15, 16) = 1.

Definition 1.8. On dit que deux nombres entiers non negatifs a et b sont premiers entre eux si leurpgcd est 1, autrement dit si (a, b) = 1. On dira que les nombres a1, a2, . . . an sont premiers deux adeux si (ai, aj) = 1 pour i 6= j.

Remarquons que si les nombres a1, a2, . . . , an sont premiers deux a deux, alors on a (a1, a2, . . . , an) =1. Mais la reciproque n’est pas vraie. En effet, on a (15, 3, 5) = 1 mais 3 et 15 ne sont pas premiersentre eux car (3, 15) = 3.

1.2. PGCD ET ALGORITHME D’EUCLIDE 3

1.2.2 Algorithme d’Euclide

Nous allons donner maintenant un algorithme qui permet de calculer le pgcd de deux nombres entiers.

Algorithme d’Euclide : Soient a et b deux nombres entiers naturels. On suppose que b ≥ a. Oncalcule alors (a, b) en faisant des divisions euclidiennes successives comme suit :

b = aq1 + r1

a = r1q2 + r2

r1 = r2q3 + r3

...

rn−2 = rn−1qn + rn

rn−1 = rnqn+1 + 0.

L’algorithme s’arrete lorsque le reste vaut 0 et le dernier reste non nul (dans l’algorithme ci-dessus :rn) est le pgcd de a et b.

Exemple 1.9. Calculons le pgcd de 24 et de 18.

24 = 18 + 6

18 = 6 · 3 + 0.

On a donc (18, 24) = 6.

Exemple 1.10. Trouvons le pgcd de 13 et 18 :

18 = 13 + 5

13 = 5 · 2 + 3

5 = 3 + 2

3 = 2 + 1

2 = 1 · 2 = 0.

On a ainsi (13, 18) = 1.

1.2.3 Identite de Bezout

L’algorithme d’Euclide nous permet egalement de trouver une identite de Bezout entre les nombresa, b et leur pgcd :

Theoreme 1.11 (Identite de Bezout). Soient a et b deux nombres entiers naturels et d = (a, b)leur pgcd. Alors il existe des entiers (pas necessairement positifs) r et s tels que

d = as+ br.

Reciproquement, si at+ bu = d′ pour des entiers t et u, alors d divise d′.

La demonstration de ce theoreme est une consequence de l’algorithme d’Euclide. Nous n’allons pasfaire une demonstration rigoureuse mais l’illustrer sur un exemple. Nous reprenons a = 13 et b = 18.Le calcul du pgcd a l’aide de l’algorithme d’Euclide (voir l’exemple 1.10 ci-dessus) nous permetd’ecrire les equations suivantes :

1 = 3− 2

= 3− (5− 3) = 2 · 3− 5

= 2(13− 2 · 5)− 5 = 2 · 13− 5 · 5= 2 · 13− 5(18− 13)

= 7 · 13− 5 · 18.


Ainsi on a (13, 18) = 1 et 1 = 7 · 13− 5 · 18. On a donc s = 7 et r = −5.

Nous demontrons la reciproque : soit at+ bu = d′ une egalite d’entiers. Alors, si d = (a, b), on a d|aet d|b, c’est-a-dire que a = dm et b = dn. Mais alors d′ = dmt + dnu = d(mt + nu) ce qui montreque d divise d′.

Exemple 1.12. Calculons une identite de Bezout pour les nombres 121 et 365. On commence parcalculer leur pgcd a l’aide de l’algorithme d’Euclide.

365 = 121 · 3 + 2

121 = 2 · 60 + 1.

Ainsi (121, 365) = 1. On remonte maintenant l’algorithme en isolant le reste a chaque fois pourtrouver l’identite de Bezout.

1 = 121− 2 · 60= 121− 60 · (365− 3 · 121)= 181 · 121− 60 · 365.

L’identite cherchee est alors 1 = 181 · 121− 60 · 365.

L’identite de Bezout nous permet de montrer quelques proprietes du pgcd.

Corollaire 1.13. Tout diviseur commun de a et b divise leur pgcd. Autrement dit,

e|a et e|b =⇒ e|(a, b).

Demonstration : Soit ar + bs = d une identite de Bezout avec d = (a, b). Par hypothese, on aa = em et b = en pour des entiers n et m. On obtient alors

emr + ens = e(mr + ns) = d

ce qui montre que e divise d.

Corollaire 1.14. Si a divise bc et (a, b) = 1 alors a divise c.

Demonstration : On a une identite de Bezout as+ br = 1. En multipliant cette egalite par c, ontrouve

asc+ bcr = c.

Comme a divise bc, a divise bcr. Mais a divise egalement asc ce qui montre que a divise asc+bcr = c.

1.3 Nombres premiers et factorisation

Nous avons deja vu la definition d’un nombre premier. En fait, ces nombres jouent un role preponde-rant en arithmetique comme nous allons le voir dans cette section. D’abord nous allons montrer quechaque nombre entier s’ecrit d’une unique facon comme le produit de nombres premiers. Puis nousverrons qu’il existe une infinite de nombres premiers.

1.3.1 Factorisation

Theoreme 1.15 (Theoreme fondamental de l’arithmetique). Tout nombre entier > 1 s’ecritcomme un produit de nombres premiers.

1.3. NOMBRES PREMIERS ET FACTORISATION 5

Demonstration : On va demontrer ce resultat par l’absurde. Supposons qu’il existe au moins unnombre > 1 qui ne s’ecrit pas comme le produit de nombres premiers et choisissons le plus petitayant cette propriete. Notons-le a. Ce nombre n’est donc pas premier puisqu’il n’est pas le produitde nombres premiers. Comme, de plus, a > 1, on a a = bc ou b et c sont des diviseurs stricts de a,c’est-a-dire que b < a et c < a. Mais alors, par choix de a, les nombres b et c peuvent s’ecrire commeun produit de nombres premiers. Ainsi b = p1p2 · · · pn et c = q1q2 · · · qm ou les pi et les qj sont desnombres premiers (pas necessairement distincts). Mais comme a = bc, on a

a = p1p2 · · · pnq1q2 · · · qm

ce qui contredit l’hypothese de depart.

Pour prouver l’unicite de la decomposition en premiers, nous avons besoin du lemme suivant :

Lemme 1.16. Soit p un nombre premier. Si p divise le produit ab, alors p divise a ou b.

Demonstration Comme p est premier, on a soit p|a ou (p, a) = 1. Mais par le corollaire 1.14, si(p, a) = 1 et p|ab alors p divise b. En conclusion, p divise a ou p divise b

Remarque 1.17. On peut montrer en appliquant n fois le lemme precedent, que si un nombrepremier p divise le produit a1a2 · · · an alors il divise au moins l’un des ai.

Cette remarque nous permet de montrer que la decomposition d’un nombre en produit de nombrespremiers est unique (a l’ordre pres) :

Theoreme 1.18. Si m = p1p2 · · · pn = q1q2 · · · qm ou les pi et les qj sont des nombres premiers,alors m = n et, pour tout 1 ≤ i ≤ n, il existe un j tel que pi = qj. Autrement dit, la factorisationen produit de nombres premiers est unique a l’ordre pres.

Demonstration : Sip1p2 · · · pn = q1q2 · · · qm (1.1)

alors p1 divise q1q2 · · · qm. Par la remarque ci-dessus, ceci implique que p1 divise l’un des qj . Maiscomme ils sont tous les deux premiers, ceci implique que p1 = qj pour un certain j. On peut alorssimplifier l’egalite (1.1) a gauche par p1 et a droite par qj . En appliquant ce procede iterativement,on arrive a la conclusion voulue.

En general, on ecrira donc le nombre a comme

a = pe11 pe22 · · · pen

n

ou les pi sont des nombres premiers distincts et les ei sont des nombres ≥ 1. Dire que la factorisationest unique revient a dire que les pi et les ei sont uniquement determines a l’ordre pres. Si l’onconvient de plus que p1 < p2 < · · · < pn alors l’unicite est complete.

Remarque 1.19. Il peut arriver pour des raisons de commodite que l’on permette que certains desei soient nuls. Ceci veut dire que le nombre en question n’est pas divisible par les nombres premiersdont les exposants sont nuls mais que l’on veut les faire apparaıtre neanmoins. Ce sera par exemplele cas dans le paragraphe 1.3.3.

Exemple 1.20. On a les factorisation suivantes :

24 = 23 · 375 = 3 · 52

126 = 2 · 32 · 7.


1.3.2 Infinite de nombres premiers

Theoreme 1.21 (Theoreme d’Euclide). Il y a une infinite de nombres premiers.

Demonstration : Supposons qu’il existe un nombre fini de premiers, disons p1 < p2 < · · · < pn etconsiderons le nombre

m = p1p2 · · · pn + 1.

Comme il est strictement plus grand que pn, il ne peut pas etre premier. Il est donc divisible parun nombre premier qui est necessairement un des pi. Mais alors ce nombre premier pi divise m etdivise p1p2 · · · pn. Il divise donc leur difference qui est 1, ce qui est absurde. Le nombre de premiersest donc infini.

1.3.3 Divisibilite et factorisation

On peut exprimer la notion de divisibilite en fonction de la factorisation en nombres premiers. Soienta et b deux nombres entiers et p1, p2, . . . , pn l’ensemble des premiers qui divise a ou b. On a alors

a = pe11 pe22 . . . pen

n

et (1.2)

b = pf11 pf22 . . . pfn

n

ou certains des ei et des fj peuvent etre nuls. On a

Theoreme 1.22. Soient a et b comme ci-dessus. Alors a divise b si et seulement si ei ≤ fi pourtout i = 1, . . . , n.

Demonstration : Si a divise b alors on peut ecrire b = am pour un certain m. En factorisant enproduit de premiers les deux membres de l’egalite, on trouve

b = pf11 pf22 . . . pfn

n = pe11 pe22 . . . pen

n · q1 . . . qr︸︷︷︸

=m

= am.

Comme la factorisation est unique, les premiers qui sont a droite doivent se retrouver a gauche a lameme puissance. Ainsi ei ≤ fi.Reciproquement, si ei ≤ fi pour tout i = 1, . . . , n, on pose gi = fi − ei ≥ 0 pour tout i et

m = pg11 pg22 · · · pgn

n .

On a alors am = b ce qui montre que a divise b.

On peut utiliser ce theoreme pour trouver le pgcd de deux nombres :

Corollaire 1.23. Soient a et b comme ci-dessus. Alors leur pgcd est le nombre

d = phi

1 ph2

2 · · · phnn

ou hi = min(ei, fi) pour tout i = 1, . . . , n.

Exemple 1.24. Calculons le pgcd de 120 et de 105. On factorise d’abord chaque nombre :

120 = 23 · 3 · 5105 = 3 · 5 · 7.

On peut reecrire ceci comme suit :

120 = 23 · 31 · 51 · 70 105 = 20 · 3 · 5 · 7.

Ainsi le pgcd de 105 et 120 est 20 · 3 · 5 · 70 = 3 · 5 = 15.

1.3. NOMBRES PREMIERS ET FACTORISATION 7

On peut definir une notion duale a celle de pgcd. Considerons deux nombres naturels a et b. On diraque c est un multiple commun de a et b si am = c et bn = c pour des entiers m et n non nuls. Parexemple, le produit ab est clairement un multiple commun de a et de b. On peut alors considererle plus petit multiple commun de a et de b que nous noterons [a, b]. Ceci donne lieu a la definitionsuivante :

Definition 1.25 (Plus petit commun multiple). L’entier naturel m est le plus petit communmultiple (ou ppcm de a et b) s’il satisfait les deux proprietes suivantes :

(i) a|m et b|m ;

(ii) si n est un multiple commun de a et b alors m ≤ n.

Le ppcm de a et b est note [a, b].

Comme pour le pgcd, l’on peut trouver le ppcm de deux nombres en fonction de leur factorisation.

Theoreme 1.26. Soient a et b deux entiers naturels comme en (1.2). Alors le ppcm de a et b estle nombre

m = pk1

1 pk2

2 · · · pknn

ou ki = max(ei, fi) pour tout i = 1, . . . , n.

Demonstration : C’est une consequence directe du theoreme 1.22.

Le corollaire 1.23 et le theoreme 1.26 permettent d’obtenir une relation entre le pgcd et le ppcm :

Corollaire 1.27. Soient a et b deux entiers. Alors

a · b = [a, b] · (a, b).

On a montre que tout diviseur commun de deux nombres divise leur pgcd. On peut montrer unresultat analogue pour le ppcm :

Theoreme 1.28. Soient a et b deux nombres naturels et m leur ppcm. Si n est un multiple de a etde b, alors m divise n.

Demonstration : Par hypothese, a est un diviseur de n et de m. En appliquant le theoreme 1.13,on obtient que a divise (m,n). De maniere identique, on a que b divise (m,n). Mais alors (m,n)est un multiple commun de a et b et de ce fait doit etre plus grand que leur ppcm qui est m. Mais(m,n) ≥ m implique que (m,n) = m et donc que m divise n.

En d’autres termes, la condition (ii) dans la definition du ppcm devient :

(ii) si n est un multiple commun de a et b alors le [a, b] divise n.

Chapitre 2

Congruences et classes de

congruence

2.1 Congruences

2.1.1 Definitions de base

La notion de divisibilite introduite dans le chapitre precedent va nous permettre de definir unerelation d’equivalence sur les entiers.

Definition 2.1 (Congruence modulo m). Soient a, b et m des entiers avec m > 1. On dit quea et b sont congrus modulo m si m divise a − b, ou de maniere equivalente, si b = a + km pour uncertain entier k. On le notera

a ≡ b (mod m).

Remarquons que a ≡ 0 (mod m) est equivalent a m|a.L’entier m dans la definition precedente est appele le modulus (pluriel : moduli).

Exemple 2.2.

13 ≡ 3 ≡ 43 (mod 5)

41 ≡ 5 ≡ 17 (mod 6)

35 ≡ −3 ≡ 11 (mod 2)

L’ensemble de tous les entiers qui sont congrus a b modulo m est l’ensemble {b+ km | k ∈ Z}. Cecinous permet de demontrer le resultat suivant :

Theoreme 2.3. Soit m un entier > 1. Alors tout nombre entier a est congru modulo m a un et unseul entier r de l’ensemble {0, 1, 2, . . . ,m − 1}. De plus, cet entier r est exactement le reste de ladivision de a par m. En d’autres termes, si 0 ≤ r < m, alors

a ≡ r (mod m)

si et seulement si a = qm+ r ou q est le quotient de a par m et r le reste.

Demonstration : C’est une consequence immediate de la definition de la congruence et de ladivision euclidienne.

La relation de congruence ≡ est une relation d’equivalence, en d’autres termes :

Theoreme 2.4. Soient a, b, c et m des entiers avec m > 1. Alors

(i) a ≡ a (mod m)

(ii) si a ≡ b (mod m) alors b ≡ a (mod m)

(iii) si a ≡ b (mod m) et b ≡ c (mod m), alors a ≡ c (mod m).

9

10 CHAPITRE 2. CONGRUENCES ET CLASSES DE CONGRUENCE

Demonstration : Les parties (i) et (ii) sont evidentes. Nous demontrons (iii). Les hypothesesimpliquent que b = a+ km et c = b+ lm. Mais alors

c = a+ km+ lm = a+ (k + l)m

ce qui montre que a et c sont congrus modulo m.

La relation de congruence ≡ est compatible avec la somme et le produit :

Theoreme 2.5. Soient a, b, a′, b′ et m > 1 des entiers tels que a ≡ b (mod m) et a′ ≡ b′ (mod m).Alors

(a) a+ a′ ≡ b+ b′ (mod m) ;

(b) aa′ ≡ bb′ (mod m).

Demonstration : On a a = b+ km et a′ = b′ + lm par hypothese. Mais alors,

a+ a′ = b+ b′ + (l + k)m

ce qui demontre (a). On a egalement

aa′ = bb′ + blm+ b′km+ klm2 = bb′ + sm

ce qui demontre (b).

La relation ≡ se comporte sur de nombreux points comme la relation d’egalite =. Neanmoins, unepropriete de la relation d’egalite n’est plus vraie pour celle de congruence, a savoir la simplification :si ab ≡ ac (mod m), on n’a pas necessairement b ≡ c (mod m). Par exemple 2 · 1 ≡ 2 · 3 (mod 4)mais 1 6≡ 3 (mod 4).De meme, 4 · 3 ≡ 4 · 6 (mod 12) mais 3 et 6 ne sont pas congrus modulo 12. Nous verrons plus loinquelle regle utiliser lors des simplifications.

2.1.2 Changement de modulus

Jusqu’ici, nous avons vu des proprietes des congruences faisant intervenir un seul modulus. Nousallons maintenant etudier le comportement de la relation de congruence lors d’un changement demodulus.

Theoreme 2.6. (i) Si a ≡ b (mod m) et d divise m, alors a ≡ b (mod d).

(ii) Si a ≡ b (mod r) et a ≡ b (mod s) alors a et b sont congrus modulo [r, s].

Demonstration : Le point (i) est evident. Nous demontrons (ii). Par hypothese, b − a est unmultiple de r et de s. Par le theoreme 1.28, b− a est un multiple du ppcm de r et s ce qui demontre(ii).

Nous avons vu au paragraphe 2.1.1 que la simplification n’est pas possible avec les congruences.Neanmoins, on peut utiliser le resultat suivant

Theoreme 2.7. Si ra et rb sont congrus modulo m, alors a et b sont congrus modulo m(r,m) .

Demonstration : Posons d = (m, r). Par definition du pgcd, on a(m

d,r

d

)

= 1.

On a alors une identite de Bezout :sm

d+ t

r

d= 1. (2.1)

Maintenant, l’hypothese implique que ra− rb = km. Divisant par d, on obtient

ar

d− b

r

d= k

m

d. (2.2)

2.2. CLASSES DE CONGRUENCE 11

Multipliant l’equation (2.2) par t et utilisant l’equation (2.1), on trouve

atr

d− bt

r

d= kt

m

d

a(1− sm

d)− b(1− s

m

d) = kt

m

d

a− b = k′m

d

ou k′ = kt+ as− bs. Ceci prouve que a et b sont congrus modulo md.

Exemple 2.8. L’egalite 24 ≡ 84 (mod 15) implique (en posant r = 12) que 2 ≡ 7 (mod 15(15,12) = 5).

Mentionnons explicitement deux cas particuliers du theoreme ci-dessus. Ce sont les situations ou(m, r) = 1 et ou (m, r) = r.

Corollaire 2.9. (i) Si ra ≡ rb (mod m) et (m, r) = 1, alors a ≡ b (mod m) ;

(ii) Si ra ≡ rb (mod rm), alors a ≡ b (mod m).

2.2 Classes de congruence

Dans la section precedente, nous avons vu que la relation congrus modulo m est une relationd’equivalence. On peut alors partitionner l’ensemble Z en sous-ensembles - appeles classes de congru-ence modulo m - definis par la propriete que deux elements a et b de Z sont dans la meme classe siet seulement si a ≡ b (mod m).Ces classes pourront a leur tour etre additionnees et multipliees et seront donc considerees commedes “nouveaux nombres”. L’ensemble des classes modulo m est denote Z/mZ.Le but de cette section est de preciser tout cela. Nous commencons par un exemple.

Exemple 2.10. Soit m = 3. On divise l’ensemble des entiers en classes de congruence modulo 3.Comme tout nombre est congru a 0, a 1 ou a 2 (voir theoreme 2.3), il y a trois classes qui sont :

{. . . ,−9,−6,−3, 0, 3, 6, 9, 12, . . .}{. . . ,−8,−5,−2, 1, 4, 7, 10, 13, . . .}{. . . ,−7,−4,−1, 2, 5, 8, 11, . . .}

Le plus petit nombre non negatif de la premiere classe est 0, celui de la deuxieme est 1 et celui dela derniere est 2. Ainsi l’on notera ces trois classes respectivement [0]3, [1]3 et [2]3, le chiffre 3 enindice indiquant le modulus.Il est interessant de noter que si l’on prend un nombre quelconque de la premiere classe et unnombre quelconque de la deuxieme, alors leur somme est toujours dans la deuxieme classe. Parexemple, 0 + 1 = 1, 9 − 5 = 4 et 12 + 7 = 19 sont tous dans la deuxieme classe. Il en est de memesi l’on prend deux nombres quelconques dans [1]2 : leur somme est toujours dans la classe [2]3. Cecise generalise et permet de definir une somme sur les classes modulo 3 en posant

[0]3 + [0]3 = [0]3 [0]3 + [1]3 = [1]3

[0]3 + [2]3 = [2]3 [1]3 + [1]3 = [2]3

[1]3 + [2]3 = [0]3 [2]3 + [2]3 = [1]3

Ceci n’est qu’une consequence du theoreme 2.5 (a).La partie (b) de ce meme theoreme 2.5 nous permet de definir un produit sur ces 3 classes decongruences en posant

[0]3 · [0]3 = [0]3 [0]3 · [1]3 = [0]3

[0]3 · [2]3 = [0]3 [1]3 · [1]3 = [1]3

[1]3 · [2]3 = [2]3 [2]3 · [2]3 = [1]3

Cette definition est coherente car, par exemple, −4 · 2 = −8 et 5 · 8 = 40 sont tous deux dans laclasse [1]3.


Nous allons maintenant definir les classes de congruence pour tout modulus m. Fixons donc unm > 1.

Definition 2.11 (Classes de congruences). Soit a un entier. La classe de congruence de a (modm) est l’ensemble des entiers congrus a a modulo m. Cette classe est notee [a]m.

On deduit de la definition et du theoreme 2.4 les deux proprietes suivantes :

(i) Le nombre b est dans la classe [a]m si et seulement si a ≡ b (mod m).

(ii) Les classes [a]m et [b]m sont egales si et seulement si a ≡ b (mod m).

Le theoreme 2.3 permet d’affirmer qu’il y a exactement m differentes classes de congruence modulom, a savoir [0]m, [1]m, . . ., [m− 1]m.

Definition 2.12 (Representant d’une classe). Un entier a qui est dans une classe de congruence(mod m) est appele un representant de cette classe.

Exemple 2.13. Les nombres −3, 0, 33 sont tous des representants de la classe (mod 3)

[0]3 = {. . . ,−9,−6,−3, 0, 3, 6, 9, 12, . . .}.

Les nombres 45 et 21 sont deux representants de la classe [9]12.

Il est clair, vu la definition et les exemples ci-dessus, que deux representants a et b de la meme classe(mod m) satisfont a ≡ b (mod m).Nous allons maintenant pouvoir definir une addition et une multiplication sur les classes de congru-ence. Pour definir la somme de deux classes [a]m et [b]m, il suffit de prendre un representant dechaque classe, de faire leur somme et de prendre la classe de congruence du resultat. Le theoreme2.5 nous permet d’affirmer que cette definition est correcte et que le resultat ne depend pas desrepresentants choisis. En termes mathematiques :

[a]m + [b]m = [a+ b]m.

Par exemple, si m = 3, [1]3 + [2]3 = [1 + 2]3 = [3]3 = [0]3 et l’on retrouve le resultat de l’exemple2.10 ci-dessus.Si m = 12, alors [4]12 + [11]12 = [15]12 = [3]12.On definit le produit de deux classes de maniere analogue, en posant

[a]m · [b]m = [ab]m.

Ceci est bien defini grace, a nouveau, au theoreme 2.5.Par exemple, dans Z/3Z, on a [2]3 · [2]3 = [4]3 = [1]3.Si m = 12, on a, par exemple, [5]12 · [9]12 = [45]12 = [9]12. Si l’on prend d’autres representants, parexemple 17 et −3, on obtient le meme resultat car [−51]12 = [9]12.Par definition de la somme et du produit, on constate que la classe de 0 est l’element neutre pourl’addition, i.e.

[a]m + [0]m = [a]m pour tout a ∈ Z et tout m ∈ N

et la classe de l’entier 1 est l’element neutre pour la multiplication :

[a]m · [1]m = [a]m pour tout a ∈ Z et tout m ∈ N.

2.2.1 Unites dans Z/mZ

Lorsque l’on a un ensemble muni d’une multiplication et d’un element identite 1, on peut se demanderquels sont les elements de cet ensemble qui possede un inverse. En d’autres termes, quels sont les atels qu’il existe b avec a · b = b · a = 1 ? Si un tel b existe, il est appele l’inverse de a. Il est alorsunique car si ab = 1 = ba et ab′ = 1, alors en multipliant la derniere equation par b, on obtientbab′ = b d’ou b′ = b.Un element qui possede un inverse est appele une unite.Dans Z, il n’ y a que 1 et −1 qui ont des inverses. En effet 1 · 1 = 1 et −1 · −1 = 1. Mais pour toutautre entier, il n’existe pas d’inverse dans Z. Il faut se placer dans Q pour que tout nombre non nulpossede un inverse.


Quand est-il maintenant de Z/mZ ? Nous avons vu que cet ensemble possede une multiplication etun element identite 1 (en fait c’est un anneau au sens du chapitre suivant). On peut donc definir lanotions d’unites :

Definition 2.14 (Unites de Z/mZ). Un element [a]m de Z/mZ est une unite s’il existe un element[b]m ∈ Z/mZ tel que [a]m[b]m = [1]m.

Quelles sont alors les unites de Z/mZ ?Si l’on prend Z/3Z, on constate que tous ses elements non nuls sont des unites car [1]3 · [1]3 = [1]3et [2]3 · [2]3 = [1]3.Si l’on prend m = 12, on observe que [1], [5], [7] et [11] sont les seules unites. Leurs inverses sontrespectivement [1], [5], [7] et [11] c’est-a-dire que toutes les unites sont leur propre inverse. En re-vanche [3]12 n’est pas une unite car s’il possedait un inverse [a] on aurait [a] · [3] · [4] = [4] mais aussi[a] · [3] · [4] = [a] · [12] = [0] ce qui est une contradiction.Le theoreme suivant permet de caracteriser les classes (mod m) qui sont des unites dans Z/mZ.

Theoreme 2.15. Soit [a] un element de Z/mZ. Alors [a] est une unite si et seulement si (a,m) = 1.

Demonstration : Supposons d’abord que (a,m) = 1. Alors par Bezout on a une identite

as+mr = 1.

Autrement dit, as est congru a 1 modulo m. Mais ceci est equivalent a dire que [a][s] = [1] ce quimontre que [a] est une unite.Reciproquement, si [a] est une unite, ceci implique qu’il existe une classe [s] telle que [a][s] = [1].Ceci est equivalent a dire que as est congru a 1 (mod m) ou encore que as−1 = km. Par le theoreme1.11, ceci implique que (a,m) = 1.

2.2.2 Indicatrice d’Euler

Definition 2.16 (Indicatrice d’Euler). Le nombre d’entiers naturels a < m qui sont premiers am est note ϕ(m). La fonction

ϕ : N −→ N

s’appelle l’ indicatrice d’Euler.

Exemple 2.17. On a

ϕ(1) = 1

ϕ(2) = 1

ϕ(3) = 2

ϕ(4) = 2

ϕ(5) = 4

ϕ(6) = 2

ϕ(7) = 6

ϕ(8) = 4

...

ϕ(p) = p− 1 pour tout premier p

Corollaire 2.18. Le nombre d’unites dans Z/mZ est egal a ϕ(m).

Nous donnons quelques resultats sur la fonction ϕ.

Theoreme 2.19. Soient m,n ∈ N tels que (m,n) = 1. Alors

ϕ(mn) = ϕ(m) · ϕ(n).


La demonstration de ce theoreme se trouve au chapitre 6.

Theoreme 2.20. Soit p un nombre premier. Alors

ϕ(pk) = (p− 1) · pk−1

pour tout entier k ∈ N.

Demonstration : Par definition, ϕ(pk) est le nombre d’entiers n satisfaisant 1 ≤ n < pk et quisont premiers a pk. Comptons d’abord le nombre d’entiers naturels m < pk qui ne sont pas premiersa pk. Comme p est un premier, il faut que de tels m soient multiples de p. Les entiers

p, 2p, 3p, 4p, . . . , (pk−1 − 1)p

sont donc les seuls entiers naturels < pk qui ne sont pas premiers a pk. Il y en a exactement pk−1−1.Il y a donc

pk − 1− (pk−1 − 1) = pk − pk−1 = (p− 1)pk−1

entiers naturels < pk qui sont premiers a pk d’ou la valeur de ϕ(pk).

Les deux theoremes precedents permettent de calculer ϕ(n) pour n’importe quel entier n en lefactorisant en produit de premiers. Si

n = pe11 · pe22 · · · perr

avec ei ≥ 1 pour tout i, alors

ϕ(n) = (p1 − 1)pe1−11 · · · (pr − 1)per−1r .

Exemple 2.21. On a

ϕ(12) = ϕ(22) · ϕ(3) = 2 · 2 = 4

ϕ(60) = ϕ(5) · ϕ(12) = 4 · 4 = 16

ϕ(128) = ϕ(27) = 26 = 64

ϕ(81) = ϕ(34) = 2 · 33 = 54

ϕ(1000) = ϕ(23) · ϕ(53) = 22 · 4 · 52 = 400

Nous terminons ce chapitre en traitant l’exemple Z/6Z.

2.2.3 Le cas Z/6Z

Comme ensemble, on aZ/6Z = {[0], [1], . . . , [5]}.

(nous omettons le 6 en indice).Voici la table de multiplication de Z/6Z :

[0] [1] [2] [3] [4] [5]

[0] [0] [0] [0] [0] [0] [0]

[1] [0] [1] [2] [3] [4] [5]

[2] [0] [2] [4] [0] [2] [4]

[3] [0] [3] [0] [3] [0] [3]

[4] [0] [4] [2] [0] [4] [2]

[5] [0] [5] [4] [3] [2] [1]


Les unites sont donc [1] et [5]. On a bien ϕ(6) = 2.

Chapitre 3

Anneaux et corps

Ce chapitre contient des notions plus abstraites qui permettront de demontrer des resultats generali-sant ceux obtenus pour les entiers. La notion d’anneau nous permettra d’appliquer a l’ensemble despolynomes les techniques utilisees pour les entiers.

3.1 Notions de base

Definition 3.1 (Anneau). Un ensemble R muni de deux operations internes + et · et de deuxelements particuliers distincts 0 et 1 est un anneau s’il satisfait les proprietes suivantes :

(i) (a+ b) + c = a+ (b+ c) pour tout a, b, c ∈ R (associativite de l’addition)

(ii) a+ b = b+ a pour tout a, b ∈ R (commutativite de l’addition)

(iii) a+ 0 = 0 + a = a pour tout a ∈ R (0 est l’element neutre pour l’addition)

(iv) pour tout a ∈ R, il existe un element −a ∈ R tel que a+ (−a) = 0 (existence de l’oppose)

(v) (a · b) · c = a · (b · c) pour tout a, b, c ∈ R (associativite de la multiplication)

(vi) a · 1 = 1 · a = a pour tout a ∈ R (1 est l’element identite)

(vii) a · (b+ c) = a · b+ a · c pour tout a, b, c ∈ R (distributivite de l’addition par rapport a lamultiplication)

Un anneau sera note (R,+, ·, 0, 1) en toute rigueur pour bien specifier les deux operations et les deuxelements distingues. Mais s’il n’y a aucune ambiguıte, il sera simplement note R.

Notation : Par la suite, il sera souvent note ab au lieu de a · b et a− b au lieu de a+ (−b).De plus, pour tout n ∈ N, la notation n · a ( ou meme na ) designe l’element

a+ a+ · · ·+ a︸︷︷︸

n fois

.

Si n est un entier negatif, alors n · a ( ou na ) designe l’element

(−a) + (−a) + · · ·+ (−a)︸︷︷︸

|n| fois

= |n| · (−a).

Exemple 3.2.

1. L’ensemble des entiers Z muni de l’addition et de la multiplication usuelles est un anneau dontles elements distingues sont 0 et 1.

2. Les nombres rationnels Q forment un anneau pour les operations usuelles.

3. Il en est de meme de R et de C.

4. Les ensembles Z/mZ munis des operations d’addition et de multiplication definies dans le chapitreprecedent sont des anneaux. Les elements neutres sont respectivement [0]m et [1]m.

17

18 CHAPITRE 3. ANNEAUX ET CORPS

5. L’ensemble Mnn(R) des matrices carrees d’ordre n a coefficients dans R muni de la somme etde la multiplication usuelles des matrices forme un anneau. C’est vrai plus generalement si lescoefficients des matrices sont pris dans un anneau quelconque : par exemple l’ensemble Mnn(Z)des matrices a coefficients entiers est un anneau.

6. L’ensemble R[X] des polynomes a coefficients dans un anneau R est egalement un anneau (munide la somme et du produit usuels).

7. Soit V un R-espace vectoriel. L’ensemble (End(V ),+, ◦, 0, idV ) des applications lineaires

f : V → V

muni de la somme et de la composition est un anneau. L’element neutre pour la somme estl’application triviale 0 et l’element neutre pour la composition est l’application identite

idV : V → V.

Si V est de dimension finie n, cet anneau peut etre identifie - moyennant le choix d’une base - al’anneau Mnn(R) defini dans l’exemple 5 ci-dessus.

Donnons quelques proprietes elementaires des anneaux.

Lemme 3.3. Soit R un anneau. On a les resultats suivants :

(a) si a+ b = a+ c alors b = c pour tout a, b, c ∈ R ;

(b) 0 · a = 0 pour tout a ∈ R ;

(c) (−1) · a = −a pour tout a ∈ R ;

Demonstration : L’affirmation (a) decoule de la propriete (iv) de la definition 3.1. En effet, onpeut additionner a l’egalite a+ b = a+ c l’element −a. On obtient (−a) + a+ b = (−a) + a+ c. Par(iv) ceci donne 0 + b = 0 + c d’ou b = c.L’affirmation (b) decoule des proprietes (iii), (vi) et (vii) de la definition 3.1 ainsi que du point (a)ci-dessus. En effet, on a

0 · a+ a = 0 · a+ 1 · a = (0 + 1) · a = 1 · a = a.

On a donc a + 0 · a = a et a + 0 = a (point (iii) de la definition). Le point (a) du present lemmepermet de conclure que 0 · a = 0.Le point (c) se montre a l’aide du point (b). On a

0 = 0 · a = (1 + (−1)) · a = 1 · a+ (−1) · a.

En ajoutant −a a cette derniere egalite, on obtient −a = (−1) · a.

Definition 3.4 (Sous-anneau). Soit R un anneau et S ⊂ R un sous-ensemble de R. On dit queS est un sous-anneau de R si

(i) 1R ∈ S ;

(ii) a ∈ S =⇒ −a ∈ S ;

(iii) a, b ∈ S =⇒ a+ b ∈ S ;

(iv) a, b ∈ S =⇒ ab ∈ S.

L’ensemble S, muni des memes operations que R, est alors un anneau.

Exemple 3.5. L’anneau Z est un sous-anneau de Q et de R.L’anneau R est un sous-anneau de R[X] quelque soit R.

Definition 3.6 (Anneau commutatif). Un anneau R dans lequel on a

a · b = b · a

pour tout a, b ∈ R est dit commutatif.

3.1. NOTIONS DE BASE 19

Exemple 3.7. Les exemples 1, 2, 3, 4 et 6 ci-dessus sont commutatifs alors que les exemples 5 et 7ne le sont pas.

Definition 3.8 (Anneau integre). On dira qu’un anneau commutatif R est integre si a · b = 0implique a = 0 ou b = 0 pour tout a, b ∈ R. Autrement dit, l’anneau R est integre si et seulement sile produit de deux elements non nuls est non nul.

Exemple 3.9. Les anneaux des exemples 1, 2 et 3 sont des anneaux integres.L’exemple 6 donne un anneau qui est integre si et seulement si l’anneau des coefficients R l’est. Parexemple, l’anneau des polynomes a coefficients dans R est integre alors que celui des polynomes acoefficients dans Z/12Z ne l’est pas.Nous verrons plus loin dans quel cas l’anneau Z/mZ est integre. Signalons que Z/12Z ne l’est paspuisque nous avons vu au chapitre precedent que [3]12 · [4]12 = [0]12. En revanche, on peut verifierque Z/3Z est integre.L’anneau Mnn(R) des matrices carrees n × n a coefficients dans un anneau R n’est jamais integresi n > 1. En effet, on sait qu’il existe des matrices A et B non nulles telles que AB = 0. Si n = 1,Mnn(R) = R est integre si et seulement si R l’est.

Definition 3.10 (Diviseur de zero). Soit R un anneau. On dit que R possede des diviseurs dezero s’il existe a, b ∈ R avec a 6= 0 6= b et ab = 0. Les elements a et b sont appeles des diviseurs dezero.

Il est clair qu’un anneau est integre si et seulement s’il ne possede aucun diviseur de zero.Nous generalisons, a tous les anneaux, la notion d’unite vue au chapitre precedent.

Definition 3.11 (Unites d’un anneau). Un element a d’un anneau R est une unite s’il existeb ∈ R tel que ab = ba = 1.

Si un tel b existe, il est unique par le meme raisonnement que celui fait au paragraphe 2.2.1.

Exemple 3.12.

• Dans Z les seules unites sont 1 et −1 alors que dans Q tous les nombres non nuls sont des unites.

• DansMnn(R), les unites sont les matrices inversibles, c’est-a-dire les matrices de determinant nonnul. Plus generalement, si R est un anneau commutatif, les unites dans l’anneauMnn(R) sont lesmatrices dont le determinant est une unite dans R. En particulier, si l’on considere l’anneau desmatrices a ceofficients dans Z, les unites sont les matrices de determinant egal a ±1.

• Dans R[X], l’anneau des polynomes a coefficients dans R, les seules unites sont les polynomesconstants non nuls c.

• Dans Z/mZ, nous avons vu dans le theoreme 2.15 que [a]m est une unite si et seulement si(a,m) = 1.

Notation : Soit R un anneau. L’ensemble des unites de R sera note R∗.Les notions d’unites et de diviseurs de zero sont incompatibles mais un element d’un anneau peutetre ni l’un ni l’autre. C’est le cas, par exemple, de tous les entiers 6= 0,−1, 1 dans Z. Ce ne sont nides unites ni des diviseurs de zero.En revanche, dans Z/mZ, tout element non nul qui n’est pas une unite est un diviseur de zero. Eneffet, si d = (a,m) > 1 et m6 | a alors m = d · e et a = d · b. Mais alors

a · e = d · b · e = b ·m ≡ 0 (mod m).

Mais comme m6 | a et m6 | e, [a] est bien un diviseur de zero dans Z/mZ. En resume on a

Theoreme 3.13. Soit a ∈ Z et m ∈ N. Alors

1. si m|a alors [a]m = [0]m ∈ Z/mZ ;

2. si (m, a) = 1 alors [a]m est une unite dans Z/mZ et ;

3. si 1 < (a,m) < m alors [a]m est un diviseur de zero mod m.

Definition 3.14 (Corps). Un anneau commutatif dont tous les elements non nuls sont des unitesest appele un corps


Exemple 3.15. Les anneaux Q, R, C sont des corps.

Corollaire 3.16. L’anneau Z/mZ est un corps si et seulement si m = p est premier.

Demonstration : Ceci decoule du theoreme precedent en notant que le cas 3 est possible si etseulement si m n’est pas premier.

Notation : Le corps Z/pZ sera note Fp. C’est donc un corps a p elements. On verra plus loin quepour tout r ≥ 1, il existe un (unique) corps a q = pr elements qui sera note Fq. Il est important denoter que si r > 1, Fq 6= Z/qZ puisque Z/qZ n’est pas un corps dans ce cas-la.

3.2 Exemple : calcul d’un inverse dans Z/mZ

Pour demontrer que[a] ∈ (Z/mZ)∗ ⇐⇒ (a,m) = 1

nous avons utilise l’identite de Bezout (cf. theoreme 2.15). Pour calculer explicitement l’inverse d’uneunite, il faut utiliser l’algorithme d’Euclide pour trouver une relation de Bezout.

Exemple 3.17. Soit R = Z/10Z. Les unites de R sont [1], [3], [7] et [9]. Comme l’inverse d’une uniteest encore une unite, il suffit, dans ce cas, d’essayer pour constater que [3] · [7] = [1] et [9] · [9] = [1].On a donc l’inverse des 4 unites.Dans le cas plus complexe de l’anneau R = Z/49Z, il est un peu long de tout tester. On utilisealors l’algorithme d’Euclide. Cherchons par exemple l’inverse de [18]49. C’est bien une unite car(18, 49) = 1.

49 = 2 · 18 + 13

18 = 1 · 13 + 5

13 = 2 · 5 + 3

5 = 3 + 2

3 = 2 + 1

En remontant, on trouve l’identite de Bezout :

1 = 3− 2

= 3− (5− 3) = 2 · 3− 5

= 2 · (13− 2 · 5)− 5 = 2 · 13− 5 · 5= 2 · 13− 5(18− 13)

= 7 · 13− 5 · 18= 7(49− 2 · 18)− 5 · 18 = 7 · 49− 19 · 18

On a donc1 = 7 · 49− 19 · 18

ce qui montre que 18 · (−19) ≡ 1 (mod 49). L’inverse de [18]49 est donc [−19]49 = [30]49.

3.3 Homomorphismes d’anneaux

Lorsque l’on considere des espaces vectoriels, les applications interessantes entre de tels espaces sontles applications lineaires. Elles doivent respecter la structure de chaque espace vectoriel. Il en estde meme pour les anneaux et nous allons maintenant etudier les applications entre anneaux quirespectent la structure d’anneau.

Definition 3.18 (Homomorphisme d’anneaux). Soient R et S deux anneaux. Une application

f : R −→ S

est un homomorphisme d’anneaux si les conditions suivantes sont satisfaites :

3.3. HOMOMORPHISMES D’ANNEAUX 21

(i) f(a+ b) = f(a) + f(b) pour tout a, b ∈ R ;

(ii) f(ab) = f(a)f(b) pour tout a, b ∈ R ;

(iii) f(1R) = 1S .

La notation 1R et 1S sera souvent abusivement simplifiee en 1 mais il est important de garder al’esprit que ce sont deux elements distincts qui ne sont pas dans le meme anneau.

Exemple 3.19.

1. L’application

πm : Z −→ Z/mZ

a 7→ [a]m

qui, a chaque entier fait correspondre sa classe mod m, est un homomorphisme d’anneaux. Cecidecoule de tout ce qui a ete fait au chapitre 2.

2. L’application

f : Z/4Z −→ Z/12Z

[0] 7→ [0]

[1] 7→ [9]

[2] 7→ [6]

[3] 7→ [3]

respecte l’addition et la multiplication mais f(1) 6= 1. Ce n’est donc pas un homomorphismed’anneaux.

3. L’application

f : Z −→ Z

n 7→ 2n

n’est pas un homomorphisme d’anneau car f(1) = 2.

4. L’application

f : Q[X] −→ Q

p(X) 7→ p(0)

qui, a chaque polynome associe son terme constant, est un homomorphisme d’anneaux. En effet,soient p, q ∈ Q[X] avec

p(X) = a0 + a1X + · · ·+ anXn

etq(X) = b0 + b1X + . . . bmX

m.

On peut supposer que m ≥ n. Alors

(p+ q)(X) = a0 + b0 + (a1 + b1)X + · · ·+ (an + bn)Xn + · · ·+ bmX

m

et donc (p+ q)(0) = a0 + b0 = p(0) + q(0) ce qui montre que f(p+ q) = f(p) + f(q). De plus

(p · q)(X) = a0b0 + (a0b1 + a1b0)X + · · ·+ anbmXn+m

et donc f(p+q) = a0b0 = f(p)·f(q) ce qui montre que f respecte le produit. Finalement l’elementidentite dans Q[X] est le polynome constant p ≡ 1 et f(p) = 1.

5. Soit R un anneau et S ⊂ R un sous-anneau. Alors l’inclusion

S ↪→ R

s 7→ s

est un homomorphisme d’anneaux.


Donnons quelques proprietes des homomorphismes d’anneaux.

Proposition 3.20. Soit f : R −→ S un homomorphisme d’anneaux. Alors

(i) f(0) = 0 ;

(ii) f(−a) = −f(a) ;(iii) si a est une unite de R, alors f(a) est une unite de S et f(a)−1 = f(a−1).

Demonstration :

(i) Par 3.18 (i), on a f(a) = f(a + 0) = f(a) + f(0). Ajoutant −f(a) des deux cotes de l’egalite,on obtient 0 = f(0).

(ii) Ceci decoule de 3.18 (i) et du point precedent. En effet, on a f(0) = f(a + (−a)) = f(a) +f(−a) = 0. En additionnant −f(a) aux deux cotes de la derniere egalite, on obtient f(−a) =−f(a).

(iii) Soient a, b ∈ R tels que ab = ba = 1. Alors par 3.18 (ii) et (iii), on a 1 = f(1) = f(ab) = f(a)f(b)et de meme 1 = f(b)f(a) ce qui montre que f(b) est l’inverse de f(a) si b est l’inverse de a.

Nous rappelons quelques notions sur les applications en general :

Definition 3.21. Soient A et B deux ensembles. Une application f : A −→ B est dite

(a) injective si f(a) = f(a′) implique a = a′ ; en d’autres termes, un element de B a au plus unepre-image ;

(b) surjective si pour tout b ∈ B il existe un a ∈ A tel que f(a) = b ; autrement dit, un element deB a au moins une pre-image ;

(c) bijective si elle est injective et surjective. Tout element de B a donc une et une seule pre-image.

Exemple 3.22. L’application

N −→ N

n 7→ n2

est injective mais pas surjective car 3, par exemple, n’est pas un carre dans N et n’a donc pas depre-image.

Pour savoir si une application quelconque f : A→ B est injective, il faut utiliser la definition donneeci-dessus et verifier que tout element de B a au plus une pre-image. En revanche, si les ensemblesconsideres ont une structure supplementaire (d’espace vectoriel ou d’anneau par exemple) et que fest un homomorphisme, le critere devient beaucoup plus simple. Ce resultat est connu dans le casdes espaces vectoriels. En effet, une application lineaire f entre espaces vectoriels est injective si etseulement si son noyau - note Ker(f) - est reduit a {0}. Il en est de meme pour un homomorphismed’anneaux comme le montre le theoreme qui suit.Avant de l’enoncer, nous avons besoin de definir le noyau.

Definition 3.23 (Noyau d’un homomorphisme). Soient R et S deux anneaux et f : R −→ Sun homomorphisme. Le sous-ensemble de R

f−1(0) = {r ∈ R | f(r) = 0}est appele le noyau de f et se note Ker(f).

Theoreme 3.24. Un homomorphisme d’anneaux f : R −→ S est injectif si et seulement si l’element0 est la seule pre-image de 0, autrement dit si

Ker(f) = {0}.

Demonstration : La condition est clairement necessaire. Montrons qu’elle est suffisante. On sup-pose donc que Ker(f) = 0. Soit a, a′ ∈ R tels que f(a) = f(a′). Alors 0 = f(a)− f(a′) = f(a− a′).Ceci implique que a− a′ = 0 donc que a = a′ ce qui montre que f est injectif.

3.4. IDEAL 23

3.4 Ideal

Dans le cas des espaces vectoriels, le noyau d’une application lineaire est un sous-espace vectoriel.Dans le cas des anneaux, il faut introduire une nouvelle notion, celle d’ideal.

Definition 3.25 (Ideal d’un anneau). Soit R un anneau commutatif. Un sous-ensemble I ⊂ Rest un ideal si

(i) a+ a′ ∈ I pour tout a, a′ ∈ I et

(ii) ra ∈ I pour tout a ∈ I et tout r ∈ R.

En d’autres termes, un ideal est un sous-ensemble ferme pour l’addition et stable par multiplicationpar un element quelconque de R.Les ideaux I = {0} et I = R sont appeles les ideaux triviaux.

Pour savoir si un ideal est egal a tout l’anneau, il est utile d’utiliser le lemme suivant :

Lemme 3.26. Soient R un anneau et I un ideal de R. Si 1 ∈ I alors I = R.

Demonstration : Ceci resulte du point (ii) de la definition d’un ideal : pour tout r ∈ R, on ar = r · 1 ∈ I car 1 ∈ I.

Un premier exemple d’ideal est donne par le noyau d’un homomorphisme d’anneaux.

Theoreme 3.27. Le noyau d’un homomorphisme f : R −→ S est un ideal de R.

Demonstration : Soient a, a′ ∈ Ker(f). Alors

f(a+ a′) = f(a) + f(a′) = 0 + 0 = 0

ce qui montre que a+ a′ ∈ Ker(f). Soit r ∈ R. Alors

f(ra) = f(r) · f(a) = f(r) · 0 = 0

ce qui montre que ra ∈ Ker(f).

Exemple 3.28. Reprenons les exemples donnes sous 3.19 qui sont des homomorphismes.Dans l’exemple 1, le noyau de f est l’ideal mZ des multiples de m.Dans l’exemple 4, le noyau de f est l’ideal forme des polynomes sans terme constant.Dans l’exemple 5, les noyaux sont triviaux puisque ce sont des injections.

Proposition 3.29. Soit R un anneau et soit r ∈ R. Le sous-ensemble

{rx |x ∈ R},note (r) ou rR, est un ideal.

Definition 3.30 (Ideal et anneau principaux). Un ideal I 6= R d’un anneau R est dit principals’il existe r ∈ R tel que I = (r). Un anneau dont tous les ideaux sont principaux est dit principal.

Exemple 3.31. On peut montrer que Z et Q[X] sont des anneaux principaux (voir ci-dessous).En revanche l’anneau Z[X] n’est pas principal car l’ideal constitue des polynomes dont le termeconstant est pair n’est pas un ideal principal. Il est engendre au minimum par deux polynomes, parexemple les polynomes 2 et X.

Theoreme 3.32. L’anneau Z est principal.

Demonstration : Soit I un ideal de Z. Soit r ∈ I le plus petit entier positif non nul de I. Nousallons montrer que I = rZ. Soit a un element quelconque de I. La division euclidienne nous permetd’ecrire

a = qr + r′

avec 0 ≤ r′ < r. Mais comme r′ = a − qr et que a, r ∈ I, par la definition d’un ideal, on a r′ ∈ I.Par choix de r ceci implique que r′ = 0 et donc que a = rq. Ainsi tout element de I est un multiplede r et donc I = rZ.


Remarque 3.33. La preuve ci-dessus n’utilise que la division euclidienne sur Z. On peut alorsgeneraliser ce resultat aux anneaux qui possedent une “division euclidienne”. Ainsi, par exemple,l’anneau K[X] des polynomes a coefficients dans un corps K est un anneau principal car il possedeune division euclidienne (voir le theoreme 7.1).

Ainsi les seuls ideaux de Z sont ceux de la forme mZ. De plus

Lemme 3.34. Soient d et m des entiers > 1. Alors mZ ⊂ dZ si et seulement si d|m.

Demonstration : Si d|m alors il existe n avec m = dn. Soit ma un element de mZ. Alors ma =dna ∈ dZ ce qui montre que mZ ⊂ dZ.Reciproquement, si m ∈ dZ ceci implique que m est de la forme dn et ceci prouve que d divise m.

On peut reformuler la definition de la notion de corps en fonction des ideaux :

Theoreme 3.35. Un anneau R est un corps si et seulement s’il ne possede que les ideaux triviaux0 et R.

Demonstration : Montrons que la condition est necessaire. Soit I un ideal non nul de R et r ∈ Iun element non nul. Par hypothese, il est inversible, c’est-a-dire qu’il existe t ∈ R tel que rt = tr = 1.Ceci implique que 1 ∈ I et donc, par le lemme 3.26, que I = R.Reciproquement, supposons que tout ideal I 6= R soit l’ideal nul. Alors si r ∈ R est un element nonnul de R, l’ideal principal (r) doit etre egal a R. Mais ceci implique que 1 ∈ (r) et donc qu’il existex ∈ R avec rx = 1 ce qui montre que r est inversible. L’anneau R est donc un corps.

Cette caracterisation va nous permettre de demontrer facilement que tout homomorphisme partantd’un corps est injectif.

Theoreme 3.36. Soit f : R −→ S un homomorphisme ou R est un corps. Alors f est injectif.

Demonstration : Nous mettons ensemble ce qui a ete vu jusque-la. Par le theoreme 3.27, Ker(f) estun ideal. Mais par le theoreme 3.35, on a soit Ker(f) = 0 soit Ker(f) = R. Mais vu que f(1) = 1 6= 0,il s’ensuit que Ker(f) = (0). Ceci implique, par le theoreme 3.24, que f est injectif.

Etudions maintenant les homomorphismes dont l’anneau de depart est Z. Soit R un anneau etf : Z −→ R un homomorphisme. Par definition d’un homomorphisme et par ses proprietes, il fautque f(0) = 0 et f(1) = 1. Mais il faut encore que

f(n) = f(1 + 1 + · · ·+ 1︸︷︷︸

n

) = 1R + 1R + · · ·+ 1R︸︷︷︸

n

= n · 1R

pour tout n ∈ Z. Ainsi f est completement determine par la donnee de f(1) et est donc unique.Reciproquement, on montre que l’application f : Z −→ R definie par

f(n) = n · 1R

est un homomorphisme d’anneaux.En resume, il existe un et un seul homomorphisme de Z dans un anneau quelconque R.

Definition 3.37 (Caracteristique). Soit R un anneau et f : Z −→ R l’unique homomorphismedefini ci-dessus. Si f est injectif, on dira que R est de caracteristique nulle. Sinon, Ker(f) est unideal non trivial de Z et comme Z est principal (voir le theoreme 3.32) il est de la forme mZ avecm > 0. L’entier m est appele la caracteristique de R.

Moins formellement, la caracteristique d’un anneau est le plus petit entier positifm tel quem·1R = 0.S’il n’ y en a pas, alors la caracteristique est nulle.

Exemple 3.38.

3.5. FACTORISATION DES HOMOMORPHISMES 25

1. Nous avons vu que le noyau de l’homomorphisme

Z −→ Z/mZ

a 7→ [a]m

est l’ideal mZ. Ceci implique que Z/mZ est de caracteristique m.

2. L’anneau Z est de caracteristique nulle car l’unique homomorphisme f : Z −→ Z est l’identite. Ilest donc injectif.

3. Les injections canoniques Z −→ Q ou Z −→ R montrent que Q et R (et C egalement) sont descorps de caracteristique nulle.

4. Les corps Fp sont des exemples de corps de caracteristique p (avec p premier).

Proposition 3.39. La caracteristique d’un anneau integre (et en particulier d’un corps) est egalea 0 ou a un premier p.

Demonstration : Nous montrons la contraposee. Soit R un anneau de caracteristique m 6= 0 avecm non premier. Il existe alors des entiers naturels n, r < m tels que m = nr. Soit f : Z −→ Rl’unique homomorphisme. Par definition de m, on a f(m) = 0 mais f(r) 6= 0 6= f(n). Mais alorsf(r)f(n) = f(rn) = f(m) = 0 ce qui montre que R n’est pas integre.

La reciproque du theoreme n’est pas vraie comme le montre l’exemple de l’anneau R×R ou l’additionet la multiplication se font composante par composante. C’est un anneau de caracteristique nullemais avec des diviseurs de zero car

(1, 0) · (0, 1) = (0, 0).

3.5 Factorisation des homomorphismes

Dans ce paragraphe, on s’interesse a la question de savoir quand un homomorphisme d’anneauxf : Z −→ R induit un homomorphisme sur les classes mod m.

Theoreme 3.40. Soit

f : Z −→ R

un homomorphisme d’anneaux. On suppose que l’ideal mZ est contenu dans l’ideal Ker(f). Alors finduit un homomorphisme

f : Z/mZ −→ R.

De plus, si mZ = Ker(f) alors f est injectif.

Demonstration : Soient a et b deux representants de la meme classe (mod m). Alors a = b+ kmet

f(a) = f(b+ km) = f(b) + f(km) = f(b)

car km ∈ mZ ⊂ Ker(f). Ainsi deux entiers congrus modulo m ont la meme image par f . On peutalors poser

f : Z/mZ −→ R

[a]m 7→ f(a)

et cette definition a un sens par ce qui vient d’etre dit.

Maintenant, supposons que Ker(f) = mZ. Alors si f([a]m) = f([b]m) ceci implique, par definitionde f que f(a) = f(b), i.e. f(a − b) = 0, donc que a − b ∈ Ker(f). Mais comme Ker(f) = mZ, cecientraıne que a− b ∈ mZ c’est-a-dire que a = b+ lm ou encore que [a]m = [b]m. Ceci montre que fest injectif.


Notons que l’on a f = f ◦ πm, c’est-a-dire que l’on a un diagramme commutatif

Z

πm

²²

f// R

Z/mZf

77o

oo

oo

oo

oo

oo

oo

ou πm : Z → Z/mZ designe l’homomorphisme canonique defini dans l’exemple 1 de 3.19.

Remarque 3.41. La reciproque du theoreme est egalement vraie : soit f : Z → R un homo-morphisme d’anneaux. S’il existe un homomorphisme f : Z/mZ → R tel que f = f ◦ πm, alorsceci implique que mZ ⊂ Ker(f). Ceci est clair car si a ∈ mZ alors πm(a) = 0 et a fortiorif ◦ πm(a) = 0 = f(a).

Un cas particulier est traite dans le corollaire suivant avec R = Z/dZ.

Corollaire 3.42. Soient m et d des entiers > 1. Il existe un homomorphisme d’anneaux

g : Z/mZ −→ Z/dZ

si et seulement si d|m. De plus, si d|m, alors g est unique et determine par g([1]m) = [1]d.

Demonstration : C’est une consequence du theoreme et de la remarque qui precedent ainsi quedu lemme 3.34 en prenant f = πd et g = πd.

Z

πm

²²

πd // Z/dZ

Z/mZ

g=πd

77n

nn

nn

nn

nn

nn

n

Chapitre 4

Theoremes d’Euler et de Fermat

Dans ce chapitre nous allons nous interesser aux puissances successives d’un entier a (modm) lorsque(a,m) = 1. Commencons par un exemple.

Exemple 4.1. Prenons m = 7 et considerons l’anneau Z/7Z. Les unites dans cet anneau sont toutesles classes non nulles. Si l’on calcule les puissances de 2, on trouve que

22 = 4 ≡ 4 (mod 7) 23 ≡ 1 (mod 7)

ce qui donne, en d’autres termes, que [2]3 = [1] dans Z/7Z.On trouve encore que

32 = 9 ≡ 2 (mod 7) 33 = 27 ≡ −1 (mod 7)

34 ≡ −1 · 3 ≡ 4 (mod 7) 35 ≡ 4 · 3 ≡ 5 (mod 7)

36 ≡ 15 ≡ 1(mod 7)

ce qui montre que [3]6 = [1] dans Z/7Z et 6 est le plus petit entier positif n tel que [3]n = [1].

On peut montrer qu’il existe toujours un entier n tel que an ≡ 1 (mod m).

Proposition 4.2. Soient a et m des entiers tels que (a,m) = 1 et m > 1. Alors il existe un entiern tel que an ≡ 1 (mod m).

Demonstration : On travaille dans l’anneau Z/mZ. Comme (a,m) = 1, la classe [a] (mod m) estune unite dans cet anneau. Considerons alors les elements

1, [a], [a]2, . . . [a]m−1.

Ce sont m elements de Z/mZ tous differents de 0 car a est une unite. Comme Z/mZ possede melements, deux de ces elements doivent etre egaux, c’est-a-dire qu’il existe s tel que [a]s = [a]s+n

avec n > 0. Mais comme [a] est inversible, ceci implique que [a]s l’est aussi et donc que [a]n = [1].Autrement dit an ≡ 1 (mod m).

Ceci nous amene a la definition suivante :

Definition 4.3 (Ordre d’un entier (mod m)). Soit m un entier > 1 et a un entier tel que(a,m) = 1. Le plus petit entier positif n tel que an ≡ 1 (mod m) est appele l’ordre de a modulo m.

Exemple 4.4. Les exemples ci-dessus ont montre que l’ordre de 2 (mod 7) est egal a 3 alors quel’ordre de 3 (mod 7) vaut 6.

L’entier 1 est bien evidemment toujours d’ordre 1 quelque soit m.

Voici, a titre d’exemple, le tableau des ordres de toutes les unites de Z/10Z.

27

28 CHAPITRE 4. THEOREMES D’EULER ET DE FERMAT

element ordre

[1] 1

[3] 4

[7] 4

[9] 2

Nous allons maintenant enoncer un theoreme que nous demontrerons plus tard lorsque nous auronsles outils techniques pour le faire.

Theoreme 4.5 (Theoreme d’Euler). Soit a et m deux entiers tels que m > 1 et (a,m) = 1.Alors

aϕ(m) ≡ 1 (mod m).

En d’autres termes, si x = [a]m dans Z/mZ, alors xϕ(m) = 1.

Un corollaire de ce theoreme est le petit theoreme de Fermat, anterieur chronologiquement a celuid’Euler.

Corollaire 4.6 (Petit theoreme de Fermat). Soit a un nombre et p un premier ne divisant pasa. Alors

ap−1 ≡ 1 (mod p).

Demonstration : C’est une consequence immediate du theoreme d’Euler en sachant queϕ(p) = p− 1 lorsque p est premier.

Exemple 4.7. Soit a = 2 et p = 7. Alors 26 = 64 ≡ 1 (mod 7).Soit a = 3 et p = 5. Alors 34 = 81 ≡ 1 (mod 5).Soit a = 4 et p = 3. Alors 42 = 16 ≡ 1 (mod 3).Soit a = 3 et m = 10. Alors ϕ(10) = ϕ(2) · ϕ(5) = 4 et 34 = 81 ≡ 1 (mod 10).Soit a = 5 et m = 12. Alors ϕ(12) = ϕ(4) · ϕ(3) = 4 et 54 = 625 = 52 · 12 + 1 ≡ 1 (mod 12).

Le theoreme d’Euler nous permet de calculer l’inverse d’une unite. En effet, comme [a]ϕ(m) = 1 dansZ/mZ, l’inverse de a (mod m) est la classe de aϕ(m)−1.

Exemple 4.8. Calculons l’inverse de [4] dans Z/9Z. On a ϕ(9) = 6 et donc 46 ≡ 1 (mod m). Cecientraıne que [45] = [1096] = [7] est l’inverse de 4 (mod 9). On verifie en effet que

4 · 7 = 28 ≡ 1 (mod m).

Calculons l’inverse de 5 modulo 7. On a 56 ≡ 1 (mod 7). L’inverse de 5 est donc

55 = 125 · 25 ≡ 6 · 4 ≡ 3 (mod 7).

En effet, 5 · 3 = 15 ≡ 1 (mod 7).

Chapitre 5

Les groupes

5.1 Notions de base

Pour demontrer le theoreme d’Euler, nous avons besoin de quelques fondements de la theorie desgroupes.

Definition 5.1 (Groupe). Un groupe est un ensemble G muni d’une loi interne

G×G −→ G

(g, h) 7→ g ∗ h

et d’un element distingue e ∈ G, appele element neutre, tels que les proprietes suivantes soientsatisfaites :

(i) (g ∗ h) ∗ k = g ∗ (h ∗ k) pour tout g, h, k ∈ G (associativite de la loi) ;

(ii) g ∗ e = e ∗ g = g pour tout g ∈ G ;

(iii) pour tout g ∈ G il existe un element g−1 ∈ G tel que g ∗ g−1 = g−1 ∗ g = e (existence del’inverse)

Un groupe sera note (G, ∗, e) ou plus simplement (G, ∗) (resp. G) si l’element neutre (resp. la loiinterne) sont sans ambiguıte.

Exemple 5.2.

1. L’ensemble Z avec l’addition comme loi interne et 0 comme element neutre est un groupe. Il seranote (Z,+) par la suite.

2. Plus generalement, si (R,+, ·) est un anneau alors (R,+, 0) est un groupe. On oublie simplementle produit.

3. (Z, ·) n’est pas un groupe car les entiers ne possedent pas tous des inverses pour le produit. Lapropriete (iii) n’est donc pas verifiee.

4. Si R est un anneau, alors (R∗, ·, 1) est un groupe. Par exemple les unites dans Z/6Z forment ungroupe pour le produit, l’element neutre etant la classe de [1].

5. De meme, l’ensemble des matrices n × n reelles inversibles muni du produit matriciel forme ungroupe dont l’element neutre est la matrice identite In. Ce groupe est note GLn(R).

6. L’ensemble Sn des bijections de l’ensemble {1, 2, . . . , n} sur lui-meme muni de la compositioncomme loi interne est un groupe. L’element neutre est l’application identite. Chaque applicationpossede un inverse puisque l’on a pris les bijections. Ce groupe est appele le groupe symetrique an lettres et ses elements sont des permutations.

Definition 5.3 (Groupe abelien). Soit (G, ∗) un groupe. On dit que G est abelien ou commutatifsi

g ∗ h = h ∗ g pour tout g, h ∈ G.

29

30 CHAPITRE 5. LES GROUPES

Exemple 5.4. Les groupes des exemples 1 et 2 ci-dessus sont abeliens. En revanche, les groupesGLn(R) ne le sont pas pour n ≥ 2 et les groupes Sn ne le sont pas pour n ≥ 3. Dans le cas del’exemple 4, le groupe (R∗, ·) est un groupe abelien si l’anneau R est commutatif.

Definition 5.5 (Ordre d’un groupe fini). Un groupe est dit fini s’il possede un nombre finid’elements. Ce nombre est appele l’ordre de G et est note |G| ou ]G.

Exemple 5.6. Le groupe Z/nZ est un groupe abelien fini a n elements.Le groupe ((Z/nZ)∗, ·) est un groupe abelien fini a ϕ(n) elements.Le groupe Sn est un groupe fini a n! elements.

Notation 5.7. Soit (G, ∗) un groupe. Pour n ∈ N, on note gn l’element g ∗ g ∗ · · · ∗ g︸︷︷︸

n fois

. Si n ∈ Z et

n < 0 on note gn l’element g−1 ∗ g−1 ∗ · · · ∗ g−1︸︷︷︸

|n| fois

.

Finalement, on convient que g0 = e.Si le groupe G est abelien, on utilisera souvent la notation n · g au lieu de gn et ceci de manieresystematique si l’operation interne est une addition.

Dans le chapitre precedent, la notion d’ordre d’un entier a ete introduite. Nous allons generaliserceci en definissant l’ordre d’un element d’un groupe.

Definition 5.8 (Ordre d’un element). Soient (G, ∗, e) un groupe et g ∈ G. L’ordre de g est leplus petit entier positif non nul n tel que gn = e. Si un tel n n’existe pas, on dit que g est d’ordreinfini.

Exemple 5.9.

• Dans Z, tous les entiers sont d’ordre infini a l’exception de 0 qui est d’ordre 1.

• Dans Z/6Z, on a [2]+ [2]+ [2] = 0 et [2]+ [2] = [4] 6= 0 ce qui montre que 2 (mod 6) est d’ordre 3.

• Plus generalement, pour tout x ∈ Z/mZ, on a m ·x = 0 ce qui montre que tout element de Z/mZest d’ordre au plus m.

• Dans ((Z/7Z)∗, ·), on a vu que 22 6≡ 1(mod 7) alors que 23 = 8 ≡ 1(mod 7). Donc [2]7 est d’ordre3.

Lemme 5.10. Soit g ∈ G un element d’ordre n. Alors g−1 est aussi d’ordre n.

Demonstration : Remarquons d’abord que (g−1)n est l’inverse de gn car

(g−1)n ∗ gn = g−1 ∗ g−1 ∗ · · · g−1 ∗ g ∗ g ∗ · · · ∗ g = e.

Mais comme gn = e ceci implique que (g−1)n = e. Ainsi g−1 est d’ordre au plus n, i.e. m ≤ n.Mais symetriquement, si m est l’ordre de g−1, alors g est d’ordre au plus egal a m. Donc n ≤ m.Ceci montre que m = n.

La suite est consacree a la demonstration du theoreme de Lagrange qui nous permettra de relierl’ordre d’un element avec l’ordre du groupe auquel il appartient. Pour cela, nous avons besoin de lanotion de sous-groupe qui est l’objet de la section suivante.

5.2 Sous-groupe

Definition 5.11 (Sous-groupe). Soit G un groupe. Un sous-ensemble H de G est un sous-groupede G s’il est non vide et si on a :

(i) pour tout g, h ∈ H, on a g ∗ h ∈ H ;

(ii) pour tout h ∈ H, on a h−1 ∈ H.

Remarquons que (i) et (ii) implique que e ∈ H. En effet si h ∈ H alors par (ii) h−1 ∈ H et par (i),on a h ∗ h−1 = e ∈ H.

5.2. SOUS-GROUPE 31

5.2.1 Groupe cyclique

Soient G un groupe et g ∈ G. Considerons le sous-ensemble

< g >= {gn |n ∈ Z}.On verifie que (< g >, ∗, e) est un sous-groupe. Il est appele le sous-groupe engendre par g.

Definition 5.12 (Groupe cyclique). Un groupe G est dit cyclique s’il existe g ∈ G tel queG =< g >. L’element g est un generateur du groupe G.

Remarquons que tout groupe cyclique est abelien.

Exemple 5.13.

(a) Le groupe Z est cyclique car il est engendre par 1. En effet, l’inverse de 1 est −1 et toutentier s’ecrit comme une somme de 1 ou une somme de -1. Les elements 1 et −1 sont les seulsgenerateurs de Z.

(b) Le groupe Z/5Z est cyclique car il est engendre par 1. Mais on constate qu’il est egalementengendre par [2] car [2] + [2] = [4], [2] + [2] + [2] = [1] et 4 · [2] = [3]. En fait, on peut montrerque tout element non nul de Z/5Z est un generateur.

(c) Le groupe Sn (n > 2) n’est pas cyclique car il n’est pas abelien.

(d) Le groupe G = Z/3Z×Z/3Z n’est pas cyclique. En effet, supposons que (a, b) soit un generateur.On a alors que (a, b) + (a, b) + (a, b) = (0, 0). L’inverse de (a, b) est donc (2a, 2b) et le groupeengendre par (a, b) n’a que 3 elements. C’est donc un sous-groupe strict de G.

(e) Le groupe Z/2Z× Z/3Z est cyclique. Il est engendre, par exemple, par ([1], [1]).Plus generalement, on montrera plus tard que le groupe

Z/mZ× Z/nZ

est cyclique si et seulement si (m,n) = 1.

Remarque 5.14. Dans un groupe cyclique fini, l’ordre d’un generateur est egal a l’ordre du groupe.

Nous sommes maintenant en mesure d’enoncer et de demontrer le theoreme de Lagrange.

Theoreme 5.15 (Theoreme de Lagrange). Soient G un groupe fini et H ⊂ G un sous-groupe.Alors l’ordre de H divise l’ordre de G.

Demonstration : Pour tout g ∈ G, nous allons considerer les sous-ensembles Xg de G definis par

Xg = gH = {g ∗ h | h ∈ H}.Par exemple, Xe = H. Comme e ∈ H, tout element g est dans Xg car g = g ∗ e. Ainsi la reunion detous les Xg recouvre le groupe G :

⋃

g∈G

Xg = G.

De plus les sous-ensembles Xg sont soit egaux soit disjoints. En effet, supposons qu’un element g ∈ Gappartienne a Xa et Xb avec a 6= b. Ceci revient a dire que g = a ∗ h et g = b ∗ h′ avec h, h′ ∈ H.Mais alors a = g ∗ h−1 = b ∗ h′ ∗ h−1 = b ∗ l avec l ∈ H, ce qui montre que a ∈ Xb. On a donc lesimplications suivantes

g ∈ Xa ⇒ g = a ∗ h, h ∈ H ⇒ g = b ∗ l ∗ h⇒ g ∈ Xb.

Symetriquement, on montre que g ∈ Xb implique g ∈ Xa ce qui prouve que Xa = Xb.Ainsi on a soit Xg ∩Xg′ = ∅ soit Xg = Xg′ .Maintenant, comme g ∗ h 6= g ∗ h′ si h 6= h′, tous les Xg ont le meme nombre d’elements a savoir|H|. Comme ils recouvrent tout G et qu’ils sont disjoints, on doit avoir

m · |H| = |G|ou m est le nombre de ces Xg distincts. Ceci montre que |H| divise |G|.

Une application importante de ce resultat est le corollaire suivant :


Corollaire 5.16. Soient G un groupe et g ∈ G. Alors l’ordre de g divise |G|. En particulier g |G| = epour tout g ∈ G.

Demonstration : On considere le sous-groupe H =< g > dans G. L’ordre de g est egal a |H| (voirla remarque 5.14 ci-dessus) et, par le theoreme precedent, |H| divise |G|.

Une application de ce theoreme est que tout groupe d’ordre premier est cyclique. En effet, si |G| = pest un nombre premier alors l’ordre de tout element g de G doit diviser p. Donc si g 6= e, il doit etred’ordre p et ainsi < g >= G ce qui montre que g engendre G.

Une autre consequence du corollaire est le theoreme d’Euler qui a ete enonce au paragraphe 4.

Demonstration du theoreme d’Euler : On considere le groupe multiplicatif G = ((Z/mZ)∗, ·).Il est d’ordre ϕ(m) comme nous l’avons vu ci-dessus. Le corollaire implique donc que

xϕ(m) = 1

pour tout x ∈ (Z/mZ)∗. En termes de congruence, ceci revient bien a dire que si (a,m) = 1 alors

aϕ(m) ≡ 1 (mod m).

Un resultat important sur l’ordre d’un element est la proposition suivante.

Proposition 5.17. Soit G un groupe et soit g ∈ G un element d’ordre d. Supposons que gn = e.Alors d divise n.

Demonstration : On a gd = gn = e. Par definition de l’ordre, on a d ≤ n. Faisons alors la divisioneuclidienne de n par d. On a n = qd+ r avec r < d. Ceci donne

e = gn = gqd+r = gqd ∗ gr = (gd)q ∗ gr = e ∗ gr = gr.

Mais comme d est le plus petit entier positif tel que gd = e, on a r = 0. Ce qui implique que n = qdet le resultat voulu est demontre.

5.3 Homomorphisme de groupes

Definition 5.18 (Homomorphisme de groupes). Soient (G, ∗) et (H, ◦) deux groupes. Uneapplication f : G −→ H est un homomorphisme de groupes si l’on a

1. f(g ∗ g′) = f(g) ◦ f(g′) pour tout g, g′ ∈ G ;

2. f(eG) = eH

Les proprietes 1 et 2 impliquent que f(g−1) = (f(g))−1.

Un homomorphisme de groupes qui est bijectif est appele un isomorphisme de groupes. Deux groupesG etH pour lesquels il existe un isomorphisme f : G −→ H sont dits isomorphes et on le noteG ∼= H.

Exemple 5.19. On a vu que si d|m il existe un homomorphisme d’anneaux

f : Z/mZ −→ Z/dZ.

Cet homomorphisme se restreint sur les unites en un homomorphisme de groupes :

f : (Z/mZ)∗ −→ (Z/dZ)∗.

5.3. HOMOMORPHISME DE GROUPES 33

Par exemple si m = 12 et d = 3, on obtient l’homomorphisme suivant

(Z/12Z)∗ = {[1]12, [5]12, [7]12, [11]12} −→ (Z/3Z)∗ = {[1]3, [2]3}[1]12 7→ [1]3

[5]12 7→ [2]3

[7]12 7→ [1]3

[11]12 7→ [2]3.

On verifie que l’application f respecte tous les produits dans Z/12Z et Z/3Z. C’est donc bien unhomomorphisme.Par exemple,

[5]12 · [7]12 = [11]12

etf([5]12) · f([7]12) = [2]3 · [1]3 = [2]3 = f([11]12).

Definition 5.20 (Noyau et image d’un homomorphisme). Soit f : G −→ H un homomor-phisme de groupes. On definit le noyau de f comme l’ensemble

{g ∈ G |f(g) = eH}.

On le note Ker(f). De meme, on definit l’image de f par

Im(f) = {h ∈ H | ∃ g ∈ G avec f(g) = h}.

On peut montrer que si f : G −→ H est un homomorphisme, alors Ker(f) est un sous-groupe de Get Im(f) est un sous-groupe de H.Comme pour les anneaux, l’injectivite d’un homomorphisme se lit sur le noyau :

Theoreme 5.21. Soit f : G −→ H un homomorphisme de groupes. Alors f est injectif si etseulement si Ker(f) = {e}.Demonstration : La preuve est similaire a celle faite dans le cas des anneaux (voir theoreme 3.24).

Remarque 5.22. Si G =< g > est un groupe cyclique, alors un homomorphisme de groupesf : G→ H est entierement determine par l’element f(g) ∈ H. Si g est d’ordre infini, l’element f(g)peut etre quelconque. En revanche si g est d’ordre n, l’ordre de f(g) doit etre un diviseur de n. Ona en effet

f(g)n = f(gn) = f(e) = e

et le theoreme 5.17 nous permet de conclure que l’ordre de f(g) divise n.

Exemple 5.23. Nous donnons quelques exemples d’homomorphismes de groupes

1. Considerons l’homomorphisme de groupes

f : Z/6Z −→ Z/12Z

defini par f([1]6) = [2]12. Cet homomorphisme est bien defini vu la remarque ci-dessus. En effet,l’element [1]6 est d’ordre 6 dans Z/6Z puisque c’est un generateur et l’element [2]12 est aussid’ordre 6 dans Z/12Z. Le noyau de f est nul ce qui montre que f est injectif.

2. On peut egalement definir un homomorphisme de groupes

h : Z/6Z −→ Z/12Z

par h([1]6) = [4]12. C’est un homomorphisme bien defini car [4]12 est d’ordre 3 et 3 divise bienl’ordre de [1]6. Le noyau de h est le sous-groupe

Ker(h) = {[0], [3]}

carh([3]6) = 3 · h([1]6) = 3 · [4]12 = [12]12 = [0].

L’homomorphisme h n’est donc pas injectif.


3. L’application determinant

det : GLn(R) −→ (R∗, ·)A 7→ det(A)

est un homomorphisme du groupe des matrices n×n inversibles dans le groupe des nombres reelsnon nuls muni du produit. Son noyau est le sous-groupe des matrices de determinant 1 que l’onnote SLn(R).

5.4 Table de multiplication d’un groupe

Dans le cas d’un groupe fini, on peut donner une table de multiplication du groupe.Nous mettons ici, en guise d’exemple, la table de multiplication du groupe ((Z/9Z)∗, ·). L’ordre dece groupe est ϕ(9) = 6. Ses elements sont [1], [2], [4], [5], [7] et [8]. Dans le tableau, on a omis lescrochets.

· 1 2 4 5 7 81 1 2 4 5 7 82 2 4 8 1 5 74 4 8 7 2 1 55 5 1 2 7 8 47 7 5 1 8 4 28 8 7 5 4 2 1

Ce groupe a deux elements d’ordre 6 qui sont [2] et [2]−1 = [5]. Il a deux elements d’ordre 3, a savoir[4] et [4]−1 = [7]. Et il a un element d’ordre 2 qui est [8].Remarquons que chaque element du groupe doit apparaıtre une et une seule fois dans chaque ligneet chaque colonne.

5.5 Exemple d’un groupe non abelien : S3

Dans cette section, nous traitons l’exemple du groupe S3. Rappelons que ce groupe est l’ensembledes permutations de l’ensemble {1, 2, 3}. Il est d’ordre 3! = 6. Voici la liste de ces elements :

id : (1, 2, 3) −→ (1, 2, 3)

ρ : (1, 2, 3) −→ (2, 3, 1) i.e. ρ(1) = 2, ρ(2) = 3, ρ(3) = 1

φ : (1, 2, 3) −→ (2, 1, 3)

σ1 : (1, 2, 3) −→ (1, 3, 2)

σ2 : (1, 2, 3) −→ (3, 2, 1)

σ3 : (1, 2, 3) −→ (3, 1, 2).

La loi de groupe est la composition. On remarque que

ρ ◦ ρ = σ3 φ ◦ ρ = σ1

φ ◦ ρ2 = σ2

ce qui montre que ρ et φ suffisent a engendrer S3.Nous donnons maintenant le tableau de multiplication de S3. (On a note φρ au lieu de φ ◦ ρ.)

id ρ ρ2 φ φρ φρ2

id id ρ ρ2 φ φρ φρ2

ρ ρ ρ2 id φρ2 φ φρρ2 ρ2 id ρ φρ φρ2 φφ φ φρ φρ2 id ρ ρ2

φρ φρ φρ2 φ ρ2 id ρφρ2 φρ2 φ φρ ρ ρ2 id

5.5. EXEMPLE D’UN GROUPE NON ABELIEN : S3 35

Le groupe S3 est d’ordre 6. Il a deux elements d’ordre 3 a savoir ρ et ρ2 et trois elements (φ, φρ etφρ2) d’ordre 2.Un sous-groupe de S3 doit etre d’ordre 1, 2, 3 ou 6 par le theoreme de Lagrange. S’il est d’ordre 6c’est S3 tout entier. S’il est d’ordre 1 c’est le sous-groupe trivial {id}. Sinon, il est d’ordre un nombrepremier (2 ou 3) et est donc cyclique. Chaque element d’ordre 2 engendre un sous-groupe d’ordre 2et les deux elements d’ordre 3 etant l’inverse l’un de l’autre engendrent le meme sous-groupe d’ordre3. En conclusion S3 a 4 sous-groupes stricts non-triviaux dont trois sont d’ordre 2 et le quatriemeest d’ordre 3.

Chapitre 6

Le theoreme des restes chinois

6.1 Bases theoriques

On raconte que, dans la Chine ancienne, les regiments comptaient 1000 soldats. Pour savoir si unregiment etait au complet, on faisait aligner les hommes par rangs de 7, puis de 11 et enfin de 13.Si, dans les trois cas, il manquait 1 homme pour que le dernier rang soit rempli, on en deduisait quele regiment etait au complet.Cette methode s’appuie sur le bien nomme theoreme des restes chinois dont l’etude fait l’objet dece chapitre.Nous allons donner deux formes differentes mais equivalentes de ce theoreme.

Theoreme 6.1 (Theoreme des restes chinois). Soient m1, m2, . . ., mr des entiers premiersdeux a deux (i.e. (mi,mj) = 1 si i 6= j) et a1, a2, . . ., ar, des entiers quelconques. Alors il existe unentier x tel que

x ≡ a1 (mod m1)x ≡ a2 (mod m2)

...x ≡ ar (mod mr).

(6.1)

De plus, si x et x′ sont deux entiers qui sont solutions de ce systeme de congruences, alors

x ≡ x′ (mod M)

ou M = m1m2 · · ·mr.Reciproquement, si x est une solution et x ≡ x′ (mod M) alors x′ est aussi une solution.

Nous donnons une seconde formulation de ce theoreme, plus abstraite et plus compacte.

Theoreme 6.2 (Theoreme des restes chinois). Soient m1, m2, . . ., mr des entiers premiersdeux a deux et M = m1m2 · · ·mr. Alors l’homomorphisme d’anneaux (voir corollaire 3.42)

f : Z/MZ −→ Z/m1Z × Z/m2Z × · · · × Z/mrZ

[a]M 7→ ([a]m1, [a]m2

, · · · , [a]mr)

est un isomorphisme.

Nous demontrons le theoreme sous cette forme mais donnerons ensuite une preuve explicite de lasurjectivite.Demonstration : Montrons que f est injectif. Soit [a]M et [b]M tels que f([a]M ) = f([b]M ),c’est-a-dire que

a ≡ b (mod mi)

pour tout i = 1, 2, . . . , r. En d’autres termes, b − a est un multiple de mi pour tout i = 1, 2, . . . , r.Par le theoreme 1.28, b− a est un multiple du ppcm des mi. Mais comme les mi sont premiers deux

37

38 CHAPITRE 6. LE THEOREME DES RESTES CHINOIS

a deux, ceci implique que b − a est un multiple de M et donc [a]M = [b]M . Ceci prouve que f estinjectif.Maintenant, comme Z/MZ a M elements et l’anneau

Z/m1Z × Z/m2Z × · · · Z/mrZ

a aussi M elements, le fait que f soit injectif implique qu’il est surjectif. C’est donc un isomorphismeet le theoreme est demontre.

Le “defaut” de la demonstration precedente est qu’elle ne donne pas l’algorithme pour trouverl’entier x (ou sa classe mod M) tels que f([x]) = (a1, a2, . . . , ar). Nous allons donner maintenantune methode pour trouver x.

6.2 Restes chinois : deux algorithmes

6.2.1 Premiere methode

On cherche donc a resoudre le systeme de congruences (6.1). On commence par resoudre, pour un ifixe, le systeme

xi ≡ 0 (mod m1)

xi ≡ 0 (mod m2)

...

xi ≡ 0 (mod mi−1)

xi ≡ 1 (mod mi)

xi ≡ 0 (mod mi+1)

...

xi ≡ 0 (mod mr)

Pour ce faire, on pose ki = m1m2 · · ·mi−1mi+1 · · ·mr. Par hypothese, ki et mi sont premiers entreeux et l’identite de Bezout nous donne une egalite

1 = rki + smi.

On pose xi = rki. On a alors que xi satisfait le systeme ci-dessus. Pour chaque i = 1, 2, . . . , n, ontrouve un tel xi tel que xi ≡ 1 (mod mi) et tel que xi soit un multiple des autres mj . Une solutiondu systeme (6.1) est alors

x = a1x1 + a2x2 + · · ·+ arxr.

Exemple 6.3. Resolvons le systeme

x ≡ 3 (mod 11)

x ≡ 6 (mod 8)

x ≡ −1 (mod 15)

par la methode decrite ci-dessus. Premierement, nous resolvons le systeme

x ≡ 1 (mod 11)

x ≡ 0 (mod 8)

x ≡ 0 (mod 15)

en cherchant une identite de Bezout pour 11 et 120 = 8 · 15. De

120 = 11 · 10 + 10

11 = 10 + 1

6.2. RESTES CHINOIS : DEUX ALGORITHMES 39

on tire que 1 = 11 − 10 = 11 − (120 − 11 · 10) = 11 · 11 − 120. On obtient donc x1 = −120 qui estbien un multiple de 8 et de 15 et qui est congru a 1 modulo 11.Nous resolvons ensuite le systeme

x ≡ 0 (mod 11)

x ≡ 1 (mod 8)

x ≡ 0 (mod 15)

de la meme maniere. On a

165 = 8 · 20 + 5

8 = 5 + 3

5 = 3 + 2

3 = 2 + 1

d’ou l’on tire l’identite de Bezout

1 = 3− 2 = 3− (5− 3) = 2 · (8− 5)− 5 = 2 · 8− 3 · (165− 8 · 20) = 62 · 8− 3 · 165.

On a alors x2 = −3 · 165 = −495.Troisiemement, on resout le systeme

x ≡ 0 (mod 11)

x ≡ 0 (mod 8)

x ≡ 1 (mod 15)

ÃL’identite de Bezout 1 = 7 · 88− 41 · 15 donne x3 = 7 · 88 = 616.Finalement, on obtient

x = 3x1 + 6x2 − x3 = −3946qui est une solution du systeme propose. Si l’on veut la solution dont la valeur absolue est la pluspetite, on rajoute a −3946 des multiples de M = 8 · 11 · 15 = 1320 pour obtenir

x′ = −3946 + 3 · 1320 = 14.

6.2.2 Seconde methode

Une seconde methode pour resoudre un systeme de congruences comme (6.1) est de remplacer lesdeux premieres equations

x ≡ a1 (mod m1)

x ≡ a2 (mod m2)

par une unique equationx ≡ b (mod m1m2).

(On suppose toujours que les mi sont premiers deux a deux.)Pour ce faire, on ecrit

x = a1 +m1ux = a2 +m2t

(6.2)

ou u et t sont des entiers qui doivent satisfaire

a1 +m1u = a2 +m2t

ou encorem1u−m2t = a2 − a1.

Cette equation se resout a l’aide de l’identite de Bezout. Connaissant t et u, une solution au systeme(6.2) est

x = m1u+ a1 = b.

40 CHAPITRE 6. LE THEOREME DES RESTES CHINOIS

On peut maintenant remplacer les deux premieres equations par l’unique equation

x ≡ b (mod m1m2)

et continuer de maniere recursive jusqu’a ce qu’il ne reste qu’une seule equation.

Exemple 6.4. Resolvons le systeme

x ≡ 3 (mod 11)

x ≡ 6 (mod 8)

x ≡ −1 (mod 15)

par cette seconde methode. On commence par resoudre

x ≡ 3 (mod 11)

x ≡ 6 (mod 8)

en cherchant t et u tels que3 + 11t = 6 + 8u

ou11t− 8u = 3.

On peut resoudre ceci par l’algorithme d’Euclide et par Bezout mais ici, on constate que t = u = 1est une solution. Donc x ≡ 14 (mod 88) est une solution des deux premieres equations. On remplaceces deux equations par cette derniere et le systeme devient

x ≡ 14 (mod 88)

x ≡ −1 (mod 15).

On resout ce dernier systeme de la meme maniere en cherchant t et u tels que

14 + 88t = −1 + 15u.

On peut prendre t = 0 et u = 1 ce qui nous donne la solution finale

x ≡ 14 (mod 1320).

6.2.3 Une application : la fonction indicatrice d’Euler

Nous sommes maintenant en mesure de demontrer le theoreme 2.19 qui affirme que

ϕ(mn) = ϕ(m) · ϕ(n)

si m et n sont premiers entre eux.

On a besoin du lemme suivant :

Lemme 6.5. Soient A et B deux anneaux commutatifs et A×B l’anneau produit. Alors (a, b) ∈ A×Best une unite si et seulement si a et b sont des unites. En particulier, si |A∗| et |B∗| sont finis, alors

|(A×B)∗| = |A∗| · |B∗|.

Demonstration : Si a′ (resp. b′) est l’inverse de a (resp. b) alors

(a, b) · (a′, b′) = (aa′, bb′) = (1, 1)

ce qui montre que (a, b) est une unite de A×BReciproquement, si (a, b) est une unite dont l’inverse est (a′, b′), alors on a (aa′, bb′) = (1, 1) ce quiimplique que a (resp. b) est une unite de A (resp. B).

6.2. RESTES CHINOIS : DEUX ALGORITHMES 41

Demonstration du theoreme 2.19 : Soientm et n deux entiers premiers entre eux. On considerel’anneau

Z/mnZ.

Par le theoreme des restes chinois, on a un isomorphisme d’anneaux

f : Z/mnZ∼=−→ Z/mZ× Z/nZ.

Par definition, ϕ(mn) est le nombre d’unites dans l’anneau Z/mnZ. Or, un isomorphisme envoieune unite sur une unite et vice versa. Ainsi, si u ∈ (Z/mnZ)∗, alors

f(u) = (a, b)

est une unite dans l’anneau Z/mZ×Z/nZ. Par le lemme ci-dessus, le nombre d’unites dans l’anneauZ/mZ× Z/nZ est egal a ϕ(m) · ϕ(n). Par l’isomorphisme f il est aussi egal au nombre d’unites deZ/mnZ. On a donc le resultat cherche

ϕ(mn) = ϕ(m) · ϕ(n).

Chapitre 7

Anneau de polynomes et corps finis

7.1 Introduction

Dans ce chapitre nous allons etudier les polynomes a coefficients dans un corps. Ils forment unanneau qui a des proprietes semblables a l’anneau des entiers Z.En particulier, nous verrons qu’il existe une division euclidienne sur les polynomes, une notion depgcd et de ppcm ainsi qu’une unique factorisation en produit de polynomes irreductibles unitaires.De plus, l’identite de Bezout et le theoreme des restes chinois sont encore valables.Ces proprietes seront utilisees pour faire une construction similaire a celle faite pour obtenir lesanneaux Z/mZ. On peut en effet definir une notion de congruence modulo un polynome f et etudierles classes de congruences des polynomes modulo f . On obtient alors un anneau qui se comporte demaniere semblable a l’anneau Z/mZ. En particulier, si le polynome f est irreductible, on obtient uncorps. Ce resultat est analogue a celui qui affirme que Z/pZ est un corps si p est un nombre premier.En considerant des polynomes a coefficients dans un corps fini Fp, on pourra ainsi construire d’autrescorps finis qui auront un nombre d’elements egal a une puissance de p.

7.2 Anneau de polynomes

Soit R un anneau etf(X) = anX

n + · · ·+ a1X + a0

un polynome a coefficients dans R, i.e. ai ∈ R pour tout 0 ≤ i ≤ n. On suppose que an 6= 0 etl’entier n est alors le degre de f ; il est note deg f .L’ensemble des polynomes a coefficients dans R est note R[X]. Un polynome de degre nul est appeleun polynome constant. On a alors f(X) = r pour un certain r ∈ R et ceci montre que l’on al’inclusion R ⊂ R[X].L’addition et la multiplication des polynomes donnent une structure d’anneau a R[X]. L’element 0est le polynome constant f(X) = 0 et l’element 1 est le polynome constant f(X) = 1.Si l’anneau R est integre, on a la regle des degres

deg(fg) = deg(f) + deg(g).

Les unites de l’anneau R[X] sont les polynomes constants f(X) = r avec r ∈ R∗. En d’autres termes,l’inclusion R∗ ⊂ R[X]∗ est egalement une surjection.

Si aucune confusion n’est possible, on notera simplement f au lieu de f(X).

Notation et remarque importante : : Soient A et B deux anneaux et φ : A −→ B un homomor-phisme d’anneaux. Alors φ induit un homomorphisme d’anneaux, que l’on note encore φ par abusde notation,

φ : A[X] −→ B[X]

qui est defini comme suit : soit f(X) = anXn + · · ·+ a1X + a0 un element de A[X] ; on pose alors

φ(f)(X) = φ(an)Xn + · · ·+ φ(a1)X + φ(a0).

43

44 CHAPITRE 7. ANNEAU DE POLYNOMES ET CORPS FINIS

C’est bien un polynome a coefficients dans B.En general, si l’homomorphisme φ n’est “pas trop particulier” on notera meme f au lieu de φ(f) cequi est encore un abus de notation.Par exemple, soit f ∈ Z[X] un polynome a coefficients entiers comme par exemple f(X) = X4 +3X3 − 2X2 + 7X − 10 et soit

πd : Z −→ Z/dZ

l’homomorphisme d’anneaux qui envoie un entier sur sa classe modulo d. Alors le polynome f peut-etre vu comme un polynome a coefficients dans Z/dZ en appliquant πd a chaque coefficient. Onobtient, dans notre exemple, le polynome

πd(f) = X4 + [3]dX3 − [2]dX

2 + [7]dX − [10]d ∈ Z/dZ[X].

Cette notation est lourde et on fera l’abus de notation decrit ci-dessus en notant toujours f au lieude πd(f). On parlera donc encore du polynome

f(X) = X4 + 3X3 − 2X2 + 7X − 10

meme si on le considere dans Z/dZ. Il se peut alors que f se simplifie. Si l’on considere f dans lecorps F3, par exemple, on a

f(X) = X4 +X2 +X + 2

car 3 ≡ 0 (mod 3), −2 ≡ 1 (mod 3), 7 ≡ 1 (mod 3), etc . . .. Mais si l’on considere f dans F7, ildevient f(X) = X4 + 3X3 − 2X2 − 10.On peut encore utiliser les inclusions

Z ⊂ Q ⊂ R ⊂ C

pour considerer polynome a coefficients dans Z comme un polynome a coefficients dans Q ou dans Rou encore dans C. Dans tous ces cas, f s’ecrit de la meme maniere mais il est important de specifiersi on le “voit” comme un element de Q[X] ou de C[X] par exemple.

7.2.1 Division euclidienne

A partir de maintenant, nous nous restreignons au cas ou R = K est un corps. On a alors, commepour les entiers, une division euclidienne.

Theoreme 7.1 (Division euclidienne). Soit K un corps et soient f 6= 0 et g des polynomes deK[X]. Alors il existe des polynomes q, r ∈ K[X] tels que

g(X) = f(X)q(X) + r(X)

avec deg(r) < deg(f) et les polynomes q et r sont uniques avec ces proprietes.Le polynome r est appele le reste de la division de g par f .

C’est un resultat bien connu que nous ne demontrerons pas ici. Le lecteur interesse peut consulter[1].

Definition 7.2. Soient f, g ∈ K[X] deux polynomes. On dit que f divise g s’il existe q ∈ K[X] telque

g = fq.

On dit egalement que g est un multiple de f .

On verifie facilement que f divise g si et seulement si le reste de la division de g par f est nul.

Sif(X) = anX

n + · · ·+ a1X + a0

est un polynome a coefficients dans le corps K, on peut l’evaluer en tout element u de K. On definitdonc

f(u) = anun + · · ·+ a1u+ a0 ∈ K.

7.2. ANNEAU DE POLYNOMES 45

Theoreme 7.3. Soient f ∈ K[X] un polynome et u ∈ K un scalaire. Alors f(u) = 0 si et seulementsi le polynome X − u divise f .

Demonstration : Considerons la division euclidienne

f(X) = (X − u)q(X) + r(X)

avec deg(r) < deg(X − u) = 1. Ceci implique que r(X) = k ∈ K. On a donc f(u) = k et

f(u) = 0⇐⇒ (X − u) divise f.

Corollaire 7.4. Un polynome f ∈ K[X] de degre n a au plus n racines.

Un polynome f(X) = anXn + · · ·+ a1X + a0 est dit unitaire si an = 1.

On dit que deux polynomes f et g sont associes si f(X) = a · g(X) avec a ∈ K∗.

Definition 7.5 (PGCD). Soient f, g ∈ K[X]. On dit que p ∈ K[X] est un pgcd de f et g si p|f etp|g et si le degre de p est maximal pour cette propriete.

Il faut remarquer que le pgcd de deux polynomes n’est pas unique. En effet, si p est un pgcd, alorstout polynome associe a p est egalement un pgcd. En revanche, deux polynomes f et g ont un uniquepgcd unitaire qui sera note (f, g).

Theoreme 7.6 (Identite de Bezout). Soient f, g ∈ K[X] et p un pgcd de f et g. Alors il existedeux polynomes r et s tels que

r · f + s · g = p.

Definition 7.7 (Polynome irreductible). Soit f ∈ K[X]. On dit que f est irreductible sideg f > 0 et si l’egalite f = g · h implique que g ∈ K∗ ou h ∈ K∗.

Remarque 7.8. Il est important de noter que la notion d’irreductibilite depend du corps K surlequel “on regarde” le polynome. Par exemple, le polynome f(X) = X2 − 2 est irreductible dansQ[X] car 2 n’est pas un carre dans Q. En revanche, il est reductible dans R[X] car il se decomposeainsi : f(X) = (X −

√2)(X +

√2).

Il est donc essentiel de bien specifier sur quel corps l’on considere un polynome lorsque l’on affirmeson irreductibilite ou non.

Exemple 7.9. Considerons le polynome f(X) = X3 +X + 1. Comme ses coefficients sont 0 ou 1,on peut considerer que f est defini sur n’importe quel corps.Sur F2, on a f(0) = 1 = f(1) ce qui montre qu’il n’a pas de racines dans F2. Il est donc irreductiblepuisqu’il est de degre 3.En revanche, sur F3, il a une racine (f(1) = 1 + 1 + 1 = 0) et est donc reductible.On peut egalement montrer qu’il est irreductible sur Q. En revanche, il a une racine dans R car toutpolynome de degre impair a une racine reelle. Il est donc reductible sur R et, bien entendu, sur C.

Remarque 7.10. Dans l’exemple ci-dessus, une propriete importante a ete utilisee concernant lespolynomes de degres 2 ou 3. Il existe un critere simple d’irreductibilite pour de tels polynomes, asavoir qu’un polynome de degre 2 ou 3 est irreductible sur un corps K si et seulement s’il ne possedeaucune racine dans K.Cette affirmation n’est plus vraie pour les degres superieurs ou egaux a 4. Par exemple, le polynomef(X) = X4 +X3 + 2X2 +X + 1 n’a pas de racines dans Q puisque ses 4 racines complexes sont

i, −i, −1 + i√3

2et

−1− i√3

2.

Mais il n’est pas irreductible sur Q car

X4 +X3 + 2X2 +X + 1 = (X2 + 1)(X2 +X + 1).


Exemple 7.11.

1. Le polynome X2 + 2X + 1 est reductible sur n’importe quel corps puisqu’il possede −1 commeracine.

2. Le polynome f(X) = X4 +1 est irreductible sur Q. En revanche, sur un corps de caracteristiqueegale a 2, f est reductible car on a

X4 + 1 = (X2 + 1)2 = (X + 1)4.

Le polynome f est aussi reductible sur F7 comme le montre la decomposition

X4 + 1 = (X2 + 3X + 1)(X2 − 3X + 1).

Les polynomes irreductibles jouent un role analogue a celui des nombres premiers dans Z. Letheoreme suivant en est une illustration.

Theoreme 7.12 (Decomposition en produit d’irreductibles). Soit f ∈ K[X] un polynome dedegre > 0. Alors il existe des polynomes irreductibles et unitaires p1, p2, . . . , pr et une unite a ∈ K∗

tels que

f = a · p1 · p2 · · · pr.

De plus, cette decomposition est unique a l’ordre pres, c’est-a-dire que si f = b ·q1 ·q2 ·qs avec b ∈ K∗

et qj irreductibles unitaires , alors r = s, a = b et pour tout i, il existe j tel que pi = qj.

Demonstration : La demonstration se fait par reccurence sur le degre de f . Si deg(f) = 1 alors fest irreductible et on peut ecrire f = a · g ou a est le coefficient dominant de f et g est un polynomeirreductible et unitaire.

Supposons le theoreme demontre pour tout polynome de degre ≤ n. Soit f un polynome de degreegal a n + 1. Si f est irreductible, le resultat est demontre en mettant le coefficient dominant def en evidence. Si f n’est pas irreductible, alors il existe deux polynomes g et h avec f = gh etdeg(g),deg(h) ≤ n. Par hypothese de reccurence on a

g = a · p1 · · · pr

et

h = b · pr+1 · · · psou a, b ∈ K∗ et ou les pi sont des polynomes irreductibles unitaires. Mais alors

f = gh = (ab) · p1 · · · ps.

L’unicite se demontre de la meme maniere que pour la d’ecomposition d’un entier en produit depremiers (voir theoreme 1.15) et en utilisant le lemme suivant.

Lemme 7.13. Soit K un corps et soient p, f, g ∈ K[X] avec p irreductible. Alors si p divise leproduit fg, il divise f ou g.

La demonstration est similaire a celle du lemme 1.16.

Comme pour les nombres entiers, on notera plutot

f = a · pe11 · pe22 · · · pemm

ou les pi sont des polynomes irreductibles unitaires distincts et les ei sont des entiers > 0.

Definition 7.14. Soient f, g ∈ K[X] avec deg f,deg g > 0. On dit que f et g sont premiers entreeux si leurs pgcd sont les constantes, autrement dit si (f, g) = 1.

7.2. ANNEAU DE POLYNOMES 47

7.2.2 Congruences modulo un polynome

Definition 7.15. Soient f , g et m des polynomes de K[X] avec deg(m) > 0. On dit que lespolynomes f et g sont congrus modulo m si le polynome m divise le polynome f − g. On le note

f ≡ g (mod m).

Proposition 7.16. La relation de congruence mod m est une relation d’equivalence, i.e.

(i) f ≡ f (mod m) ;

(ii) f ≡ g (mod m) ⇔ g ≡ f (mod m) ;

(iii) si f ≡ g (mod m) et g ≡ h (mod m) alors f ≡ h (mod m).

La verification est immediate.

7.2.3 Classes de congruence

Comme dans le cas des nombres entiers, on peut construire les classes de congruences modulo unpolynome m. On regroupe tous les polynomes qui sont congrus (mod m) en une seule classe et l’onconsidere l’ensemble de toutes ces classes que l’on note

K[X]/(m).

La classe de f (mod m) est notee [f ]m.

Exemple 7.17. Soit R[X] et m = X3 − 2X + 1. Prenons f(X) = X4 et g(X) = 2X2 −X. Comme

f(X) = m(X) ·X + g(X)

on a que f ≡ g (mod m). La classe [f ]m contient aussi, outre f et g, le polynome

h = 3X4 − 4X2 + 2X

car h(X) = f(X) + 2X ·m(X). Ainsi

[X4]m = {X4, 2X2 −X, 3X4 − 4X2 + 2X, . . .}.

Definition 7.18 (Representant d’une classe). Soit [f ]m une classe de congruence modulo m.Tout polynome de cette classe est appele un representant de la classe [f ]m.

Le lemme suivant nous permettra de definir une addition et une multiplication sur K[X]/(m).

Lemme 7.19. Soit m(X) ∈ K[X] un polynome de degre > 0 et soient f, g, f ′, g′ ∈ K[X] despolynomes satisfaisant f ≡ f ′ (mod m) et g ≡ g′ (mod m). Alors

f + g ≡ f ′ + g′ (mod m) et

fg ≡ f ′g′ (mod m).

La demonstration est similaire a celle du theoreme 2.5.

Le lemme precedent nous permet de definir une addition et une multiplication sur K[X]/(m) qui enfont un anneau. Il suffit de definir

[f ]m + [g]m = [f + g]m

et[f ]m · [g]m = [fg]m.

En d’autres termes, pour additionner (resp. multiplier) deux classes de congruences, il suffit d’ad-ditionner (resp. multiplier) deux representants de chaque classe et de prendre la classe du resultat.

Notation : On notera ξ la classe mod m du polynome X. Un element de A = K[X]/(m) est alorsun polynome en ξ. L’anneau A sera note K[ξ].


Exemple 7.20. Considerons R[X] et le polynome m(X) = X2 + 1. Nous allons etudier l’anneauA = R[X]/(X2 + 1).Soit f ∈ R[X]. On peut effectuer la division euclidienne de f par m pour trouver

f = qm+ r

ou deg r < 2. Ainsi tout polynome est congru mod m a un polynome de degre 0 ou 1. On peut doncrepresenter chaque classe de A par un polynome

aX + b.

Comme X2 = X2 + 1− 1, on a X2 ≡ −1 (mod m) et donc [X2] = [−1].Si l’on note ξ la classe de X, on a alors ξ2 = −1.

A = R[X]/(X2 + 1) = {aξ + b | a, b ∈ R}L’addition de chaque classe est l’addition usuelle, c’est-a-dire que

(aξ + b) + (cξ + d) = (a+ c)ξ + (b+ d).

Etudions le produit de deux classes. On a

(aξ + b) · (cξ + d) = acξ2 + adξ + bcξ + bd

= (ad+ bc)ξ + bd− ac

car ξ2 = −1.On a ainsi expliciter les lois d’addition et de multiplication de l’anneau R[X]/(X2+1). Si l’on observeattentivement ce qui precede, on constate que l’on peut remplacer ξ par le nombre complexe i sansrien changer. L’anneau que l’on vient de construire n’est donc rien d’autre que le corps des nombrescomplexes C.

R[X]/(X2 + 1) ∼= C.

Dans le cas des entiers, l’on sait que Z/mZ est un corps si et seulement si m est un nombre premier.On a ici un resultat analogue :

Theoreme 7.21. L’anneau K[X]/(m) est un corps si et seulement si m(X) est irreductible.

Demonstration : Supposons que m soit irreductible et montrons que toute classe non nulle estinversible. Soit f un representant d’une telle classe. Alors m ne divise pas f (sinon on aurait [f ]m =[0]m). Mais commem est irreductible, ceci implique que f etm sont premiers entre eux. Par l’identitede Bezout, il existe des polynomes r et s tels que

fr + sm = 1.

En considerant l’equation precedente modulo m, on obtient

[f ]m · [r]m = [1]m

ce qui montre que la classe [r]m est l’inverse de la classe [f ]m.Reciproquement, supposons que m = p · q avec deg(p),deg(q) > 0. Les classes [p]m et [q]m sont nonnulles dans K[X]/(m) car m ne divise ni p ni q. Mais comme pq = m on a

[p]m · [q]m = [m]m = [0]

ce qui montre que K[X]/(m) possede des diviseurs de zero. Ce n’est donc pas un corps.

Remarque 7.22. La preuve du theoreme precedent a montre que seules deux possibilites peuventse presenter : soit K[X]/(m) est un corps, soit il possede des diviseurs de zero. On retrouve unresultat qui est vrai pour Z/mZ.

Remarque 7.23. Soit F un corps et f ∈ F [X] un polynome irreductible (sur F ). Considerons alorsle corps K = F [X]/(f). Par construction, si l’on note ξ la classe de X dans K, alors f(ξ) = 0. Lepolynome f est donc reductible sur K puisqu’il y possede une racine.

7.3. THEOREME DES RESTES CHINOIS 49

7.3 Theoreme des restes chinois

Theoreme 7.24. Soient f, g ∈ K[X] deux polynomes premiers entre eux. Alors

K[X]/(fg) ∼= K[X]/(f)×K[X]/(g).

Esquisse de la demonstration : On considere l’homomorphisme d’anneaux

T : K[X]/(fg) −→ K[X]/(f)×K[X]/(g)

[q]fg 7→ ([q]f , [q]g).

On montre d’abord que T est injectif. En effet, supposons que T ([q]fg) = 0. Ceci veut dire que q estcongru a 0 modulo f et modulo g. Comme f et g sont premiers entre eux, ceci implique que q estcongru a 0 modulo fg et donc que [q]fg = [0]fg. Ceci montre que le noyau de T est trivial et doncque T est injectif par le theoreme 3.24.Pour demontrer la surjectivite, on utilise un resultat d’algebre lineaire. Posons n = deg(f) et m =deg(g).L’anneau K[X]/(fg) est un espace vectoriel sur K. Sa dimension est egale au degre du polynomefg a savoir n + m. D’autre part, les anneaux K[X]/(f) et K[X]/(g) sont aussi des K-espacesvectoriels de dimensions n et m respectivement. Le produit K[X]/(f) × K[X]/(g) est donc dedimension m + n. L’application T etant un homomorphisme d’anneaux, elle est K-lineaire. Maison sait qu’une application lineaire injective entre deux espaces vectoriels de meme dimension estegalement surjective. Ceci termine la demonstration.

Corollaire 7.25. Soient f1, . . . fn ∈ K[X] des polynomes premiers deux a deux ( i.e. (fi, fj) = 1 sii 6= j). Alors

K[X]/(f1f2 · · · fn) ∼= K[X]/(f1)×K[X]/(f2)× · · · ×K[X]/(fn).

Corollaire 7.26 (Theoreme des restes chinois). Soient f1, . . . fn ∈ K[X] des polynomes pre-miers deux a deux et g1, . . . , gn ∈ K[X] des polynomes quelconques. Alors il existe un polynomeF ∈ K[X] qui satisfait le systeme de congruences

F ≡ g1 (mod f1)

F ≡ g2 (mod f2)

...

F ≡ gn (mod fn)

En pratique, pour trouver un polynome F , il faut appliquer le meme algorithme que dans le casdes entiers (cf. section 6.2). En particulier, l’algorithme d’Euclide s’adapte au cas des polynomes etpermet de trouver un pgcd de deux polynomes et egalement une identite de Bezout.

7.4 Corps finis

La section precedente nous permet de construire des corps finis a partir du corps Fp et d’un polynomede Fp[X] irreductible.Soit p un nombre premier. Nous avons vu que Fp = Z/pZ est un corps. Choisissons alors un polynomef ∈ Fp[X] irreductible et de degre n. L’anneau

Fp[X]/(f)

est un corps par le theoreme 7.21.Un element de Fp[X]/(f) est une classe de polynomes modulo f . Toute classe peut etre representeepar un polynome de degre < n. De plus deux polynomes distincts de degres < n ne sont pas congrusmod f et representent ainsi deux classes differentes. Il y a donc exactement autant d’elements dansFp[X]/(f) qu’il y a de polynomes de degre < n a coefficients dans Fp. Ce nombre est egal a pn. Ona donc montre que Fp[X]/(f) est un corps a pn elements ou n = deg(f).


Exemple 7.27. Considerons le corps F2 = {0, 1} et le polynome

f(X) = X2 +X + 1 ∈ F2[X].

On verifie que f est irreductible (ici, il suffit de voir que f(0) 6= 0 et f(1) 6= 0). Le corps K =F2[X]/(f) a 22 = 4 elements qui sont

0, 1, ξ, ξ + 1.

La loi de multiplication est donnee par la table ci-dessous

· 1 ξ ξ + 11 1 ξ ξ + 1ξ ξ ξ + 1 1

ξ + 1 ξ + 1 1 ξ

Verifions, par exemple, que ξ · ξ = ξ+1. Comme ξ est la classe de X, on a ξ2 + ξ+1 = 0, ou encoreξ2 = −ξ − 1 = ξ + 1 car les coefficients sont dans F2.De meme, ξ · (ξ + 1) = ξ2 + ξ = 1 toujours en utilisant la relation ξ2 + ξ + 1 = 0.

Exemple 7.28. Partons du corps F3 et du polynome f(X) = X2 + 1 ∈ F3[X]. On verifie que f estirreductible car f(0) = 1 6= 0, f(1) = 2 6= 0 et f(2) = 2 6= 0. L’anneau A = F3[X]/(X2 +1) est doncun corps a 32 = 9 elements. Ses elements peuvent etre notes

aξ + b

avec a, b ∈ F3. Ces 9 elements sont donc

0, 1, 2, ξ, ξ + 1, ξ + 2, 2ξ, 2ξ + 1, 2ξ + 2.

Voici la table de multiplication de ce corps :

2 ξ ξ + 1 ξ + 2 2ξ 2ξ + 1 2ξ + 22 1 2ξ 2ξ + 2 2ξ + 1 ξ ξ + 2 ξ + 1ξ 2ξ 2 ξ + 2 2ξ + 2 1 ξ + 1 2ξ + 1

ξ + 1 2ξ + 2 ξ + 2 2ξ 1 2ξ + 1 2 ξξ + 2 2ξ + 1 2ξ + 2 1 ξ ξ + 1 2ξ 22ξ ξ 1 2ξ + 1 ξ + 1 2 2ξ + 2 ξ + 2

2ξ + 1 ξ + 2 ξ + 1 2 2ξ 2ξ + 2 ξ 12ξ + 2 ξ + 1 2ξ + 1 ξ 2 ξ + 2 1 2ξ

Pour trouver cette table, on uilise simplement le fait que ξ2 + 1 = 0 donc que

ξ2 = −1 = 2.

Pour le reste, on multiplie normalement, l’on remplace ξ2 par 2 et l’on simplifie en tenant comptedu fait que les coefficients sont pris dans F3. Par exemple

(2ξ + 1)(ξ + 2) = 2ξ2 + 5ξ + 2 = 4 + 2ξ + 2 = 2ξ.

7.4.1 Existence et unicite des corps finis

Dans ce paragraphe, nous allons voir qu’il existe toujours un corps fini a pn elements pour toutpremier p et pour tout entier n ≥ 1. De plus, nous montrerons que pour p et n fixes, ce corps estunique a isomorphisme pres. Ceci signifie que deux corps K et K ′ qui sont finis et qui ont le memenombre d’elements sont isomorphes.Pour arriver a ces resultats, il nous faut d’abord construire un corps qui contienne toutes les racinesd’un polynome f . C’est l’objet de la proposition suivante.

Proposition 7.29. Soit F un corps et f ∈ F [X] un polynome. Alors il existe un corps K contenantF et qui contient toutes les racines de f .

7.4. CORPS FINIS 51

Esquisse de la demonstration : Soit f = ph avec p ∈ F [X] irreductible. Alors K1 = F [X]/(p)est un corps qui contient F . De plus, dans le corps K1, le polynome p possede une racine a savoir laclasse de X que l’on a note ξ. Cette racine est egalement une racine de f et on peut faire la divisioneuclidienne

f = (X − ξ)g.

On a alors deg(g) < deg(f). On conclut la preuve par recurrence sur le degre de f .

Exemple 7.30. Soit F = Q le corps des rationnels et f = X3 − 2 ∈ Q[X]. On peut verifier que fest irreductible sur Q (il ne contient aucune racine dans Q). On considere alors le corps

K1 = Q[X]/(X3 − 2)

et on note ξ la classe de X dans K1. On a donc ξ3 − 2 = 0 et donc ξ3 = 2. Ainsi le corps K1 estun corps qui contient Q et qui contient une racine cubique de 2. Les contient-il tous ? Pour cela, oneffectue la division euclidienne de X3 − 2 par X − ξ dans le corps K1.

X3 −2−X3 +ξX2

ξX2 −2−ξX2 +ξ2X

ξ2X −2−ξ2X +ξ3

0

X − ξ

X2 + ξX + ξ2

Le reste vaut 0 car ξ3−2 = 0. On peut montrer que le polynome g(X) = X2+ξX+ξ2 est irreductibledans K1. Le corps K1 ne contient donc pas toutes les racines de f et il faut considerer le corps

K = K1[X]/(g).

Cette fois, dans K, le polynome f se decompose en produit de polynomes du premier degre.Si l’on se plonge dans C, la construction precedente peut se resumer comme suit : on rajoute 3

√2 a

Q et on obtient le corps K1. Puis on rajoute le nombre complexe j defini par j3 = 1 au corps K1 eton obtient K. Le corps K contient alors les 3 racines de f a savoir 3

√2, 3√2j et 3

√2 · j ou j designe

le conjugue de j.

Avant de construire un corps a pn elements, il nous faut un critere pour savoir si un polynomepossede une racine multiple.On introduit pour ce faire la notion de derivee d’un polynome (qui est connue de tous).

Definition 7.31 (Derivee d’un polynome). Soit

f(X) = anXn + · · ·+ a1X + a0

un polynome a coefficients dans K. Alors la derivee de f est le polynome

f ′(X) = nanXn−1 + (n− 1)an−1X

n−2 + · · ·+ 2a2X + a1.

La derivee satisfait les proprietes bien connues :

(f + g)′ = f ′ + g′

(kf)′ = kf ′

(fg)′ = f ′g + fg′

pour tout f, g ∈ K[X] et tout element k ∈ K.

Ce qui est peut-etre moins connu, c’est que la derivee d’un polynome f peut etre le polynome nulsans que f soit un polynome constant.


Exemple 7.32. Soit f(X) = X6+X3+1 un polynome a coefficients dans F3. Alors sa derivee vaut

f ′(X) = 6X5 + 3X2 ≡ 0

car les classes de 3 et 6 sont nulles dans F3.

L’exemple ci-dessus montre que la derivee d’un polynome depend fortement du corps dans lequel onle considere.

On est maintenant en mesure de donner un critere pour savoir si un polynome admet une racinemultiple :

Lemme 7.33. Soient f ∈ K[X] et α ∈ K une racine de f . Alors α est une racine multiple de fsi et seulement si f ′(α) = 0.

Demonstration :Comme α est une racine de f , on peut faire une division eulidienne par X −α lenombre de fois qu’il faut pour avoir

f(X) = (X − α)ng(X)

avec g(α) 6= 0 et n ≥ 1. En derivant des deux cotes on obtient

f ′(X) = n(X − α)n−1g(X) + (X − α)ng′(X). (7.1)

Supposons maintenant que α est une racine multiple, c’est-a-dire que n > 1. Alors en evaluant laderniere egalite en α, on obtient

f ′(α) = 0 · g(α) + 0 = 0

ce qui montre la necessite de la condition.Reciproquement, si α n’est pas une racine multiple, alors n = 1 et l’egalite (7.1) devient

f ′(X) = g(X) + (X − α)g′(X).

Evaluee en α, on trouve f ′(α) = g(α) 6= 0 ce qui prouve la suffisance de la condition.

Exemple 7.34. Sur n’importe quel corps, le polynome X2 − 2X + 1 se decompose en

(X − 1)2.

Il a donc une racine double qui est 1. Ceci se verifie sur la derivee. En effet, la derivee de f vaut

f ′(X) = 2X − 2 = 2(X − 1)

et s’annule aussi en 1.Considerons le polynome f(X) = X3 − 1. Sa derivee vaut

f ′(X) = 3X2.

Si la caracteristique du corps est differente de 3, alors f ′ ne s’annule qu’en 0. Mais, d’autre part,f(0) = −1 6= 0. Ceci prouve que f n’a pas de racines multiples en caracteristique differente de 3.En revanche, si la caracteristique vaut 3 - par exemple sur F3 - alors f ′ est le polynome nul ets’annule donc en tout point du corps considere. En particulier, f ′(α) = 0 pour toute racine α de f .Ceci prouve que f(X) = X3 − 1 a une racine multiple. En fait, en caracteristique 3, on a

(X − 1)3 = X3 − 1 = f(X)

ce qui montre que 1 est une racine de f de multiplicite egale a 3.

Theoreme 7.35. Soit p un nombre premier et soit n un entier ≥ 1. Alors il existe un corps a pn

elements.

7.4. CORPS FINIS 53

Demonstration : Posons q = pn et considerons le polynome f(X) = Xq − X ∈ Fp[X]. Par letheoreme precedent, il existe un corps K contenant Fp et toutes les racine de f . Soit F le sous-ensemble de K qui consiste en les racines de f . Alors F contient exactement pn elements et F estun corps.En effet, la derivee de f est

f ′ = qXq−1 − 1 = −1 ∈ Fp[X]

ou la derniere egalite vient du fait que q = pn et donc que q · 1 = 0 dans Fp. Comme f ′ est unpolynome constant, il n’a aucune racine commune avec f , ce qui implique que f n’a pas de racinesmultiples. Le polynome f a donc pn racines distinctes.Montrons que F est un corps. Pour tout a ∈ K, on a

a ∈ F ⇐⇒ aq = a

par definition de F . Mais si a, b ∈ F , alors

(a+ b)q = aq + bq = a+ b (7.2)

ce qui montre que a+b ∈ F . La premiere egalite dans (7.2) vient du fait que l’on est en caracteristiquep.On a aussi

(ab)q = aqbq = ab

et donc ab ∈ F . Supposons que a ∈ F , a 6= 0. Alors

(a−1)q = (aq)−1 = a−1

et donc a−1 ∈ F . Finalement, on a que (−a)q = −aq = −a et donc −a ∈ F .Ceci prouve que F est un corps.

On peut montrer, ce que nous ne ferons pas ici, que tout corps fini F a pn elements peut s’ecrire

F = Fp[X]/(f)

ou f ∈ Fp[X] est irreductible de degre n. On a alors :

Corollaire 7.36. Soit p un nombre premier et n un entier ≥ 1. Alors il existe un polynomeirreductible f ∈ Fp[X] de degre n.

Remarque 7.37. Ce resultat est aussi vrai si l’on prend Q comme corps de base. En revanche, sil’on prend le corps R, les polynomes irreductibles sont alors forcement de degres 1 ou 2. Et dans C,seuls les polynomes de degre 1 sont irreductibles. On dit que C est algebriquement clos.

Proposition 7.38. Soit p un nombre premier et n un entier ≥ 1. Soit f ∈ Fp[X] un polynomeirreductible de degre m avec m|n. Alors f divise Xpn −X.

Demonstration : Considerons le corps

K = Fp[X]/(f) = Fp(ξ)

ou ξ est la classe de X mod f . C’est un corps a pm elements. L’element ξ appartient au groupemultiplicatif K∗ qui est d’ordre pm − 1. Par le theoreme de Lagrange, on a alors que

ξpm−1 = 1

autrement dit ξpm

= ξ. Mais comme m|n, si l’on pose q = pn, on a encore ξq = ξ.Supposons maintenant, par l’absurde, que f ne divise pas Xq −X. Ils sont donc premiers entre euxpuisque f est irreductible et on a une identite de Bezout

r(X)f(X) + s(X)(Xq −X) = 1.


Evaluee en ξ, cette identite devient

r(ξ)f(ξ) + s(ξ)(ξq − ξ) = 1.

Mais comme f(ξ) = 0 et ξq = ξ, on trouve 0 = 1 ce qui est une contradiction. Donc f divise Xq−X.

Nous arrivons maintenant a l’unicite du corps a pn elements pour p et n fixes.

Theoreme 7.39. Soient p un nombre premier et n un entier ≥ 1. Soient K et K ′ des corps a pn

elements. Alors K ∼= K ′.

Demonstration : Posons q = pn et F l’ensemble des racines de Xq −X. Nous avons vu dans lapreuve du theoreme 7.35 que F est un corps a pn elements. Nous allons demontrer que K ∼= F . Ceciimpliquera par symetrie que K ′ ∼= F et donc que K ∼= K ′.On peut ecrire

K = Fp[X]/(f)

ou f ∈ Fp[X] est irreductible de degre n. Par la proposition 7.38, le polynome f divise Xq −X. Ilexiste donc une racine α de f qui est dans F . On definit alors un homomorphisme d’anneaux

φ : Fp[X] −→ F

par φ(X) = α et φ(a) = a pour tout a ∈ Fp. Le noyau de φ contient l’ideal (f) et comme f estirreductible, on a Ker(φ) = (f). On a alors un homomorphisme injectif (voir le theoreme 3.40)

φ : K = Fp[X]/(f) −→ F

qui est egalement surjectif car F et K ont tous les deux pn elements. C’est donc un isomorphisme.

Notation : L’unique corps a q = pn elements est note Fq.

Attention : si n > 1

Fq 6= Z/qZ

puisque, dans ce cas, Z/qZ n’est pas un corps.

Remarque 7.40. Soit q = pn. Alors Fq est de caracteristique p (et non pas q ! !)

Exemple 7.41. Construisons le corps a 8 = 23 elements. Il suffit pour cela de trouver un polynomef a coefficient dans F2 qui soit irreductible et de degre 3. Prenons f(X) = X3 + X + 1. Commef(0) = 1 = f(1), f est irreductible. On a alors

F8 = F2[X]/(f).

Explicitons les elements de F8. Chaque classe peut etre representee par un unique polynome acoefficients dans F2 et de degre ≤ 2. Si l’on note ξ la classe de X, on a alors les 8 elements de F8 :

0 1 ξ ξ + 1 ξ2 ξ2 + 1 ξ2 + ξ ξ2 + ξ + 1.

La table de multiplication est obtenue en utilisant la relation f(ξ) = 0, c’est-a-dire ξ3 = ξ + 1.

ξ ξ + 1 ξ2 ξ2 + 1 ξ2 + ξ ξ2 + ξ + 1ξ ξ2 ξ2 + ξ ξ + 1 1 ξ2 + ξ + 1 ξ2 + 1

ξ + 1 ξ2 + 1 ξ2 + ξ + 1 ξ2 1 ξξ2 ξ2 + ξ ξ ξ2 + 1 1

ξ2 + 1 ξ2 + ξ + 1 ξ + 1 ξ2 + ξξ2 + ξ ξ ξ2

ξ2 + ξ + 1 ξ + 1

7.4. CORPS FINIS 55

Verifions par exemple que (ξ2 + ξ)(ξ2 + ξ + 1) = ξ2. On a

(ξ2 + ξ)(ξ2 + ξ + 1) = ξ4 + ξ3 + ξ2 + ξ3 + ξ2 + ξ

= ξ4 + ξ

= ξ(ξ3) + ξ

= ξ(ξ + 1) + ξ

= ξ2 + ξ + ξ = ξ2.

Remarque 7.42. Nous avons montre, dans la demonstration du theoreme 7.38 que ξq = ξ, a l’aidedu theoreme de Lagrange. En fait, ce resultat est vrai pour tout element de Fq. On a donc

aq = a pour tout a ∈ Fq.

7.4.2 Isomorphismes de Frobenius

Theoreme 7.43. Pour tout corps K de caracteristique p, l’application

K −→ K

x 7→ xp

est un homomorphisme de corps. Il est donc injectif. De plus, si K est fini, alors c’est un isomor-phisme.

Demonstration : la preuve est laissee en exercice.

Remarque 7.44. Notons que si K = Fp, alors l’isomorphisme de Frobenius n’est rien d’autre quel’identite. En effet, pour tout a ∈ Fp, on a ap = a par le petit theoreme de Fermat.

Exemple 7.45. Considerons le corps F8 construit dans l’exemple 7.41. Il est de caracteristique 2est l’isomorphisme de Frobenius est donc

φ : F8 −→ F8

a 7→ a2.

Explicitons l’action de φ sur tous les element de F8.

φ(0) = 0 φ(1) = 1 φ(ξ) = ξ2

φ(ξ2) = ξ + ξ2 φ(1 + ξ) = 1 + ξ2 φ(1 + ξ2) = 1 + ξ + ξ2

φ(ξ + ξ2) = ξ φ(1 + ξ + ξ2) = 1 + ξ

Si on applique φ une seconde fois, on trouve que φ ◦ φ(ξ) = ξ + ξ3 et donc que

φ ◦ φ ◦ φ(ξ) = φ(ξ + ξ2) = ξ.

Comme ξ engendre F8, on a

φ◦3 = Id.

L’observation de l’exemple precedent se generalise a tous les corps finis. On utilise la notation

φ◦n := φ ◦ φ ◦ · · · ◦ φ︸︷︷︸

n fois

.

Theoreme 7.46. Soient p un premier, q = pn et Fq le corps a q elements. Soit φ : Fq → Fql’automorphisme de Frobenius. Alors

φ◦n = Id.


Demonstration : Soit a ∈ Fq. Alors

φ◦n(a) = apn

= aq = a

par la remarque 7.42 ci-dessus. On a donc le resultat cherche.

Remarque 7.47. On peut montrer un resultat un peu plus fort que le theoreme precedent, a savoirque l’isomorphisme de Frobenius est exactement d’ordre n dans le groupe Aut(Fq) des automor-phismes de Fq. On peut meme montrer qu’il engendre ce groupe, c’est-a-dire que

Aut(Fq) ={

Id, φ, φ ◦ φ, · · · , φ◦(n−1)}

ou φ est l’isomorphisme de Frobenius et q = pn.En d’autres termes, les seuls automorphismes d’un corps fini sont le Frobenius et ses compositions.

Bibliographie

[1] L. Childs. A Concrete Introduction to Higher Algebra. Undergraduate Texts in Mathematics.Springer-Verlag, Inc. New York, 1995.

[2] S. Lang. Undergraduate Algebra. Undergraduate Texts in Mathematics. Springer-Verlag, Inc.New York, second edition, 1990.

57

58 INDEX

Index

anneau, 17commutatif, 18integre, 19principal, 23

anneau de polynomes, 43

Bezout, identite de, 3, 45bijective, application, 22

caracteristique d’un anneau, 24classes de congruence, 11, 47congruence mod m, 9congruence modulo un polynome, 46corps, 19

fini, 20, 49

derivee d’un polynome, 51diviseur, 1, 44diviseur de zero, 19divisibilite, 1, 44division euclidienne, 2, 44

element neutre, 29entier, 1

naturel, 1Euclide, algorithme d’, 3Euclide, theoreme, 6Euler, theoreme d’, 28

factorisation en produit de premiers, 5Fermat, petit theoreme de, 28Frobenius, isomorphisme de, 55

groupe, 29abelien, 29commutatif, 29cyclique, 31fini, 30

homomorphisme d’anneaux, 20

ideal, 23principal, 23trivial, 23

injective, application, 22inverse, 12

Lagrange, theoreme de, 31

modulus, 9multiple, 1, 44

nombrecomplexe, 1entier, 1premier, 1

rationnel, 1reel, 1

nombres premiers entre eux, 2noyau d’un homomorphisme, 22, 33

ordre d’un element, 30ordre d’un entier (mod m), 27ordre d’un groupe fini, 30

pgcd, 2, 45plus grand commun diviseur, 2, 45plus petit commun multiple, 7polynome

irreductible, 45unitaire, 45

polynomes associes, 45ppcm, 7produit de premiers, decomposition en, 5

racine multiple, 51representant, 12, 47restes chinois, algorithme des, 38restes chinois, theoreme des, 37, 49

sous-anneau, 18sous-groupe, 30surjective, application, 22

table de multiplicationd’un groupe, 34

theoreme fondamental de l’arithmetique, 4

unite, 12, 19

INDEX DES NOTATIONS 59

Index des notations

]G - ordre du groupe G, 30

(a, b) - pgcd de a et b, 2[a, b] - ppcm de a et b, 7a ≡ b (mod m) - a et b sont congrus modulo m, 9a|b - a divise b, 1[a]m - classe de congruence de a mod m, 12, 47

C, 1

f ≡ g (mod m) - f et g sont congrus modulo m, 46ϕ(n) - indicatrice d’Euler, 13Fq - corps fini a q elements, 20, 54

|G| - ordre du groupe G, 30< g > - sous-groupe engendre par g, 31

Ker(f) - noyau de f , 22K(ξ) - anneau obtenu de K en ajoutant ξ, 47K[X] - anneau de polynomes, 43K[X]/(m) - anneau de polynomes mod m, 47

N, 1

Q, 1

R, 1(r) - ideal engendre par r, 23R∗ - ensemble des unites de R, 19R, S - anneaux, 17

Z, 1Z/mZ, 11

60 GLOSSAIRE

Glossaire francais - anglais

Francais Anglais

anneau ringcaracteristique characteristiccommutatif commutativecorps fieldcorps fini finite field (or Galois field)cyclique cyclicdiviseur divisorensemble setnombre entier integerfactorisation factorizationgroupe groupimpair oddinjectif one to oneintegre, anneau integral ringirreductible irreduciblenombre premier prime numbernoyau kernelordre d’un groupe order of a grouppair evenplus grand commun diviseur (pgcd) greatest common divisors (gcd)plus petit commun multiple (ppcm) least common multiple (lcm)premiers entre eux coprime (or relatively prime)racine rootracine carree square rootrepresentant representativerestes chinois, theoreme des Chinese remainder theoremsous-anneau subringsurjectif ontosymetrique symmetricunitaire (polynome) monic (polynomial)unite unit

Documents

Algµebrepourcommunicationsnum¶eriques Sections ... · siad=bc. Le symbole R d¶esigne les nombres r¶eels : sans ^etre rigoureux dans la d¶eﬂnition, on peut voir les nombres