Table des mati eres - math.sciences.univ-nantes.frmorame/SYM04/Alg052P.pdfSYM0400, Alg ebre de base. 1 LICENCE 2004/2005 de l’UNIVESITE de NANTES SYM0400 , ALGEBRE de BASE 11 Janvier

SYM0400, Algebre de base. 1

LICENCE 2004/2005 de l’UNIVESITE de NANTESSYM0400 , ALGEBRE de BASE

11 Janvier 2005

Resume

Ce manuel est constitue de notes de cours destinees aux etudiants

de premiere annee de la licence ayant choisi au deuxieme semestre

l’option math-info.

Pour utiliser les index de la fin de ce document, regarder aussi

la pagee suivante a celle indiquee, si vous ne trouver pas la bonne

defintion dans la page cerrespondante.

Table des matieres

1 Ensembles, logique, applications, relations binaires 31.1 Ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Logique et techniques de demonstration . . . . . . . . . . . . . 5

1.2.1 Loi de De Morgan et table des verites . . . . . . . . . . 51.2.2 Techniques de demonstration . . . . . . . . . . . . . . 6

1.3 Les applications . . . . . . . . . . . . . . . . . . . . . . . . . . 71.4 Denombrement . . . . . . . . . . . . . . . . . . . . . . . . . . 101.5 Relation binaire sur E, relation d’equivalence . . . . . . . . . . 131.6 Ordre partiel, ordre total . . . . . . . . . . . . . . . . . . . . . 151.7 Lois de composition interne . . . . . . . . . . . . . . . . . . . 17

1.7.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . 171.7.2 Monoıde . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.8 Algebre de Boole et exemples . . . . . . . . . . . . . . . . . . 19

2 Arithmetique dans Z 202.1 Representation des entiers . . . . . . . . . . . . . . . . . . . . 202.2 Division euclidienne dans N et nombres premiers . . . . . . . 212.3 PGCD et PPCM dans N . . . . . . . . . . . . . . . . . . . . . 222.4 Groupe et sous-groupe: une introduction . . . . . . . . . . . . 232.5 Relation de Bezout dans Z . . . . . . . . . . . . . . . . . . . 262.6 Une petite application a l’ordre d’un groupe . . . . . . . . . . 292.7 Congruence dans Z . . . . . . . . . . . . . . . . . . . . . . . . 292.8 Groupe quotient . . . . . . . . . . . . . . . . . . . . . . . . . . 312.9 Definitions d’anneau, anneau commutatif et integre . . . . . . 322.10 L’anneau Zm . . . . . . . . . . . . . . . . . . . . . . . . . . . 352.11 Notion d’ideal et anneau quotient . . . . . . . . . . . . . . . . 38


3 Polynomes 393.1 Definition et proprietes . . . . . . . . . . . . . . . . . . . . . . 393.2 Formule de Taylor . . . . . . . . . . . . . . . . . . . . . . . . . 423.3 Division euclidienne . . . . . . . . . . . . . . . . . . . . . . . . 443.4 Adjonction de racine: extension de corps . . . . . . . . . . . . 46

4 Treillis et points fixes 484.1 Borne superieure et borne inferieure . . . . . . . . . . . . . . . 484.2 Les treillis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504.3 Points fixes pour les applications croissantes . . . . . . . . . . 51

5 Notations et indexes 52


1 Ensembles, logique, applications, relations

binaires

1.1 Ensembles

Des objets constituent un ensemble et ces objets sont appeles les elementsde cet ensemble.

Si E est un ensemble et si c est un objet qui est un element de E, on ditque c appartient a l’ensemble E, on ecrit symboliquement: c ∈ E .

La propriete pour un objet, un element d, de ne pas appartenir a unensemble A se note d /∈ A .

Pour definir un ensemble, on utilise en general les crochets { et } , parexemple

V oyelles = {a, e, i, o, u, y} ,

Entiers impairs = {2n + 1; n ∈ N} .

Par convenance, on introduit un ensemble particulier qui n’est constituepar aucun objet et qu’on appelle ensemble vide est qui est note ∅ .

Deux ensembles E et F sont dits egaux s.s.s. (si et seulement si) ilssont constitues par les memes elements: on ecrit E = F .

Un ensemble A est dit un sous-ensemble de E s.s.s. tout element de Aest aussi un element de E: cette propriete est notee A ⊂ E .

L’ensemble vide est un sous-ensemble de tout ensemble E .Si c ∈ E , alors l’ensemble constitue du seul element c est note {c} :

il clair que {c} ⊂ E .Si on considere les objets qui sont les sous-ensembles d’un ensemble E ,

alors ils constituent un ensemble note P(E) et appele ensemble des par-ties de de E .

On a toujours ∅ ∈ P(E) et E ∈ P(E) .Operations sur les ensembles

L’union de deux ensemble A et B est l’ensemble A∪B dont les elementsconstituants sont ceux de A et ceux de B .

L’intersection de deux ensembles A et B est l’ensemble A ∩ B dontles elements constituants, quand ils existent, sont ceux qui appartiennent ala fois a A et a B .

On dit que deux ensembles A et B sont disjoints s.s.s. A ∩ B = ∅ .La difference de l’ensemble A par l’ensemble B est l’ensemble A \ B

dont les elements constituants sont tous ceux de A qui n’appartiennent aB : A \ B = {x; x ∈ A et x /∈ B} .


Si A est un sous-ensemble de E , le complementaire de A dans E estle sous-ensemble de E , {A

E dont les elements sont tous ceux qui n’appar-tiennent pas a A .

On note aussi le complementaire de A dans E , quand il n’y a pas deconfusion sur l’ensemble dominant E , par ¬A .

La difference symetrique de deux ensembles A et B est l’ensemble

A∆B =(A⋃

B)\(A⋂

B)

.

Les quantificateursEn mathematiques on utilise des symboles pour designer toute une ex-

pression. Les plus courants sont ceux ci-dessous.

⇐⇒ (si et seulement si)

=⇒ (implique, entraine)

∃ (il existe,) ∃! (il existe un unique)

@ (il n′existe pas)

Exemples d’utilisation: si A est un sous ensemble de E , on a

{{A

E

E = A et A⋃

{AE = E .

Exercice 1.1 . Soit E un ensemble et A, B, C ∈ P(E) .Prouver les proprietes suivantes:i) Commutativite: A ∪ B = B ∪ A et A ∩ B = B ∩ A .ii) Identite: A ∪ ∅ = A et A ∩ E = A .iii) Domination: A ∪ E = E et A ∩ ∅ = ∅ .iv) Idempotence: A ∪ A = A et A ∩ A = A .v) Associativite: A∪(B∪C) = (A∪B)∪C et A∩(B∩C) = (A∩B)∩C .vi) Distributivite: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)et A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) .vii) Lois de De Morgan: {A∪B

E = {AE ∩ {B

E

et {A∩BE = {A

E ∪ {BE .

Si A1, A2, . . . , An sont n sous-ensembles d’un ensemble E , la commu-tativite et l’associativite de l’union et de l’intersection permettent de definirA1∪A2∪ . . .∪An et A1∩A2∩ . . .∩An sans indiquer l’ordre des operations.

On note

n⋃

i=1

Ai = A1 ∪ A2 ∪ . . . ∪ An et

n⋂

i=1

Ai = A1 ∩ A2 ∩ . . . ∩ An .


On a alors, (en notant ”tel que” par t.q. et [[1,n]] = {1,2, . . . ,n}),n⋃

i=1

Ai = {x; ∃ i ∈ [[1,n]] t.q. x ∈ Ai} .

On a aussin⋂

i=1

Ai = {x; ∀ i ∈ [[1,n]], x ∈ Ai} .

Produit cartesienSi E et F sont deux ensembles, leur produit cartesien est l’ensemble

note E × F dont les elements sont formes des couples ordonnes (x, y) ,avec x ∈ E et y ∈ F :

E × F = {(x , y) ; x ∈ E et y ∈ F } .

E × F 6= F × E , sauf quand F = E .Par definition ∅ × E = E × ∅ = ∅ .Plus generalement, si E1, E2, . . . , En sont n ensembles dans cet ordre,

leur produit est l’ensemble

E1 × E2 × . . . × En = { (x1,x2, . . . ,xn) ; xi ∈ Ei , ∀ i } .

Si on change l’ordre, le produit change aussi.Si pour tout i , Ei = E , on note alors

E1 × E2 × . . . × En = En , si ∀ i , Ei = E .

1.2 Logique et techniques de demonstration

1.2.1 Loi de De Morgan et table des verites

En mathematiques, et dans la plupart des autres sciences, on part dufait qu’une affirmation A est soit vraie, soit fausse: on exclut les cas dits”partiellement vrais”.

Si A et B sont 2 affirmations, l’affirmation conjonction C = {A et B}sera notee A ∧ B .

L’affirmation adjonction D = {A ou B} sera note A ∨ B .L’affirmation negation de A , non(A) sera note ¬A .Voici la table des verites ou V signifie ”vrai” et F signifie ”fausse”

Table des veritesA B A∧ B A ∨ BF F F FF V F VV F F VV V V V


Exercice 1.2 . Faire la table des verites

A B (¬A) ∧ B A ∧ (¬B) (¬A) ∨ B A ∨ (¬B)

1.2.2 Techniques de demonstration

Le signe d’implication =⇒ a le sens suivant:

A =⇒ B , s.s.s. {B est toujours vrai quand A l′est} .

Le signe de double implication, ⇐⇒ a le suivant

A ⇐⇒ B , s.s.s. {A =⇒ B et B =⇒ A} .

Un Theoreme ou une Proposition est constitue d’une hypothese et d’uneconclusion, l’hypothese impliquant la conclusion.

Un Lemme est une Proposition servant a prouver un Theoreme, ce quifait que, quand l’hypothese est absente dans le Lemme, il faut comprendrequ’en fait c’est la meme hypothese que celle du Theoreme.

Un Corollaire C d’un Theoreme A est un Theoreme qui est impliquee fa-cilement par le Theoreme A, ce qui fait que, si les hypotheses du Theoreme Asont aussi des hypotheses du Corollaire C, le plus souvent c’est sous-entendu:on ne les repete pas.

Une Tautologie est un Theoreme evident.

Table de tautologiesA ⇒ A A ⇔ A ¬(¬A) ⇔ A

A ⇒ A ∨ B (A ∧ B) ⇒ A ¬A ⇒ ¬(A ∧ B){(A ⇒ B) ∧ (B ⇒ C)} =⇒ {A ⇒ C}{A =⇒ B} ⇐⇒ {¬B =⇒ ¬A}

Une demonstration d’un Theoreme est dite ”par l’absurde” s.s.s. on demontreque si sa conclusion est fausse, alors necessairement son hypothese est aussifausse: la on utilise la tautaulogie

{A =⇒ B} ⇐⇒ {¬B =⇒ ¬A} .

Exemple 1.3 .√

2 n’est pas une fraction rationnelle.

Les techiques de demonstration par recurrence utilisent le theoreme sui-vant.

Theoreme 1.4 . Soit une suite (Pn) d’affirmation, n parcourant N .Si P0 est vraie et si, pour tout k ∈ N , on a

Pk =⇒ Pk+1 ,

Alors tous les Pn sont vraies.


Exemple 1.5 . Pour tout entier n ∈ N , on a la formule du binome

(a + b)n =n∑

k=0

{knan−kbk ,

ou {kn =

(nk

)=

n!

k!(n − k)!.

Des fois les hypotheses du Theoreme 1.4 ne suffisent pas, on l’utilise alorssous cette forme.

Theoreme 1.6 . Soit une suite Pn d’affirmation, n parcourant N .Si P0 est vraie et si, pour tout k ∈ N , on a

{P0, . . . , Pk} =⇒ Pk+1 ,

Alors tous les Pn sont vraies.

1.3 Les applications

Une application f d’un ensemble E , dans (vers) un ensemble F , quel’on note f : E → Fest un ’procede’ qui a chaque element x de E associe un unique element deF note f(x) .On dira que E est l’ensemble de definition, ou l’ensemble de depart,de f et que F est l’ensemble d’arrivee de f .

Autrement dit, une application f : E → Fest entierement determinee par son graphe Gr(f) ,le sous-ensemble de E × F , Gr(f) = {(x,f(x)); x ∈ E} .

Un sous-ensemble G ⊂ E × F est le graphe d’une application

f : E → F s.s.s. ∀ x ∈ E , ∃! y ∈ F t.q. (x,y) ∈ G .

Si y = f(x) , on dit que y est l’image de x par f .x est appele antecedent de y par f .L’image d’une application f : E → F

est le sous-ensemble de F de tous les elements de F ayant un antecedent:

Im(f) = {y ∈ F ; ∃ x ∈ E t.q. y = f(x)}

Si A est un sous-ensemble de E, l’image par f de A est le sous-ensemble deF , f(A) , des images de tous les elements de A :

f(A) = {y ∈ F ; ∃ x ∈ A t.q. y = f(x)}


Si B ⊂ F , le sous-ensemble de E constitue par tous les antecedents,(quand ils existent), des elements de B est appele image reciproque de Bpar f et il est note f−1(B) :

f−1(B) = {x ∈ E t.q. f(x) ∈ B}

On peut avoir f−1(B) = ∅ sans que B soit vide; par contre f(A) n’est videque quand A = ∅ .

Une application f : E → Fest dite injective s.s.s. pour tout couple de deux elements distincts de Eont des images distinctes:

{f : E → F est injective} ⇔ {∀ a , b ∈ E , a 6= b ⇒ f(a) 6= f(b)}

Une application f : E → Fest dite surjective s.s.s. pour tout element de F admet un antecedentpar f , f(E) = F :

{f : E → F est surjective} ⇔ {∀ y ∈ F , ∃ x ∈ E t.q. y = f(x)}

Une application f : E → Fest dite bijective s.s.s. elle est a la fois injective et surjective.

L’application identite sur E sera note idE :

idE : E → E , idE(x) = x (∀ x ∈ E)

Si f : E → F et si g : F → H sont deux applications, l’ensemblede definition de g etant l’ensemble d’arrivee de f , alors on peut composerces deux applications en une application

g ◦ f : E → H , g ◦ f(x) = g[f(x)] , ∀ x ∈ E .

Soient deux applications f : E → F et g : F → E ,on dira que g est inverse a gauche de f s.s.s. g ◦ f = idE .

On dira que g est inverse a droite de f s.s.s. f ◦ g = idF .On dit qu’une application f : E → F

est inversible s.s.s. il existe une application g : F → E ,qui soit a la fois un inverse a droite et a gauche pour f , on note alors cetteapplication g par f−1 qu’on appelle simplement l’inverse de f .

Quand f : E → E est une application de E dans lui-meme, etquand n ∈ N ,

fn = f ◦ f ◦ . . . ◦ f︸︷︷︸n−fois

, si n ≥ 2 , f 1 = f et f 0 = idE .


Proposition 1.7 . Soit f : E → Fune application. On a les proprietes suivantes.

i) f est injective s.s.s. f admet un inverse a gauche.ii) f est surjective s.s.s. f admet un inverse a droite.iii) f est bijective s.s.s. f est inversible.

Exemple 1.8 . Soit m ∈ N , un entier, m ≥ 2 , on considere l’appli-cation multiplication par m sur les entiers relatifs

fm : Z → Z , fm(k) = mk .

fm est injective et non surjective. Son image est notee

mZ = {mk ; k ∈ Z} .

f−1m ({1, m + 1}) = ∅ et fm({1, m + 1}) = {m, m2 + m} .

L’application gm : mZ → Z , gm(x) =x

mest bien definie et elle est bijective.

On a fm ◦ gm = idmZ , mais gm n’est pas un inverse a droite pourfm , fm n’admet pas d’inverse a droite.

On peut definir un prolongement de gm sur tout Z ,

hm : Z → Z , hm(x) =

{gm(x), si x ∈ mZ

0, si x /∈ mZ;

alors hm est un inverse a gauche pour fm : hm ◦ fm = idZ .

Exercice 1.9 . Soient une application f : E → Fet deux sous-ensembles de E , A et B .

i) Prouver que f(A∪B) = f(A)∪f(B) et que f(A∩B) ⊂ f(A)∩f(B)et trouver un exemple ou l’inclusion est stricte.

On considere maintenant deux sous-ensembles de F , C et D .ii) Prouver que f−1(C ∪ D) = f−1(C) ∪ f−1(D)et que f−1(C ∩ D) = f−1(C) ∩ f−1(D) .iii) On suppose maintenant que f est injective.Prouver que f(A ∩ B) = f(A) ∩ f(B) .

Si g est un inverse a gauche de f , montrer que f−1(C) ⊂ g(C)et trouver un exemple ou on a une inclusion stricte.

iv) On suppose que f est surjective, mais pas necessairement injective.Soit h un inverse a droite de f . Prouver que h(C) ⊂ f−1(C) .


Exercice 1.10 . Soient deux applications

f : E → F et g : F → G .

Prouver les implications ci-dessous et dans chaqu’une d’elles donner un exempleou la reciproque est fausse.

i) { f et g injectives } ⇒ { g ◦ f injective }ii) { f et g surjectives } ⇒ { g ◦ f surjective }iii) { f et g bijectives } ⇒ { g ◦ f bijective }

1.4 Denombrement

Un ensemble est dit fini s’il ne contient qu’un nombre fini delements, lenombre total de ses elements est appele cardinal de E et on le note #E ou,s’il n’y a pas confusion avec ”valeur absolue” ou ”module”, par |E| .

Un ensemble E non fini est dit infini, dans ce cas on admet que

# E = +∞ .

Proposition 1.11 . Soient E et F deux ensembles tels que E soit fini.Alors # E ≤ # F s.s.s. il existe une injection f : E → F .

Corollaire 1.12 . Si E et F sont deux ensembles finis, alors #E = #Fs.s.s. il existe une bijection f : E → F .

Proposition 1.13 . Si E est un ensemble fini, alors

#(P(E)) = 2#E .

Theoreme 1.14 . Si E est un ensemble fini et si SE designe l’ensembledes bijections de E vers E , alors on a

# SE = (# E)! .

Proposition 1.15 Definition d’arrangement.Soit E un ensemble de cardinal n .Si k ≥ 1 est un entier, un arrangement de k elements de E est la

donnee (f(1),f(2), . . . ,f(k)) ∈ Ek ,ou f : [[1, k]] → E ,est une application injective: si i 6= j , f(i) 6= f(j) .

Le nombre d’arrangements Akn de k elements dans un ensemble conte-

nant n elements est donne par

Akn =

n!

(n − k)!.

Akn est le nombre d’injections de [[1, k]] dans [[1, n]] .


Pour la preuve, on peut faire une recurrence sur k .

Proposition 1.16 Definition combinaison.Soit E un ensemble de cardinal n .Si k ≥ 0 est un entier, une combinaison de k elements de E , est

l’image d’une injection f : [[1, k]] → E ,c’est a dire un sous-ensemble de E contenant k elements.

Le nombre de combinaisons de k elements d’un ensemble a n elementsest donne par

{kn =

(nk

)=

n!

k!(n − k)!.

Definition 1.17 . Un ensemble E est dit denombrable s.s.s. il existeune injection f : E → N .En particulier tous les ensembles finis sont denombrables et tout sous-ensemblede N est denombrable.

Proposition 1.18 . Soient deux ensembles denombrables E et F .Alors E × F est denombrable.Comme consequence l’ensemble E ∪ F est denombrable.

Idee de la preuve de la Proposition 1.18.Soient deux injections u : E → N et v : F → N .

Alors f : E × F → N × N , f(x,y) = (u(x), v(y))est une injection. Si on prouve que N × N est denombrable, on aura prouveque E × F est denombrable.

On considere sur N2 la relation d’ordre suivante:

(i,j) < (k,`) s.s.s. {i + j < k + ` ou i + j = k + ` et i < k } .

On peut alors ordonner N2 :

N2 = {(0,0), (0,1), (1,0), . . . (an,bn), (an+1,bn+1), . . . . . .} = {(an,bn) n ∈ N} ,

avec (an,bn) < (an+1,bn+1) , ∀ n ∈ N . De la on voit que

f : N2 = {(an,bn) n ∈ N} → N , f((an,bn)) = n

est une injection: N2 est bien denombrable.Pour voir que E ∪ F est denombrable, on remarque que

g : E ∪ F → N × N , g(x) =

{(u(x),0) si x ∈ Eg(x) = (v(x),1) si x ∈ F \ E

est une injection.

Theoreme 1.19 . P(N) et R ne sont pas denombrables.


Idee de la preuve du Theoreme 1.19.+ Prouvons en premier, par l’absurde, que R n’est pas denombrable. Pour

ca, on va utiliser la preuve de Cantor.Si R etait denombrable, il existerait une injection f : [0, 1[ → N.En ordonnant les f(x) , on pourrait ecrire que [0,1[ = {yn ; n ∈ N} .

Or pour tout n , yn =d1(n)

10+

d2(n)

102+ . . . +

dj(n)

10j+ . . .

avec dj(n) ∈ {0,1,2, . . . 9} . Soit alors le reel

t =b1

10+

b2

102+ . . . +

bm

10m+ . . .

avec bm = 0 , si dm(m) 6= 0 , et bm = 1 , si dm(m) = 0 .Il est clair que t ∈ ]0,1[ et qu’il n’existe aucun

entier n tel que yn = t , ce qui nous donne la contradiction: [0,1[ n’estpas denombrable.

+ Pour voir que P(N) n’est pas denombrable, on peut utiliser la surjec-tion

h = P(N) → [0,1] , h(A) =χA(0)

21+

χA(1)

22+. . .+

χA(j − 1)

2j+

χA(j)

2j+1+. . .

ou χA(j) = 1 , si j ∈ A , et χA(j) = 0 autrement.La surjection h admet un inverse a droite g : [0,1] → P(N) ,

qui est une injection, d’ou si P(N) etait denombrable, [0,1] le serait aussi,ce qui est faux car [0,1] ⊂ R et R n’est pas denombrable.

Exercice 1.20 . Soient E et F deux ensembles finis.i) Prouver que #(E × F ) = (#E) × (#F ) .ii) Si E n’est pas vide, prouver que #E < #P(E) .

Exercice 1.21 . Prouver que Q , l’ensemble des nombres rationnels, estdenombrable.

Definition 1.22 . Soit E un ensemble. Une suite d’elements de E est ladonnees d’une application

f : N → E , f(n) = xn , ∀ n ∈ N .

Cette suite est notee (xn)n∈N ou simplement (xn) .Une suite de sous-ensembles de E est une application

F : N → P(E) , F(n) = An , ∀ n ∈ N .


Cette suite est notee (An)n∈N ou simplement (An) .

Son union est definie par

+∞⋃

n=0

An = {x; ∃k ∈ N t.q. x ∈ Ak} .

Son intersection est definie par+∞⋂

n=0

An = {x; ∀k ∈ N, x ∈ Ak} .

Exercice 1.23 . Prouver que si (An) est une suite de sous-ensemble deE , on a

E \(

+∞⋃

n=0

An

)=

+∞⋂

n=0

(E \An) et que E \(

+∞⋂

n=0

An

)=

+∞⋃

n=0

(E \An) .

1.5 Relation binaire sur E, relation d’equivalence

Une relation binaire R sur un ensemble E , est un sous-ensembleR(E) de E × E : R(E) ⊂ E × E .

Si (x,y) ∈ R(E) , on ecrit xRyet on dit que x est en relation R avec y .

La relation R est dite reflexive s.s.s.

xRx ∀ x ∈ E .

La relation R est dite symetrique s.s.s.

xRy =⇒ yRx .

La relation R est dite antisymetrique s.s.s.

{ xRy et yRx } =⇒ x = y .

La relation R est dite transitive s.s.s.

{ xRy et yRz } =⇒ xRz ,

Definition 1.24 . Une relation binaire R sur un ensemble E , estappelee relation d’equivalence s.s.s. R est reflexive, symetrique et tran-sitive :

xRx ∀ x ∈ ExRy =⇒ yRx

xRy et yRz =⇒ xRz


Exemple 1.25 .1). Soient E un ensemble et A ⊂ E , A 6= Ela relation sur E , RA : xRAy s.s.s. (x,y) ∈ A × Aest une relation symetrique et transitive, mais non reflexive.2). La relation sur E , RA : xRAy s.s.s. (x,y) ∈ A × {A

E ou(x,y) ∈ {A

E × Aest une relation symetrique, non reflexive et non transitive.3). La relation sur E , RA

A : xRAAy s.s.s. (x,y) ∈ A × A ou (x,y) ∈

{AE × {A

E

est une relation d’equivalence.

Definition 1.26 . Soit une relation d’equivalence R sur un ensembleE . Pour tout x ∈ E , la classe d’equivalence de x , par rapport a R ,est

[x]R = {y ∈ E t.q. xRy} .

[x]R est un sous-ensemble non vide de E et ∀ y ∈ [x]R , [y]R = [x]R .L’ensemble quotient de la relation d’equivalence R , est l’ensemble

des classes d’equivalence, on le notera E/R :

E/R = {[x]R ; x ∈ E} .

Dans l’Exemple 1.25, le cas de la relation d’equivalence (3), RAA ,

on a juste 2 classes d’equivalences:si a ∈ A et b ∈ {A

E , alors E/RAA = {[a]RA

A, [b]RA

A} .

Proposition 1.27 . Soit R est une relation d’equivalence sur un en-semble E . Alors tout element de E appartient a une et une seule classed’equivalence.

Autrement dit, on a une application surjective

qR : E → E/R , qR(x) = [x]R .

Exemple 1.28 . Soit m ∈ N , m ≥ 2 . Sur Z , on a la relationd’equivalence multiple de m , Mm

jMmk ⇐⇒ k − j = mq avec q ∈ Z .

La classe d’equivalence de j ∈ Z , [j]Mmsera notee [j]m :

[j]m = j + mZ = {j + md ; d ∈ Z} .

L’ensemble des classes d’equivalences Z/Mm sera notee Zm ou Z/mZ .On a #(Zm) = m : Zm = Z/mZ = {[0]m, [1]m, . . . , [m − 1]m} .


Exemple 1.29 . Sur Z? × Z? , on a la relation d’equivalence

(a,b)R(c,d) ⇐⇒ ad = bc .

L’ensemble quotient est Z? × Z?/R = Q? .

Exemple 1.30 . Sur N × N , on une relation d’equivalence

(a,b)R(c,d) ⇐⇒ a + d = b + c .

L’ensemble quotient est identifie a Z , (est en bijection naturelle avec Z ) :N × N/R = Z .

1.6 Ordre partiel, ordre total

Definition 1.31 . Sur un ensemble E , une relation d’ordre , R ,est une relation reflexive, antisymetrique et transitive.

On dit qu’une relation d’ordre R est totale s.s.s.

∀ (a,b) ∈ E × E , on a aRb ou bRa .

Une relation d’ordre qui n’est pas totale est dite partielleOn dit que (E, R) est un ensemble ordonne s.s.s. E est un ensemble

et R une relation d’ordre sur E .

Exemple 1.32 . Si E est un ensemble, sur E = P(E) , la relation ⊂est une relation d’ordre partielle.

Sur R , Z et N on a l’ordre naturel ≤ qui est un ordre total.Sur N , on definit aussi l’ordre ”divise” | :

a | b s.s.s. a divise b ( b = `a , ` ∈ N) .

Cet ordre est partiel: 2 et 3 ne sont pas comparables pour l’ordre | .

Definition 1.33 . Soit (E, ≤E) et (F, ≤F ) deux ensembles ordonnes.Une application f : E → F ,

est dite croissante s.s.s. on a

x ≤E y =⇒ f(x) ≤F f(y) .


Proposition 1.34 . Soient (E, ≤E) et (F, ≤F )deux ensembles ordonnes. Alors la relation sur E × F , ≤ , definie par

(a,b) ≤ (c,d) ⇐⇒ a ≤E c et b ≤F d ,

est une relation d’ordre, appelee ordre produit.La relation sur E × F , ≤= , definie par

(a,b) ≤= (c,d) ⇐⇒ {a ≤E c , a 6= c} ou {a = c et b ≤F d} ,

est une relation d’ordre, appelee ordre lexicographique.

Si (E, ≤E) et (F, ≤F ) sont deux ensembles totalement ordonnes, alorsl’ordre produit sur E × F n’est pas necessairement total.

Proposition 1.35 . Soient (E, ≤E) et (F, ≤F )deux ensembles totalement ordonnes. Alors l’ordre lexicographique sur E×Fest total.

Si (E, ≤) est un ensemble ordonne et si n ∈ N , n ≥ 2 ,l’ordre lexicographique sur En est defini par recurrence et on a:

(x1,x2, . . . ,xn) < (y1,y2, . . . ,yn) ⇔ ∃ i t.q. xi < yi et xj = yj si j < i .

Exercice 1.36 . Soient (E, ≤E) et (F, ≤F ) deux ensembles ordonnes.On munit E × F de l’ordre produit.Prouver que les applications projections

f : E × E → E , f((x,y)) = x , et g : E × F → F , f((x,y)) = y ,

sont croissantes.Que se passe-t-il si l’ordre sur E × F est l’ordre lexicographique?

Definition 1.37 . Soit une application f : E → E .Un point fixe de f est un element x ∈ E tel que f(x) = x .

Theoreme 1.38 . Soit (E, ≤) un ensemble ordonne et fini.Soit f : E → E ,

une application croissante sur E , telle que

{x ∈ E , x ≤ f(x)} 6= ∅ ou {x ∈ E , f(x) ≤ x} 6= ∅ .

Alors f admet un point fixe.

Idee de la preuve. Remarquer qu’il existe une suite de E , (en)n∈N ,qui est soit croissante soit deccroissante et telle que en+1 = f(en) ∀ n .

On conclut en disant que la suite est necessairement finie, (constante apartir d’un certain rang).


1.7 Lois de composition interne

1.7.1 Definition

Si E est un ensemble, une loi de composition interne sur E , estune application

> : E × E → E(a,b) → a>b = >((a,b))

On dit que la loi > est associative s.s.s.

a>(b>a) = (a>b)>c , ∀ a , b et c ∈ E .

On dit que la loi > est commutative s.s.s.

a>b = b>a , ∀ a , b ∈ E .

On dit que la loi > admet un element neutre ζ s.s.s.

a>ζ = ζ>a , ∀ a ∈ E .

Dans ce cas l’element neutre est unique.Si la loi > admet un element neutre ζ , alors un element a ∈ E , admet

un symetrique, (ou un inverse), a′ ∈ E , s.s.s.

a>a′ = a′>a = ζ .

Si ⊥ est une autre loi sur E , on dit ⊥ est distributivepar rapport a la loi > s.s.s.

a⊥(b>c) = (a⊥b)>(a⊥c) et (b>c)⊥a = (b⊥a)>(c⊥a) , ∀ a , b , c ∈ E .

Une loi > sur E est souvent notee additivement par + ou multipli-cativement par × ou ? .

Dans le cas d’une loi sur E notee additivement par + , l’element neutreest note 0 ou 0E , le symetrique a′ de a , quand il existe, est note −a eton ecrit b − a au lieu de b + −a .

Quand en plus la loi + est associative, pour tout entier n ∈ N , n ≥ 2 ,et pour tout a ∈ E , on note

na = a + a + . . . + a (n fois) .

Si n = 1 , 1a = a et si en plus E admet un element neutre, 0a = 0E .Dans le cas d’une loi sur E notee multiplicativement par × ou ? ,

l’element neutre est note 1 ou 1E , le symetrique a′ de a , quand il existe,est note a−1 .


Quand la loi est notee × on ecrit souvent ab a la place de a × b .Quand en plus la loi ? est associative, pour tout entier n ∈ N , n ≥ 2 ,

et pour tout a ∈ E , on note

an = a ? a ? . . . ? a (n fois) .

Si n = 1 , a1 = a et si en plus E admet un element neutre, a0 = 1E .Si ∗ est une loi sur un ensemble fini G = {g1, . . . , gn} ,

la table de la loi est la matrice T , (n + 1) × (n + 1) , definie par

* g1 g2 . . . gn

g1 g1 ∗ g1 g1 ∗ g2 . . . g1 ∗ gn

g2 g2 ∗ g1 g2 ∗ g2 . . . g2 ∗ gn

· · · · · · · · · · · · · · ·gn gn ∗ g1 gn ∗ g2 . . . gn ∗ gn

La matrice de la loi est symetrique s.s.s. la loi est commutative.Exemple: G = P(E) avec la loi ∪ . On prend E = {b,c} , on pose

A = ∅ , B = {b} et C = {c} .

Table de la loi∪ A B C EA A B C EB B B E EC C E C EE E E E E

On voit que ∪ est commutatif et que A est un element neutre.

1.7.2 Monoıde

Definition 1.39 . Un monoıde est un ensemble E , muni d’une loi ⊥associative, on le note par (E, ⊥) .

Exemple d’un monoıde: l’ensemble des mots sur un alphabet aveccomme operation, l’ajout d’un mot.

Definition 1.40 . Un semi-groupe est un monoıde (E, ⊥) tel quetout element soit simplifiable:

i) ∀ a , b , c ∈ E , a⊥(b⊥c) = (a⊥b)⊥cii) ∀ a ∈ E , a est simplifiable a droite: b⊥a = c⊥a ⇒ b = ciii) ∀ a ∈ E , a est simplifiable a gauche: a⊥b = a⊥c ⇒ b = ca ∈ E est dit simplifiable s.s.s. il est simplifiable a droite et a gauche.


Exemples: (N , +) et (N? , ×) sont des semi-groupes,par contre (N , ×) est un monoıde qui n’est pas un semi-groupe: 0 n’estpas simplifiable.

Proposition 1.41 . Tout semi-groupe fini admet un element neutre.

Idee de la preuve Si (E; ∗) est un semi-groupe a n elements et si onconsidere sa table de multiplication A.

C’est une matrice n × n a coefficients dans E . Comme (E; ∗) est unsemi-groupe, chaque ligne de A contient n elements distincts, donc contientchaque element de E , on en deduit que

∀ a ∈ E , ∃ da ∈ E t.q. a ∗ da = a .

Soit a ∈ E , pour tout b ∈ E , en simplifiant a gauche par a , on trouveque a ∗ b = a ∗ da ∗ b ⇒ b = da ∗ b :da est un element neutre a gauche.

En utilisant que chaque colonne de A contient aussi tous les elements deE , on trouve qu’il existe un element neutre a droite ga :

ga ∗ b = b , ∀ b ∈ E .

Comme ga ∗ da = da = ga = 1E : c’est un element neutre.

1.8 Algebre de Boole et exemples

Definition 1.42 . Une algebre de Boole est la donnee de

(E, u , t , ¬, ♦, �) ,

ou E est un ensemble, ♦ et � sont deux elements de E , u et t sontdeux lois sur E qui sont associatives, commutatives et distributives l’unepar rapport a l’autre et tel que

x u x = x = x t x , ∀x ∈ E ,

¬ : E → E est une application bijective telle que

¬ ◦ ¬ = idE : ¬(¬(x)) = x , ∀ x ∈ E .

Les deux elements de E , ♦ et � et l’application ¬ doivent satisfaire,∀ x ∈ E ,

x u ♦ = ♦ x t ♦ = xx u � = x x t � = �

x u ¬(x) = ♦ x t ¬(x) = �


Exemple 1.43 L’algebre de Boole minimale. Elle contient seule-ment deux elements notes: E = {0, 1} .

L’une des lois est notee × et l’autre + . On la notera B .x y x × y x + y ¬(x)0 0 0 0 10 1 0 1 11 0 0 1 01 1 1 1 0

Attention de ne pas confondre la loi × de B avec celle qui sera definieplus tard sur Z2 qui n’a aussi que 2 elements.

Exercice 1.44 . Si F est un ensemble, prouver que(P(F ), ∩ , ∪ , {F , ∅, F ) est une algebre de Boole.

2 Arithmetique dans Z

2.1 Representation des entiers

L’ordre naturel sur N fait de N est semi-groupe ordonne:

j ≤ j + k et j ≤ ` ⇒ j + n ≤ ` + n , ∀ j , k , ` , n ∈ N .

Si 1 ≤ n , alors ∀ k ∈ N , ∃ j ∈ N t.q. k ≤ jn .

Proposition 2.1 Base pour les entiers.Soit b ∈ N , b ≥ 2 que nous appelerons base. Les b entiers

Db = {0, 1, . . . , b − 1} sont appeles les digits de la base b .Alors tout n ∈ N s’ecrit de maniere unique

n = d0 + d1b + d2b2 + . . . + dkb

k , avec dj ∈ Db , ∀ j .

Exercice 2.2 . 1) Soient A et B deux ensembles non vides et finis.On note F(A; B) l’ensemble des applications f : A → B .

Prouver de deux facons differentes que #F(A; B) = (#B)#A .2) Un ordinateur code les entiers positifs simples sur 32 bits et les entiers

positifs doubles en 64 bits.Quel est le plus grand entier simple? Et celui double?

Theoreme 2.3 . Pour toute base b ∈ N , b ≥ 2 , pour tout reela ∈ ]0, 1[ et pour tout entier m ∈ N? , il existe m digits uniquesd1, . . . , dm ∈ Db tel que

d1

b+

d2

b2+ . . . +

dm

bm≤ a ≤ d1

b+

d2

b2+ . . . +

dm + 1

bm.


2.2 Division euclidienne dans N et nombres premiers

On rappelle que, si a , b ∈ N et si a 6= 0 , on dit que a divise b , eton ecrit

a | b s.s.s. ∃ c ∈ N t.q. b = ac ,

on pose alors c =b

a.

On dit que a est un diviseur de b . On dit aussi que b est un multiplede a . Rappellons les proprietes suivantes:

{a|b et a|c} =⇒ a|(b + c)

∀ a , b ∈ N , a 6= 0 , ∃! (q,r) ∈ N2 , t.q. r < a et b = aq + r

r est appele le reste de la division de b par a et q est le quotient dela division de b par a .

Si b n’est pas divisible par a , on ecrit a - b .Un nombre q ∈ N, q ≥ 2 est dit premier s’il n’est divisible que par

lui-meme et 1 .

Theoreme 2.4 d’Euclide.L’ensemble P des nombres premiers est infini.

Theoreme 2.5 de Factorisation des entiers.Soit n ∈ N , n ≥ 2 . Alors

∃! r ∈ N? , ∃! (p1, . . . ,pr) ∈ Pr , p1 ≤ p2 ≤ . . . ≤ pr tel que n = p1p2 . . . pr .

Autrement dit, n admet une factorisation unique n = qr1

1 qr2

2 . . . qrk

k , oules ri ≥ 0 et les qi sont tous les nombres premiers distincts deux a deux:qi < qi+1 ≤ n .

Proposition 2.6 . Soient a et b deux entiers et p un nombre premier.Alors on a

p|(ab) =⇒ {p|a ou p|b}

Theoreme 2.7 Test d’Euclide.Soit p ∈ N , p > 2 . Alors p est premier s.s.s.

∀ k ∈ P , k2 ≤ p =⇒ k - p .


2.3 PGCD et PPCM dans N .

Definition 2.8 . Soient a et b sont deux entiers ≥ 0 .• Le plus grand commun diviseur a a et b est appele PGCD de a

et b et on le notera a ∧ b .• Le plus petit commun multiple a a et b est appele PPCM de a et

b , et on le notera a ∨ b .• On dit que a et b sont premiers entre eux s.s.s. a ∧ b = 1 ,

c’est a dire s.s.s. le seul diviseur commun a a et b est 1 .

Proposition 2.9 . Soient a et b deux entiers > 0 . Sia = ps1

1 . . . psmm , et b = pt1

1 . . . ptmm ,

avec pi ∈ P , si et ti ∈ N , ∀ i ,alors le PGCD et le PPCM de a et b sont donnes par

a ∧ b = pr1

1 . . . prmm avec ri = min{si,ti}

a ∨ b = pr1

1 . . . prmm avec ri = max{si,ti} .

Et on a toujours ab = (a ∧ b)(a ∨ b) .

Remarque 2.10 . Sur N? , on a les proprietes suivantes:

c | a et c | b =⇒ c | a ∧ b .

a | ` et b | ` =⇒ a ∨ b | ` .

Theoreme 2.11 Algorithme d’Euclide pour le PGCD.Soient deux entiers a et b , 2 ≤ a ≤ b .

On definit une suite finie d’entiers ≥ 0 , (ri)0≤i≤M ,(M est inconnu et on doit avoir rM = 0 et ri 6= 0 si i < M) , par

r0 = b , r1 = a et par la relation de recurrence basee sur la divisioneuclidienne

ri−1 = qiri + ri+1 ,(

(qi,ri+1) ∈ N2 , ri+1 < ri

).

Alors le PGCD de a et b est donne par le dernier ri non nul:

a ∧ b = rM−1 .

Pour la preuve on utilise le lemme suivant.

Lemme 2.12 . Si a , b ∈ N? et si b = aq + ravec q , r ∈ N? , r < a . Alors PGCD(b,a) = PGCD(a,r) .

Exemple a = 1122 et b = 1547Liste des rj pour j ≥ 2 .

425 272 153 119 34 17 01122 ∧ 1547 = 17


2.4 Groupe et sous-groupe: une introduction

Definition 2.13 . Un groupe est un semi-groupe (G, ∗) ayant un elementneutre et tel que tout element ait un symetrique, ce qui est equivalent aux 3proprietes ci-dessous:

i) ∀ a , b , c ∈ G , a ∗ (b ∗ c) = (a ∗ b) ∗ cii) ∃ ρ ∈ G t.q. a ∗ ρ = ρ ∗ a = a , ∀ a ∈ Giii) ∀ a ∈ G , ∃ a′ t.q. a ∗ a′ = a′ ∗ a = ρ

Exemples de groupe: (Z, +) , (Q?, ×), (mZ, +) , (SE, ◦) ,(m ∈ Z et E est un ensemble). Quand E = [[1, n]] , SE sera note

Sn , on l’appelle groupe symetrique, ou groupe des permutations.Si n ∈ N , n ≥ 2 , l’ensemble des racines complexes nieme de l’unite

Fn est un groupe pour la loi × .Le cercle unite T = {z ∈ C , |z| = 1 } est un groupe pour la loi × .Un groupe commutatif est dit abelien.

Definition 2.14 . Soit (G, ∗) un groupe. Si H ⊂ G , H 6= ∅est tel que (H, ∗) soit un groupe, on dit que H est un sous-groupe de G .

Si m ∈ N , mZ est un sous-groupe de Z .T est un sous-groupe de (C? ; ×) .

Fn est un sous-groupe de T , c’est donc aussi un sous-groupe de(C? ; ×) .

Proposition 2.15 . Premiere caraterisation d’un sous-groupe.Soit (G, ∗) un groupe d’element neutre 1G .Alors H ⊂ G est un sous-groupe de G s.s.s. on ai) 1G ∈ Hii) ∀ h ∈ H , le symetrique de h , h′ ∈ Hiii) ∀ a , b ∈ H , a ∗ b ∈ H

Proposition 2.16 . Deuxieme caraterisation d’un sous-groupe.Soit (G, ∗) un groupe d’element neutre 1G .Alors H ⊂ G est un sous-groupe de G s.s.s. on ai) 1G ∈ Hii) ∀ a , b ∈ H , a ∗ b′ ∈ H , si b′ est le symetrique de b

Theoreme 2.17 . Les seuls sous-groupes de (Z ; +) sont les

mZ , avec m ∈ N .


Proposition 2.18 Definition du centre.Soit (G ; ∗) un groupe. Son centre

Z(G) = { c ∈ G t.q. c ∗ g = g ∗ c , ∀ g ∈ G }est un sous-groupe commutatif de (G ; ∗) .

Pour S3 , le centre est reduit a l’element neutre.

Definition 2.19 . Si (G, ∗) est un groupe et si A ⊂ G le plus petitsous-groupe contenant A est appele sous-groupe engendre par A.

Pour Sn , (n ≥ 2) , le sous-groupe engendre par une transpositionτij , (i 6= j) , τij(i) = j , τij(j) = i et autrement τij(k) = k ,comprend 2 elements seulement, τij et l’element neutre.

Proposition 2.20 . Soient (G,+) un groupe et g ∈ G .Alors le sous-groupe engendre par g est

Gg = {ng , − ng , n ∈ N} = {kg , k ∈ Z} .

Il est commutatif.Le cardinal de Gg est appele l’ordre de g:

ordre ( g ) = # Gg .

On rappelle que 0g = 0G , 1g = g , − 1g = −g et si n ∈ N , n ≥ 2 ,

ng = g + g . . . g︸︷︷︸n−fois

et − ng = n(−g) .

Si la loi du groupe est notee multiplicativement, alors le sous-groupe de(G, ×) engendre par un element g , est

Gg = {gk , k ∈ Z} .

Proposition 2.21 . Soient (G ×) un groupe et soit g ∈ G . Alorson a

i) ordre(g−1) = ordre(g) .ii) n = ordre(g) quand il est fini est carcterise par

gj 6= 1G , ∀ j , 0 < j < n , et gn = 1G .

Definition 2.22 . Un groupe (G, +) de la forme G = Gg , avec ung ∈ G , est dit homogene.

Si (G, ∗) est un groupe fini de cardinal n ,on dit que G est un groupe d’ordre n.

Un groupe homogene et d’ordre n est dit groupe cyclique d’ordre n.


S2 est cyclique et d’ordre 2 .

Theoreme 2.23 de Lagrange. Dans un groupe fini, l’ordre d’un elementdivise toujours l’ordre du groupe.

Exercice 2.24 . Verifier que S3 a un seul sous-groupe d’ordre 3 etdeterminer tous ceux d’ordre 2 .

Proposition 2.25 . Soit (G ; ∗) un groupe abelien. Soient a , b ∈ Gd’ordres finis. Alors on a

ordre(a ∗ b) | PPCM [ordre(a) , ordre(b)] .

Idee de la preuve. Notons i = ordre(a), j = ordre(b) et m = i ∨ j .(a ∗ b)m = (ai)m/i ∗ (bj)m/j .

Definition 2.26 . Un morphisme, on dit aussi un homomorphisme,du groupe (G, >) dans le groupe (K, ⊥) est une application f : G → K ,satisfaisant

f(x>y) = f(x)⊥f(y) , ∀ x , y ∈ G .

Pour un tel morphisme f , Ker(f) = {x ∈ G t.q. f(x) = 0K} estappele noyau de f. Im(f) = f(G) est l’image de f .

Quand K = G , un morphisme de f : G → G ,de G dans lui-meme est appele un endomorphisme.

Un morphisme de groupe qui est bijectif est appele un isomorphisme degroupe.

Proposition 2.27 . Si f : G → K est un morphisme du groupe(G, ×) dans le groupe (K, ?) . Alors on a

• Ker(f) est un sous-groupe de G :

1G ∈ Ker(f) , et x , y ∈ Ker(f) ⇒ xy−1 ∈ Ker(f) .

• Ker(f) est un sous-groupe distingue, c’est a dire que

∀ a ∈ G , a [Ker(f)] a−1 = Ker(f) .

• Im(f) est un sous-groupe de K .• f est injectif s.s.s. Ker(f) = {1G} .

Exercice 2.28 .i) Soient (G, >) et (H, ⊥) deux groupes. Prouver que leur produit

G × H est un groupe pour la loi on : (x,y) on (a,b) = (x>a,y⊥b) .ii) Prouver que, pour tout n ≥ 2 , Gn est un groupe pour la loi que l’on

note aussi > et qui est definie par

(x1, . . . ,xn) > (y1, . . . ,yn) = (x1>y1, . . . ,xn>yn) .


Exercice 2.29 . Soit (G, +) un groupe abelien et soient H et Kdeux sous-groupes de G .

i) Prouver que H + K = {x ∈ G , ∃ (a,b) ∈ H × K t.q. x = a + b}est un sous-groupe de G .

ii) Justifier que H +K = K +H , que H est un sous-groupe de H +Ket que H + (H + K) = H + K .

iii) Prouver que H ∩ K est aussi un sous-groupe et trouver un exempleou H ∪ K n’est pas un sous-groupe.

2.5 Relation de Bezout dans Z

Theoreme 2.30 Division dans Z .Pour tout (a,b) ∈ Z? × Z , il existe un unique couple (q,r) ∈ Z × N

tel queb = aq + r avec 0 ≤ r < |a| .

r est appele le reste de la division de b par a , et q le quotient de ladivision de b par a .

On dira que a divise b s.s.s. b = aq avec q ∈ Zet on ecrira a | b .

Definition 2.31 PGCD et PPCM dans Z .Soient a1 , a2 , . . . , an ∈ Z .• Le plus grand commun diviseur a ces n entiers relatifs est leur PGCD

defini par:

d = PGCD(a1, a2, . . . , an) ∈ N? , d | aj ∀ j ,

∀ c ∈ N? , c|aj ∀ j =⇒ c | d .

• Le plus petit commun multiple a ces n entiers relatifs est leur PPCMdefini par:

m = PPCM(a1, a2, . . . , an) ∈ N? , aj | m ∀ j ,

∀ c ∈ N? , aj | c ∀ j , =⇒ m | c .

• Quand PGCD(a1,a2, . . . ,an) = 1 , on dit que les a1, a2, . . . , an

sont premiers entre eux.

On rappelle que, si H est sous-groupe de (Z , +) ,s.s.s. il existe m ∈ Z tel que H = mZ .

Proposition 2.32 . Soient (m,n) ∈ Z? × Z? . Alors on a

i) mZ + nZ = (m ∧ n)Z et ii) mZ⋂

nZ = (m ∨ n)Z .


Corollaire 2.33 . Si (m,n) ∈ Z? × Z? , alors on a

∃ (i,j) ∈ Z2 tel que m ∧ n = im + jn .

Theoreme 2.34 Relation de Bezout.Si m et n sont deux entiers 6= 0 .Alors m et n sont premiers entre eux s.s.s. on a

∃ (i,j) ∈ Z2 t.q. im + jn = 1 .

Exercice 2.35 . Soient d , m , n ∈ N? . Prouver qued = m ∧ n s.s.s.

d | n , d | m et ∃ u , v ∈ Z t.q. d = um + vn .

Remarque 2.36 . Dans le Theoreme precedent 2.34 et dans le Corol-laire 2.33 qui le precede, le couple d’entier (i,j) est appele couple deBezout associe a (i,j) .

L’algorithme d’Euclide, (le Theoreme 2.11), permet de retrouver le couplede Bizout.Exemples i) m = 153, n = 119, m = n + 34, n = 3 × 34 + 17,34 = 2 × 17 ⇒ 153 ∧ 119 = 17et 34 = m − n , 17 = n − 3 × 34 = n − 3(m − n) = −3m + 4n :le couple de Bizout associe a (153,119) est (−3, 4) .

ii) m = 119, n = 33, m = 3n + 20, n = 20 + 13, 20 = 13 + 7,13 = 7 + 6, 7 = 6 + 1, 6 = 6 × 1 ⇒ 119 ∧ 33 = 1 ,et 20 = m − 3n , 13 = n − (m − 3n) = 4n − m ,7 = (m−3n)−(4n−m) = 2m−7n , 6 = (4n−m)−(2m−7n) = −3m+11n ,1 = (2m − 7n) − (−3m + 11n) = 5m − 18n :le couple de Bezout associe a (119,33) est (5, − 18) .

Theoreme 2.37 de Gauss.Si a , b et c sont trois entiers 6= 0 , alors on a

{ a | (bc) et a ∧ b = 1 } =⇒ a | c .

Proposition 2.38 . Soient a , m , n ∈ N? , a ≥ 2 . Alors on a

(am − 1) | (an − 1) ⇐⇒ m | n .

Idee de la preuve. ⇐ Si n = mq , alorsan − 1 = (am)q − 1 = (am − 1)[(am)q−1 + (am)q−2 + . . . + am + 1] .⇒ Si (am −1) | (an −1) , alors m ≤ n et donc n = mq + r, 0 ≤ r < m .

On ecrit alors que an − 1 = amqar − 1 = (amq − 1)ar + ar − 1 .


La premiere etape montre que (am − 1) | (amq − 1)ar ,cette nouvelle information et l’hypothese de depart implique que

(am − 1) | (ar − 1) : si r 6= 0 , alors m ≤ r ce qui est en contradictionavec r < m .

Theoreme 2.39 . Soient a , m , n ∈ N? , a ≥ 2 . Alors on a

d = m ∧ n ⇐⇒ ad − 1 = (am − 1) ∧ (an − 1) .

Idee de la preuve. ⇒ D’apres la proposition precedente ad −1 diviseam − 1 et an − 1 .Si on trouve un couple de Bizout, on aura termine la preuve.

Or on sait qu’il existe un couple de Bizout pour (m,n) , on peut supposerpar exemple qu’il existe u , v ∈ N? t.q. d = um − vn .La proposition precedente donne que

aum − 1 = (am − 1)q et que avn − 1 = (an − 1)s .En ecrivant que um = d + vn , on trouve que

aum − 1 = adavn − 1 = ad(avn − 1) + ad − 1 ce qui donne que

ad − 1 = (aum − 1) − ad(avn − 1) = q(am − 1) − ads(an − 1) :

le couple de Bizout cherche est (q, − ads) .⇐ La premiere partie montre que am∧n − 1 = ad − 1 d’ou d = m ∧ n .

Theoreme 2.40 . Soit n ∈ N , n ≥ 2 , et soit (a1,a2, . . . ,an) ∈ Zn .Alors on a les deux proprietes suivantes:i) a1Z ∩ a2Z ∩ . . . ∩ anZ = PPCM(a1,a2, . . . ,an) Z .ii) a1Z + a2Z + . . . + anZ = PGCD(a1,a2, . . . ,an) Z .

Exercice 2.41 . Prouver les proprietes suivantes dans Z .i) PPCM(a,b,c) = PPCM [PPCM(a,b),c]et PPCM(ka,kb) = |k|PPCM(a,b) .ii) PGCD(a,b,c) = PGCD[PGCD(a,b),c]et PGCD(ka,kb) = |k|PGCD(a,b) .

Theoreme 2.42 Relation de Bezout: cas multiples.Soit n ∈ N , n ≥ 2 , et soit (a1,a2, . . . ,an) ∈ Zn .Alors a1, a2, . . . , an sont premiers entre eux s.s.s.

∃ (u1,u2, . . . ,un) ∈ Zn t.q. u1a1 + u2a2 + . . . + unan = 1 .


2.6 Une petite application a l’ordre d’un groupe

Proposition 2.43 . Soient (G ; ∗) un groupe abelien et a , b ∈ Gd’ordres finis. Alors on a

ordre(a) ∧ ordre(b) = 1 ⇒ ordre(a ∗ b) = ordre(a) × ordre(b) .

Idee de la preuve. Notons i = ordre(a), j = ordre(b) , k = ordre(a∗b) .On deja vu que k | ij , on va montrer par l’absurde que k ne divise pas i .

On ulitilise la relation de Bezout ui + vj = 1 qui donne que

(a ∗ b)ui = bui = b1−vj = b ∗ b−vj = b .

Alors, si k|i on aurait alors (a ∗ b)ui = a ∗ b = bqui donnerait, en simplifiant par b , que a = 1G

et donc i serait l’ordre de G ; dans ce cas j diviserait i : contradiction.

Corollaire 2.44 . Pour un groupe abelien fini, il existe toujours un elementdont l’ordre est divisible par l’ordre de tout autre element.

Idee de la preuve. Notons le groupe multiplicativement: (G, ∗) .Comme il est fini, il existe un element a ∈ G dont l’ordre est maximal.

Soit b ∈ G , b 6= a . Notonsn = ordre(a) et k = ordre(b) , (1 ≤ k ≤ n) .Si k ne divise pas n , alors il existe un nombre premier p tel que

n = pin′ , k = pjk′ , 0 ≤ i < j , p ∧ n′ = 1 , p ∧ k′ = 1 .

On considere c = api

et d = bk′

, alors ordre(c) = n′ et ordre(d) = pj .Comme n′ ∧ pj = 1 , la proposition precedente dit que

ordr(cd) = n′pj > pin′ = n , ce qui est en contradiction avec n lemaximum des ordres.

2.7 Congruence dans Z

Definition 2.45 . Soit m ∈ N , m ≥ 2 .Deux entiers relatifs j et k sont dits congrus modulo m s.s.s.

m | (j − k) , et on ecrira

j ≡ k (mod m) .

C’est une relation d’equivalence sur Z :

j ≡ j (mod m) , j ≡ k (mod m) =⇒ k ≡ j (mod m)


j ≡ k (mod m) et k ≡ ` (mod m) =⇒ j ≡ ` (mod m) .

La classe d’equivalence de j , (modulo m ) sera note [j]m :

k ∈ [j]m s.s.s. m | (j − k) .

L’ensemble des classes d’equivalence modulo m sera notee Zm .

Proposition 2.46 . Pour tout entier m ∈ N , m ≥ 2 , on a

Zm = { [0]m, [1]m, . . . , [m − 1]m } .

Exercice 2.47 . Soit m ∈ N , m ≥ 2 . Prouver que

∀ j ∈ Z , Zm = { [j]m , [j + 1]m , . . . , [j + m − 1]m } .

Theoreme 2.48 . Pour tout entier m ∈ N , m ≥ 2 , on a (Zm ; +)qui est un groupe abelien pour la loi

[j]m + [k]m = [j + k]m .

L’element neutre est [0]m .On a toujours ∀ [q]m ∈ Zm , m[q]m = [0]m .

Proposition 2.49 . Soit un entier m ∈ N , m ≥ 2 , et soit q ∈ Z .Alors Zm = { [kq]m k ∈ Z } = {k[q]m ; k ∈ Z}s.s.s. q est premier avec m .

Pour la preuve on utilise la relation de Bezout.

Theoreme 2.50 des restes chinois.Soient m , n ∈ N? premiers entre eux.Alors les deux groupes (Zmn , +) et (Zm × Zn , +)

sont isomorphes, par l’isomorphisme

F : Zmn → Zm × Zn , F ([j]mn) = ([j]m , [j]n) .

Idee de la preuve. On verifie que F ([j]mn) ne depend pas du choix del’element j dans la classe modulo mn .

On voit alors que F est un morphisme de groupes.Comme les deux groupes sont finis et ont le meme ordre,

F sera un isomorphisme s.s.s. Ker(F ) = { [0]mn } .Or [j]mn ∈ Ker(F ) s.s.s. j = km = `n , avec k et `

des entiers. Comme m et n sont premiers entre eux, km = `n impliqueque n divise k , ce qui donne que j est divisible par mn : [j]mn = [0]mn .


2.8 Groupe quotient

Definition 2.51 . Soit (G, ×) un groupe et H un sous-groupe de G .Alors les relations

• RH,d et RH,g sont deux relations d’equivalences sur G :

x RH,d y ⇐⇒ xy−1 ∈ H et x RH,g y ⇐⇒ y−1x ∈ H .

• On dit que H est un sous-groupe distingue de G , s.s.s.

∀ a ∈ G , aH = Ha .

(Pour un groupe abelien tous les sous-groupes sont distingues).• Pour un sous-groupe distingue H , les relations d’equivalences RH,d

et RH,g sont identiques, on les note RH :

x RH y ⇐⇒ xy−1 ∈ H .

• Si H est un sous-groupe distingue de (G, ×) , l’ensemble des classesd’equivalences G/RH est note G/H :

G/H = { L ∈ P(G) t.q. ∃ a ∈ G t.q. L = aH } = { aH ; a ∈ G } .

La classe d’equivalence d’un element a ∈ G , sera note [a]H :

[a]H = aH = Ha .

Theoreme 2.52 . Soit H un sous-groupe distingue d’un groupe (G, +) .Alors (G/H, +) est un groupe pour la loi

[x]H + [y]H = [x + y]H : 0G/H = [0]H , et − [a]H = [−a]H .

Proposition 2.53 . Pour tout m ∈ N , m ≥ 2 , on a

Zm = Z/mZ ,

(dans le sens ou les deux groupes sont isomorphes).

Theoreme 2.54 . Soit (G, +) un groupe et H un sous-groupe dis-tingue de G . Alors l’application

pH : G → G/H , pH(x) = [x]H ,

est un morphisme de groupe.pH est sujectif et Ker(pH) = H .pH est appele surjection canonique de G sur G/H .


Theoreme 2.55 . Soit f : G → Mun morphisme de groupe. Alors il se factorise de maniere unique en

p [f ] iG : −→ G/Ker(f) : −→ Im(f) : −→ M

f = i ◦ [f ] ◦ p ,

ou p est la surjection canonique de G sur G/Ker(f) ,

[f ] : G/Ker(f) → Im(f) est un isomorphisme

et i : Im(f) → M est l’injection canonique:

i(y) = y , [f ]([x]) = f(x) .

2.9 Definitions d’anneau, anneau commutatif et integre

Definition 2.56 . Un anneau A est un groupe commutatif, de loi noteeadditivement + , et qui est muni d’une deuxieme loi notee multiplicativement× , qui est associative et distributive par rapport a l’addition:

x(yz) = (xy)z , x(y + z) = xy + xz et (y + z)x = yx + zx .

On notera l’anneau (A; +, ×) .On dit que l’anneau (A; +, ×) est unitaire s.s.s.

∃ 1 ∈ A t.q. 1x = x1 = x , ∀ x ∈ A .

On dit que l’anneau (A; +, ×) est commutatif s.s.s. la loi × estaussi commutative.

Un sous-anneau d’un anneau (A; +, ×) est un sous-groupe B dugroupe (A; +) t.q. (B; +, ×) soit un anneau.

Exemple 2.57 .• Z , Q , R , C sont des anneaux commutatifs et unitaires.• Mn(R) l’ensemble des matrices reelles carrees d’ordre n ≥ 2 est un

anneau non commutatif et unitaire.• Mn(Z) l’ensemble des matrices carrees d’ordre n ≥ 2 est un anneau

non commutatif et unitaire.• Si (G, +) est un groupe commutatif, alors End(G) , l’ensemble des

endomorphismes de G , c’est a dire l’ensemble des morphismes de groupede G dans G , est un anneau unitaire.


Proposition 2.58 . Dans un anneau (A, + , ×) ,on a les proprietes suivantes:

i) 0Ax = x0A = 0A ∀ x ∈ A .ii) ∀ x , y ∈ A , (−x)y = x(−y) = −xy .iii) ∀ x , y ∈ A , ∀ n ∈ Z , (nx)y = x(ny) = n(xy) .iv) ∀ x ∈ A , ∀ n , m ∈ Z ,

mx + nx = (m + n)x , (nm)x = n(mx) = m(nx) .

v) ∀ x ∈ A , ∀ n , m ∈ N? ,

xm+n = xmxn = xnxm et (xm)n = xmn .

Dans ce cours nous considererons seulement des anneaux commutatifs etunitaire, contenant au moins deux elements:

(A, + , ×) est un anneau commutatif et unitaires.s.s. ∃ 0A , 1A ∈ A , 1A 6= 0A , t.q. ∀ x, y, z ∈ A ,

x + y = y + x x + 0A = x x + (y + z) = (x + y) + z ∃ − x t.q. x + (−x) = 0A

xy = yx x(yz) = (xy)z x(y + z) = xy + xz 1Ax = x

Proposition 2.59 Formule du binome.Dans un anneau commutatif et unitaire A , on a

(x + y)n =

n∑

j=0

{jnxjyn−j , ∀ n ∈ N? , ∀ x , y ∈ A ;

avec la convention que x0 = 1A .

Exercice 2.60 Anneau booleen des parties de E.Soit E un ensemble et soit E = P(E) , l’ensemble des parties de E .Montrer que (E , ∆, ∩) est un anneau commutatif et unitaire, si

A∆B = (A \ B) ∪ (B \ A) .

L’anneau (P(E), ∆, ∩) est appeleanneau booleen des parties de E.

Definition 2.61 . Soit (A, +, ×) est un anneau commutatif et unitaireet soit x ∈ A un element.

• On dit que x est inversible s.s.s.

∃ y ∈ A t.q. xy = yx = 1 .

Un tel y est unique, il est appele inverse de x et il est note x−1 .


• On dit que x est un diviseur de zero s.s.s.

∃ y ∈ A? = A \ {0A} t.q. xy = 0A .

L’anneau A , (non reduit a {0A} ) , qui est sans diviseur de zero autreque 0A est appele anneau integre.

• S’il existe n ∈ N? t.q.

n1A = 0A et ∀ k ∈ N k < n =⇒ k1A 6= 0A ,

on dit que l’anneau A est de caracteristique n.Quand ∀ n ∈ N? , n1a 6= 0A ,on dit que l’anneau A est de caracteristique nulle.Nous verons dans la suite, une definition plus algebrique de cette notion

de caracteristique.

Z est un anneau commutatif, unitaire et integre.Pour tout m ∈ N , m ≥ 2 , mZ , est un anneau commutatif et integre

mais non unitaire.

Exercice 2.62 . Soient (A; +, ×) un anneau commutatif et unitaireet a , b ∈ A inversibles.

i) Prouver que a 6= 0A et puis que (ab)−1 = b−1a−1 .ii) Si A est de caracteristique n ≥ 1 , prouver que

∀ a ∈ A , na = 0A .

Proposition 2.63 . Soit (A, + , ×) un anneau commutatif et unitaire.L’ensemble UA de ses elements inversibles est un groupe pour la loi

multiplicative ×.

Definition 2.64 . Soient deux anneaux A et B . Alors le groupe A×Best un anneau pour la loi produit suivante:

(a,b) × (x,y) = (ax,by) , ∀ (a,b) , (x,y) ∈ A × B .

Si A1 , . . . , An sont n anneaux,alors A1 × . . . An est aussi un anneau.

Si A et B sont unitaires, alors A × B l’est aussi: 1A×B = (1A,1B) .Si A et B sont commutatifs, alors A × B l’est aussi.

Definition 2.65 . Un corps est un anneau (A; +, ×) ,(commutatif et unitaire), tel que

0 6= 1 et (A?, ×) soit un groupe.


Si (K; +, ×) est un corps, un sous-corps de K est un sous-anneauH de K tel que (H; +, ×) soit un corps.

On dit alors que le corps K est une extension du corps H .

Attention: si K est un corps, K2 est un aneau, mais pas un corps(1,0) (0,1) ne sont pas inversibles.

Definition 2.66 . Soit (A, + , ×) un anneau commutatif, unitaire etintegre (sans diviseur de zero).

L’ensemble des fractions sur A , QA , est le quotient de A × A?

par la relation d’equivalence R ,

(a,b) R (c,d) s.s.s. ad = bc .

Si (a,b) ∈ A × A? , sa classe d’equivalence est noteea

b.

On identifie A a un sous-ensemble de QA par a =a

1.

Dans ce cas, si b ∈ A? admet un inverse b′ , alorsa

b= ab′ , ∀ a ∈ A .

Proposition 2.67 . Soit (A, + , ×) un anneau commutatif, unitaireet integre.

Alors l’ensemble des fractions QA des fractions sur A est un corpspour les lois definies ci-dessous:

a

b+

c

d=

ad + bc

bdet

a

b× c

d=

ac

bd.

De plus A est un sous-anneau de QA .

2.10 L’anneau Zm

Theoreme 2.68 . Soit m ∈ N , m ≥ 2 .Alors le groupe abelien (Zm ; +, ×) est un anneau unitaire et commutatif

pour la loi produit suivante:

[j]m × [k]m = [jk]m .

L’element unite est [1]m .

Proposition 2.69 . Soit m ∈ N , m ≥ 2 .Alors l’anneau (Zm ; +, ×) est de caracteristique m :

m[1]m = [0]m et j[1]m 6= [0]m si 1 ≤ j < m .


Theoreme 2.70 . Soit m ∈ N , m ≥ 2 .Alors l’anneau (Zm ; +, ×) est un corps s.s.s. m est un nombre

premier.

Corollaire 2.71 . Soit p un nombre premier. Alors on a

(j + k)p ≡ jp + kp (mod p) .

Preuve: on utilise la formule du binome et le fait que p | {ip si 0 < i < p .

Proposition 2.72 . Soit n ∈ N , n ≥ 2 , et soit k ∈ Z .Alors on les trois proprietes suivantes sont equivalentes:

i) [k]n est inversible dans Zn .ii) k est premier avec n : k ∧ n = 1 .iii) Zn = { `[k]n , ` ∈ Z } .

Exemple, les elements inversibles de Z30 sont

[1]30 , [7]30 , [11]30 , [13]30 , [17]30 , [19]30 , [23]30 , [29]30 ,

et leurs inverses sont

[1]30 , [13]30 , [11]30 , [7]30 , [23]30 , [19]30 , [17]30 , [29]30 ,

Definition 2.73 . La fonction d’Euler est la fonction

ϕ : N? → N? , ϕ(n) = # {k;∈ N? , 1 ≤ k < n et k ∧ n = 1 } :

ϕ(n) est le nombre d’entiers < n qui sont premiers avec n .

Exemplesn 1 2 3 4 5 6 7 8 9

ϕ(n) 1 1 2 2 4 2 6 4 6

p ∈ N? est premier s.s.s. ϕ(p) = p − 1 .

Proposition 2.74 . Soit n ∈ N , n ≥ 2 . Soit UZnl’ensemble des

elements inversibles de l’anneau Zn .Alors (UZn

; ×) est un groupe d’ordre ϕ(n) :

# UZn= ϕ(n) .


Comme consequence, on trouve le

Theoreme 2.75 d’Euler.Soit n ∈ N , n ≥ 2 . Alors pour tout entier k ∈ N? , on a

k ∧ n = 1 =⇒ kϕ(n) ≡ 1 (mod n) .

Ce qui signifie que ([k]n)−1 = ([k]n)ϕ(n)−1 ,si k et n sont premiers entre eux.

Idee de la preuve. Le groupe (UZn; ×) est d’ordre ϕ(n)

et [k]n ∈ UZn, ce qui implique que ([k]n)ϕ(n) = 1UZn

= [1]n .

Corollaire 2.76 Petit theoreme de Fermat.Si p ∈ N , p ≥ 2 , est premier, alors on a

∀ k ∈ Z , kp ≡ k (mod p) .

Idee de la preuve. Si p ne divise pas k , alors, comme |k| ∧ p = 1 ,on a |k|ϕ(p) ≡ 1 (mod p) , or ϕ(p) = p − 1 ,on en deduit que [kp]p = [k]p ;(car, si k = −|k| , on a soit p qui est impair, soit p = 2 et dans ce cas−[1]2 = [1]2 ) .

Theoreme 2.77 de Wilson.Soit p ∈ N , p ≥ 2 , alors on a

p premier ⇐⇒ (p − 1)! + 1 ≡ 0 (mod p) .

Idee de la preuve. ⇐ Si on a [1]p[2]p . . . [p − 1]p = −[1]p ,ca implique que, pour tout k , 1 ≤ k ≤ p − 1 , on a [k]p qui est inversibledans Zp .Comme Zp = {[0]p,[1]p, . . . , [p − 1]p} , on en deduit que Zp est un corps.

⇒ Si p est premier, alors ∀ [k]p ∈ Zp , ([k]p)p−1 − [1]p = [0]p ,

nous verons dans le chapitre sur les polynomes que cela implique l’egalite despolynomes

Xp−1 − [1]p =

p−1∏

j=1

(X − [j]p) .

En effectuant le produit de ces polynomes, on trouve l’egalite du termeconstantant, (ou on fait X = [0]p) ,

−[1]p = (−1)p−1

p−1∏

j=1

[j]p .

Si p > 2 , alors p est impair: (−1)p−1 = 1 .Si p = 2 , − [1]2 = [1]2 , dans les deux cas on trouve le resultat attendu.


2.11 Notion d’ideal et anneau quotient

Definition 2.78 . Soit (A, + , ×) un anneau, (commutatif et unitaire),et soit J ⊂ A un sous-ensemble non vide.

On dit que J est un ideal de A s.s.s. ∀ (x,y) ∈ A × J , xy ∈ J .Par exemple {0} et A sont deux ideaux de A .Un ideal J de A est dit premier s.s.s. il verifie

J 6= A et ∀ x , y ∈ A , xy ∈ J =⇒ x ∈ J ou y ∈ J .

Un ideal J d’un anneau A est dit maximal s.s.s. pour tout ideal Cde A , on a

J ⊂ C et C 6= J =⇒ C = A .

Pour tout b ∈ A? , J = bA est un ideal appeleideal principal engendre par b.

Les seuls ideaux de Z sont ceux principaux mZ , (m ∈ N) .

Definition 2.79 . Si (A, + , ×) et (B, + , ×)sont deux anneaux et si f : A → Best un morphisme du groupe (A, +) dans le groupe (B, +) , verifiant

f(xy) = f(x)f(y) , ∀ x , y ∈ A ,

on dit que f est un morphisme d’anneau.

Proposition 2.80 . Si f : A → B est un morphisme d’anneau,alors Ker(f) est un ideal de A .

Exercice 2.81 Nouvelle definition de la caracteristique.Soit (A, + , ×) un anneau commutatif et unitaire.

Soit Φ : Z → A , Φ(k) = k1A .i) Prouver que Φ est un morphisme d’anneau.ii) Prouver que Ker(Φ) = {0} , s.s.s. A est de caracteristique nul.iii) Prouver que A est de caracteristique non nul n s.s.s.

Ker(Φ) = nZ , n ≥ 2 .

iv) Dans le cas ii), prouver que # A = +∞et que dans le cas iii) on a necessairement n ≤ # A .

Proposition 2.82 . Dans un anneau A commutatif, unitaire et de ca-racteristique p premier, on a toujours

(x + y)p = xp + yp .


Idee de la preuve. On utilise la formule du binome et le fait que, commep est premier, si 1 ≤ k ≤ p − 1 , {k

p est divisible par p .

Proposition 2.83 . Soit (A ; +, ×) un anneau commutatif et unitairede caracteristique non nul n .

Si A est integre, alors n est premier.

Corollaire 2.84 . Un corps K est soit de caracteristique nulle, soit sacaracteristique est un nombre premier.

En particulier, si K est fini, sa caracteristique est un nombre premier.

Proposition 2.85 . Soit (A, + , ×) un anneau commutatif et unitaireet soit J un ideal de A .

Alors J est un sous-anneau de A , et le sous-groupe quotient (A/J, +)est un anneau commutatif et unitaire, si on le munit de la loi multiplicativesuivante

[x]J × [y]J = [xy]J .

L’element unite associe est [1]J .

Theoreme 2.86 . Soit (A, + , ×) un anneau commutatif et unitaireet soit J un ideal de A .

Alors J est un ideal premier s.s.s. A/J est un anneau integre.

Theoreme 2.87 . Soit (A, + , ×) un anneau commutatif et unitaireet soit J un ideal maximal de A .

Alors (A/J, + , ×) est un corps.

Theoreme 2.88 . Soit (K ; +, ×) un corps fini de caracteristiquep , ( p ∈ P ) . Alors ∃ n ∈ N? t.q. # K = pn .

Idee de la preuve. Comme p est premier et que c’est la caracteristiquede K , on a H = { 0K, 1K, 21K, . . . , (p − 1)1K } qui est un sous-corps deK . Par consequent K est un espace vectoriel sur le corps H .Comme K est fini, c’est un espace vectoriel sur H de dimension finie net donc # K = (# H)n = pn .

3 Polynomes

3.1 Definition et proprietes

Definition 3.1 . Soit (A, + , ×) un anneau commutatif, unitaire etintegre.


L’ensemble des polynomes sur A , (a une indeterminee x ) , est l’en-semble A[x] qui est l’union des polynomes de degre ≤ n , An[x] , pourtous les n ∈ N , avec la convention que

A0[x] = A , An[x] ⊂ An+1[x] .

Un element de p(x) ∈ A[x] s.s.s. ∃ n ∈ N t.q. p(x) ∈ An[x] .Dans ce cas p(x) s’ecrit

p(x) = a0+a1x+a2x2+. . .+an−1x

n−1+anxn =

n∑

k=0

akxk , avec (a0,a1, . . . ,an) ∈ An+1 .

Quand n = 0 et a0 6= 0 , on dit que p(x) est de degre zero ou quep(x) est un polynome constant.

Quand tous les aj sont nuls, on dit que p(x) est le polynome nul eton le note p(x) = 0 , par convention,

le degre du polynome nul est −∞ .Quand n ≥ 1 , et an 6= 0 , on dit que p(x) est de degre n.

Dans ce cas n est le plus petit entier k tel que p(x) ∈ Ak[x] .an est appele coefficient directeur de p(x) .

On notera deg(p(x)) le degre de p(x) .anxn est appele monome de degre n .

Dans la suite A designera un anneau commutatif, unitaire etintegre.

Theoreme 3.2 . L’ensemble des polynomes a coefficients dans A ,A[x] est un anneau commutatif, unitaire et integre, pour les lois sui-

vantes: si

p(x) =

n∑

k=0

akxk et q(x) =

m∑

j=0

bjxj .

Quand n < m , on pose ai = 0 pour n < i ≤ m ,et quand n > m , on pose bi = 0 pour m < i ≤ n .

Alors

p(x) + q(x) =

max(n,m)∑

j=0

(aj + bj)xj ,

et

p(x)q(x) =

n+m∑

i=0

cixi avec ci =

min(i,n)∑

k=0

akbi−k .


Proposition 3.3 . Pour deux polynomes p(x) et q(x) ∈ A[x] , on ai) deg(p(x) + q(x)) ≤ max{deg(p(x)), deg(q(x))} .ii) deg(p(x)q(x)) = deg(p(x)) + deg(q(x)) .

Remarque 3.4 . Si K est un corps, l’anneau K[x] des polynomes acoefficients dans K n’est pas un corps.

Les seuls elements inversibles de K[x] sont les constantes non nulles.

Definition 3.5 . Soit p(x) ∈ A[x] un polynome de degre n ≥ 1 ,

p(x) = a0 + a1x + . . . + anxn .

On associe a p(x) l’application

p : A → A , p(c) = a0 + a1c + . . . + ancn =

n∑

j=0

ajcj .

On dit que p est la fonction polynome associee a p(x) .Une racine, (on dit aussi un zero), de p(x) est un element c ∈ A

qui est un zero de la fonction polynome p :

0 = p(c) =n∑

j=0

ajcj .

Proposition 3.6 . Soit p(x) ∈ A[x] , deg(p(x)) = n ≥ 1 .Alors on a

{ c ∈ A , p(c) = 0 } ⇐⇒ { ∃q(x) ∈ A[x] t.q. p(x) = (x−c)q(x) } .

Idee de la preuve. On etablit que

xk =

k∑

j=0

{jkc

k−j(x − c)j , ∀ k ∈ N? .

Definition 3.7 . Soit p(x) ∈ A[x] , deg(p(x)) ≥ 1 .Soient k ∈ N? et c ∈ A .

On dit que c est un zero d’ordre k de p(x) s.s.s.

∃ q(x) ∈ A[x] t.q. p(x) = (x − c)kq(x) avec q(c) 6= 0 .

On dit aussi que c est une racine (un zero) de multiplicite k de p(x) .


Proposition 3.8 . Soit p(x) ∈ A[x] . Si on compte chaque zero dep(x) autant de fois que sa multiplicite, alors le nombre de zeros de p(x)est ≤ que le degre de p(x) .

Proposition 3.9 . Soit p(x) ∈ A[x] , p(x) = a0 + a1x+ . . .+ anxn

de degre n . Si c ∈ A est un zero de p(x) , alors c divise a0 .

Exercice 3.10 . Soit p(x) = a0 + a1x + . . . + anxn un polynome acoefficients dans Z de degre n ≥ 1 .

Sic

dest une fraction rationnelle avec PGCD(c, d) = 1 , prouver que

c divise a0 et que d divise an .

3.2 Formule de Taylor

Dans toute la suite K designera un corps.

Definition 3.11 . Soit p(x) =

n∑

j=0

ajxj ∈ K[x] .

La derivee de p(x) est le polynome p′(x) =n∑

j=1

jajxj−1 , si n ≥ 1 ,

et p′(x) = 0 , si n = 0 .Si deg(p(x)) > 0 , alors deg(p′(x)) ≤ deg(p(x)) − 1

et quand K est de caracteristique nul, deg(p′(x)) = deg(p(x)) − 1 .On definit les degres successifs de p(x) , et la derivee kieme de p(x) est

notee p(k)(x) :

p(k+1)(x) =(p(k)(x)

)′avec p(0)(x) = p(x) .

On ap(k)(x) = 0 quand k > n ,

et quand k ≤ n ,

p(k)(x) =n∑

j=k

j(j − 1) . . . (j − k + 1)ajxj−k .

Proposition 3.12 . Si p(x) et q(x) sont deux polynomes sur un corpsK . Alors on a

[p(x)q(x)]′ = p′(x)q(x) + p(x)q′(x) .


Plus generalement, pour tout entier k ≥ 1 , on a la formule de Leibnitz

[p(x)q(x)](k) =

k∑

j=0

{jkp

(j)(x)q(k−j)(x) .

Theoreme 3.13 Formule de Taylor.Soit p(x) un polynome de degre n ≥ 1 , sur un corps K .Soit c ∈ K , alors on a la formule de Taylor

p(x) =n∑

j=0

p(j)(c)

j!(x − c)j .

Pour la preuve, on fait une recurrence sur n .

Theoreme 3.14 Algorithme de Horner.Soit p(x) un polynome de degre n ≥ 1 , sur un corps K .Pour tout (x0,x1, . . . ,xn−1) ∈ Kn , ∃ (c0,c1, . . . ,cn−1,cn) ∈ Kn+1 t.q.

p(x) = c0 + c1(x − x0) + c2(x− x0)(x− x1) + . . . + cn(x − x0) . . . (x− xn−1)

= c0 +

n∑

j=1

cj

j−1∏

k=0

(x − xk) .

Si a ∈ K , alors

p(x) = d0 + d1(x − a) + (x − a)n∑

j=2

dj

j−1∏

k=1

(x − xk−1) ;

les coefficients dj sont donnes par l’algorithme de Horner:

dn = cn , dn−j = cn−j + cn−j+1(a − xn−j) pour j = 1, . . . ,n :

d0 = p(a) et d1 = p′(a) .

Theoreme 3.15 d’interpolation de Lagrange.Soit sur un corps K , n + 1 elements distincts c0, c1, . . . , cn ∈ K .

Alors ∀ (y0,y1, . . . ,yn) ∈ Kn+1 , ∃! p(x) K[x] , t.q.

deg(p(x)) ≤ n et p(cj) = yj ∀ j ∈ [[0,n]] .


3.3 Division euclidienne

Theoreme 3.16 Division euclidienne.Soit p(x) et s(x) deux polynomes sur un corps K . Si

1 ≤ deg(s(x)) ≤ deg(p(x)) ,

alors il existe un unique couple polynomes sur K , (q(x) , r(x)) verifiant

p(x) = q(x)s(x) + r(x) avec deg(r(x)) < deg(s(x)) .

q(x) est appele quotient de la division p(x) par s(x) et r(x) est appelele reste de la division de p(x) par s(x) .

On a deg(q(x)) = deg(p(x)) − deg(s(x)) .

Pratique de la division euclidienne dans Q[x] .x4 + 1 2x2 + x + 1

−12x3 − 1

2x2 + 1 1

2x2 − 1

4x − 1

8

−14x2 + 1

4x + 1

38x + 9

8On trouve que

x4 + 1 = q(x)(2x2 + x + 1) + r(x)avec q(x) = 1

2x2 − 1

4x − 1

8

et r(x) = 38x + 9

8.

Proposition 3.17 . Si K est un corps fini, alors il existe un polynomenon nul p(x) tel que la fonction polynome associee soit nulle:

∀ c ∈ K , p(c) = 0 , par exemple p(x) =∏

c∈K

(x − c) .

Mais, sur tout corps K de caracteristique nul ou non nul, un polynomep(x) sur K de degre n ≥ 1 , admet au plus n racines chacune etantcomptee autant de fois que sa multiplicite.

Definition 3.18 . Un polynome p(x) , deg(p(x)) ≥ 1 , sur un corpsK est dit irreductible s.s.s. on a

p(x) = q(x)s(x) =⇒ q(x) = c ∈ K ou s(x) = c ∈ K .

On dit qu’un polynome p(x) de degre n ≥ 1 , est scinde s.s.s.

p(x) = an(x−c1) . . . (x−cn) = an

n∏

j=1

(x−cj) , avec an , c1 , . . . , cn ∈ K .


Proposition 3.19 . Soit un polynome scinde dans un corps K :

p(x) = an(x − c1) . . . (x − cn) = an

n∏

j=1

(x − cj) , avec an 6= 0 .

Alors p(x) = an

[xn + d1x

n−1 + . . . + dn−1x + dn

], avec

d1 = −n∑

i=1

ci et dj = (−1)j∑

i1<i2<...<ij

ci1ci2 . . . cij , si j ≥ 2 .

Definition 3.20 . Soient deux polynomes p(x) et q(x) sur un corpsK , de degre ≥ 1 .

Le pgcd, (plus grand commun diviseur), de p(x) et q(x) est lepolynome d(x) = pgcd(p(x),q(x)) de coefficient directeur 1 , qui divise ala fois p(x) et q(x) , et dont le degre est maximum, (le plus grand possible).

Le ppcm, (plus petit commun multiple), de p(x) et q(x) est lepolynome m(x) = ppcm(p(x),q(x)) de coefficient directeur 1 , qui estdivisible a la fois par p(x) et q(x) , et dont le degre est minimal, (le pluspetit possible).

Quand pgcd(px), q(x)) = 1 , on dit que les deux polynomes sontpremiers entre eux.

Proposition 3.21 . Si p(x) et q(x) sont deux polynomes non nuls surun corps K , alors on a

pgcd(p(x), q(x)) × ppcm(p(x), q(x)) = c p(x)q(x) ,

ou c−1 est le produit des coefficients directeurs de p(x) et q(x) .

Theoreme 3.22 Algorithme d’Euclide pour les polynomes.Soit p(x) et q(x) deux polynomes sur un corps K .On suppose que 1 ≤ deg(q(x)) ≤ deg(p(x)) .On definit une suite finie de polynomes rj(x) de la facon suivante.

r0(x) = p(x) , r1(x) = q(x) ,

avec la relation de recurrence basee sur la division euclidienne :

si rj(x) 6= 0 , ∃! sj(x) , rj+1(x) ∈ K[x] t.q.

rj−1(x) = sj(x)rj(x) + rj+1(x) , deg(rj+1(x)) < deg(rj(x))

Alors le pgcd de p(x) et de q(x) , est le dernier reste rk(x) non nuldivise par son coefficient directeur.


Pour la preuve on utilise le lemme suivant.

Lemme 3.23 . Si g(x) , h(x) ∈ K[x] et si r(x) , k(x) ∈ K[x] sontdonnes par la division euclidienne:

g(x) = k(x)h(x) + r(x) , deg(r(x)) < deg(h(x)) ,

alors pgcd[g(x), h(x)] = pgcd[h(x), r(x)] .

Proposition 3.24 . Une racine c d’un polynome p(x) sur un corpsK , de caracteristique nulle, est d’ordre k s.s.s.

p(j)(c) = 0 ∀ j ≤ k − 1 et p(k)(c) 6= 0 .

3.4 Adjonction de racine: extension de corps

Theoreme 3.25 . Soit K un corps.Alors l’anneau de ses polynomes est principal:I ⊂ K[x] est un ideal de K[x] s.s.s.

∃ q(x) ∈ K[x] t.q. I = K[x]q(x) = { p(x)q(x) ; p(x) ∈ K[x] } .

Corollaire 3.26 . Soient p(x) et q(x) deux polynomes non nuls surun corps K . Alors on a

∃ u(x) , v(x) ∈ K[x] t.q. u(x)p(x) + v(x)q(x) = pqcd[ p(x) , q(x) ] .

Theoreme 3.27 de Bezout pour les polynomes.Soient p(x) et q(x) deux polynomes non nul sur un corps K .Alors p(x) et q(x) sont premiers entre eux s.s.s.

∃ u(x) , v(x) ∈ K[x] t.q. u(x)p(x) + v(x)q(x) = 1 .

Dans le Corollaire 3.26 et le Theoreme ci-dessous, le couple de polynome(u(x), v(x)) est appele couple de Bezout associe a ( p(x), q(x) ) .

L’algorithme d’Euclide permet de retrouver le couple de Bezout commedans le cas des entiers.

Theoreme 3.28 Adjonction de racines.Soit q(x) un polynome, de degre n ≥ 1 , irreductible sur un corps K .Alors l’ideal principal I = q(x)K[x] est maximal et l’anneau quotient

K = K[x]/I est un espace vectoriel sur K de dimension n , de base

B = { [1]I , [x]I , . . . , [xn−1]I } .


De plus K est un corps verifiant les deux proprietes suivantes:i) Le corps K est isomorphe au sous-corps de K ,

{[c]I ; c ∈ K} = K[1]I = P (K) ,

ici P : K[x] → K = K[x]/I designe la projection canonique.

ii) Si α = P (x) = [x]I , en identifiant K a P (K) , on peut considerer

q(x) comme un polynome sur K , dans ce cas q(α) = 0 .

Corollaire 3.29 . Soit q(x) un polynome, de degre n ≥ 1 , irreductiblesur un corps K .

Alors il existe un corps K ayant les proprietes suivantes:i) K soit un sous-corps de Kii) K est un espace vectoriel sur K de dimension ≤ n!

iii) q(x) est scinde dans K .

Corollaire 3.30 . Si p(x) = x2 + bx + c est un polynome de degre 2sur un corps K et si p(x) est irreductible dans K[x] ,

alors p(x) est scinde dans K = K[x]/p(x)K[x] .

Exemple 3.31 . • p(x) = x2 + 1 dans Q puis dans R .• p(x) = [1]2x

2 + [1]2x + [1]2 dans Z2 .• p(x) = x2 + x + 1 dans R .• p(x) = [1]2x

2 + [1]2 est scinde dans Z2 .

Theoreme 3.32 de d’Alembert.Tout polynome sur C , non constant, est scinde dans C .

Theoreme 3.33 . Soient K un corps et K ⊂ K un sous-corps deK . Alors K est un espace vectoriel sur le corps K verifiant la proprietesuivante: pour tout α ∈ K \ K , on a 2 cas possibles,

1. ∀ n ∈ N? , Bn = {α0,α1, . . . ,αn−1} est un systeme libre de n

vecteurs de K ;

2. ∃ n ∈ N , n ≥ 2 , t.q. Bn soit libre et Bn+1 soit lie.

Dans ce deuxieme cas, on a

∃! p(x) = xn +

n−1∑

j=0

λjxj ∈ K[x] t.q. p(α) = 0 .

p(x) est irreductible dans K .

Le sous-espace vectoriel L de K , engendre par Bn , est un sous-corpsde K qui est isomorphe au corps K[x]/p(x)K[x] .


Idee de la preuve du cas 2. L’hypothese sur n implique l’existencede p(x) , et par l’absurde son irreductibilite.

Pour voir que L est un corps, on remarque que c’est un anneau qui estisomorphe a K[x]/p(x)K[x] en considerant l’application

u : K[x]/p(x)K[x] → L , u([q(x)]) = q(α) .

4 Treillis et points fixes

4.1 Borne superieure et borne inferieure

Definition 4.1 . Soit (E; ≤) un ensemble ordonne. Soit A ⊂ E .• Un majorant de A, quand il existe, est un element c ∈ E t.q.

∀ a ∈ A , a ≤ c .

L’ensemble des majorants de A sera note Major(A) .Quand Major(A) 6= ∅ , on dit que A est majore.

• Un minorant de A, quand il existe, est un element c ∈ E t.q.

∀ a ∈ A , c ≤ a .

L’ensemble des minorants de A sera note minor(A) .Quand minor(A) 6= ∅ , on dit que A est minore.

• On dit que A admet un maximum s.s.s. A ∩ Major(A) 6= ∅ .Un element b ∈ E est un maximum de A s.s.s.

b ∈ A et a ≤ b , ∀ a ∈ A .

• On dit que A admet un minimum s.s.s. A ∩ minor(A) 6= ∅ .Un element b ∈ E est un minimum de A s.s.s.

b ∈ A et b ≤ a , ∀ a ∈ A .

Proposition 4.2 . Soient (E; ≤) un ensemble ordonne et A ⊂ E .• Si A admet un maximum, alors il est unique, on le notera max(A) .• Si A admet un minimum, alors il est unique, on le notera min(A) .

Definition 4.3 . Soient (E; ≤) un ensemble ordonne et A ⊂ E .• On dit que A admet une borne superieure, ou tout simple une

borne sup., s.s.s. A est majoree et min[Major(A)] existe, on le note alors


sup (A) et on l’appelle borne superieure de A. sup(A) est caracterisepar

∀ a ∈ A , a ≤ sup(A) et ∀ b ∈ Major(A) , sup(A) ≤ b .

• On dit que A admet une borne inferieure, ou tout simplement uneborne inf., s.s.s. A est minore et max[minor(A)] existe, on le note alorsinf (A) et on l’appelle borne inferieure de A. inf(A) est caracterise par

∀ a ∈ A , inf(A) ≤ a et ∀ b ∈ minor(A) , b ≤ inf(A) .

Proposition 4.4 . Soient (E; ≤) un ensemble ordonne et A ⊂ E .• Si max(A) existe, alors sup(A) = max(A) .• Si min(A) existe, alors inf(A) = min(A) .

Exemple 4.5 . Les intervalles de R , ]a,b[ , ]a,b] , [a,b[ , [a,b] .(N; ≤) , A ⊂ N , A ⊂ [[0, n]] .

Exercice 4.6 . Soit F un ensemble. On considere l’ensemble ordonnedes parties de F , (P(F ); ⊂) . On notera E = P(F ) .

i) Soient A1 , . . . , An , n sous ensembles de F . Prouver que

sup ({A1, . . . , An}) =

n⋃

j=1

Aj et inf ({A1, . . . , An}) =

n⋂

j=1

Aj .

ii) Etablir un resultat analogue dans le cas d’une suite infinie de sous-ensembles de F , (Aj)1≤j : si A = {A1, A2, . . . , Aj, Aj+1, . . .} ⊂ E ,qu’on a alors

sup(A) =

+∞⋃

j=1

Aj et inf(A) =

+∞⋂

j=1

Aj .

Exercice 4.7 . i) Montrer que (N?; | ) est un ensemble ordonne:

a | b s.s.s. a divise b .

Cet ordre est-il total?ii) Prouver que ∀ a , b ∈ N? , on a

sup ({a,b}) = PPCM(a,b) et inf ({a,b}) = PGCD(a,b) .

iii) Prouver que max ({a,b}) existe s.s.s. a | b ou b | a .Meme question en remplacant max par min .

iv) Si a1, a2, . . . , an sont n entiers > 0 , prouver que

sup ({a1,a2, . . . ,an}) = PPCM(a1,a2, . . . ,an)

et queinf ({a1,a2, . . . ,an}) = PGCD(a1,a2, . . . ,an) .


4.2 Les treillis

Definition 4.8 . Un ensemble ordonne (E; ≤) est appele un treilliss.s.s.

∀ x , y ∈ E , sup ({x,y}) et inf ({x,y}) existent .

Exemple 4.9 . (P(E); ⊂) , (N; ≤) , (N?; | ) , (R; ≤) sont des treillisainsi que (A; ≤) , quand A ⊂ N ou quand A ⊂ R , (pour l’ordre naturel≤ sur R et sur N ) .Par contre, tout A ⊂ N? n’est pas un treillis pour l’ordre ”divise” | .

Exercice 4.10 . Soit (E; ≤) un treillis et soient a , b et c ∈ E .i) Prouver que sup [{a, sup({b,c})}] = sup [{sup({a,b}), c}] = sup [{sup({a,c}), b}] .ii) Prouver que inf [{a, inf({b,c})}] = inf [{inf({a,b}), c}] = inf [{inf({a,c}), b}] .iii) Si a ≤ a′ et b ≤ b′ , prouver que

sup ({a, b}) ≤ sup ({a′, b′}) et inf (a, b}) ≤ inf ({a′, b′}) .

Proposition 4.11 . Soit (E; ≤) un ensemble ordonne.Alors E est un treillis s.s.s. tout sous-ensemble fini A ⊂ E admet

une borne sup. et une borne inf.:

A ⊂ E et #A < ∞ =⇒ sup(A) et inf(A) existent .

Pour la preuve, on fait une recurrence sur le cardinal des sous-ensembles.

Definition 4.12 . Un treillis (E; ≤) est dit complet s.s.s.

∀ A ⊂ E , A 6= ∅ =⇒ sup(A) et inf(A) existent .

Exemple 4.13 . (P(E); ⊂) et ([a,b]; ≤) sont des treillis complet.Ni (R; ≤) ni (N; ≤) n’est un treillis complet.

Proposition 4.14 . Un ensemble ordonne (E; ≤) ayant un plus petitelement, ( min(E) existe), est un treillis complet s.s.s. on a

∀ A ⊂ E , A 6= ∅ , sup(A) existe .

Idee de la preuve. Pour la reciproque, on etablit que

sup[Minor(A)] = inf(A) .

Proposition 4.15 . Soit (E; ≤) un treillis complet. Si A ⊂ B ⊂ E ,alors on a inf(B) ≤ inf(A) ≤ sup(A) ≤ sup(B) .

Exercice 4.16 . i) Soit A = {a1, . . . , an} un sous-ensemble fini deN? . Prouver que (A; | ) est un treillis complet s.s.s.

PPCM(a1, . . . ,an) ∈ A et PGCD(a1, . . . ,an) ∈ A .

ii) Plus generalement, prouver qu’un ensemble ordonne fini, (E; ≤) telque min(E) et max(E) existent, est toujours un treillis complet.


4.3 Points fixes pour les applications croissantes

Dans ce sous-chapitre (E; ≤) est un ensemble ordonne.Rappellons que si f : E → E , est une application de E dans E ,• on dit que f est croissante s.s.s.

∀ x , y ∈ E , x ≤ y =⇒ f(x) ≤ f(y) ;

• a ∈ E est dit un point fixe de f s.s.s. f(a) = a .

Theoreme 4.17 . Soient un treillis complet (E; ≤) et une applicationcroissante f : E → E .

Alors l’ensemble des points fixes de f , F ix(f) , n’est pas vide etmax[Fix(f)] et min[Fix(f)] existent:

∃ a , b ∈ E , t.q. f(a) = a ≤ b = f(b) et t.q. f(c) = c =⇒ a ≤ c ≤ b .

Idee de la preuve. Soit F = {x ∈ E ; x ≤ f(x)} .Comme E est un treillis complet, min(E) existe et il est clair que

min(E) ∈ F : F 6= ∅ .En utilisant de nouveau que E est un treillis complet, on trouve que

b = sup(F ) existe.On remarque que la croissance de f entraine que x ∈ F ⇒ f(x) ∈ F .On en deduit que f(b) ∈ F et donc f(b) ≤ sup(F ) = b .Or b ∈ F et donc b ≤ f(b) ; on conclut que b = f(b) :

b est un point fixe et c’est le plus grand, car Fix(f) ⊂ F .En considerant G = {x ∈ E ; f(x) ≤ x} , on montre de la meme facon

que max(E) ∈ G , que a = inf(G) ∈ Fix(f) , et que c’est le plus petitpoint fixe.

Theoreme 4.18 . Soient (E; ≤) un treillis complet et une applicationf : E → E verifiant ∀ A ⊂ E , A 6= ∅ , f [sup(A)] = sup[f(A)] .

Alors f est croissante. De plus, si e = min(E) ,le plus petit point fixe de f est

inf[Fix(f)] = sup ( { fn(e) ; n ∈ N } ) .

Idee de la preuve.• Croissance. On remarque que si x ≤ y ,

alors sup({x,y}) = yet l’hypothese sur f donne alors que

f(y) = sup({f(x),f(y)}) , par consequent f(x) ≤ f(y) .• Preuve de a = sup({fn(e) ; n ∈ N}) est un point fixe.


L’hypothese sur f implique que

f(a) = sup({fn+1(e) ; n ∈ N}) = sup(H) .

Or a = sup(H ∪ {e}) et e ≤ f(a) , on en deduit que

f(a) = sup(H) = sup(H ∪ {e}) = a .

• Preuve de a minore les points fixes.Si c = f(c) est un point fixe, on montre par recurrence que∀ n ∈ N , fn(e) ≤ c , ce qui prouve que

a = inf({fn(e) ; n ∈ N}) ≤ c .

Remarque 4.19 . Si une fonction reelle d’un intervalle ferme et bornedans lui-meme, f : [a, b] → [a, b]est croissante alors lim

n→+∞fn(a)

est un point fixe de f et c’est le plus petit.

Corollaire 4.20 . Sous les hypotheses du Theoreme 4.18, si E est fini,alors ∃ k ∈ [[0, #E]] t.q. f k(e) soit le plus petit point fixe de f .

5 Notations et indexes

Index

[[1,n]] = {1,2, . . . ,n}, 5A∆B = (A ∪ B) \ (A ∩ B), 4A ∩ B (intersection de A et B), 3A ∪ B (union de A et B), 3A \ B = {x; x ∈ A et x /∈ B}, 3A ⊂ B (A est inclus dans B), 3E × F produit cartesien, 5G + H, 26G/H (groupe quotient), 31Im(f) (image de f), 7Major(A) (majorants de A), 48PGCD(a1, . . . ,an), 26PPCM(a1, . . . ,an), 26SE (les bijections de E), 10Sn (les permutations sur [[1, n]]),

23Z(G) (centre de G), 24[a]H = aH, 31[j]m = j + mZ, 14[j]m (classe j (modulo m), 30{A

E = E \A (on suppose A ⊂ E), 3¬A (non(A)), 5A ∨ B (A ou B),5A ∧ B (A etB), 5Gr(f) (graphe de f), 7P(E) (l’ensemble des sous-ensembles

de E), 3P (nombres premiers), 21∅ (ensemble vide), 3A (anneau commut. unit.integre),

40Fn (racines niemes de 1), 23K (corps), 41T (cercle unite), 23Zm = {[0]m,[1]m, . . . ,[m − 1]m}, 14Zm = {[0]m,[1]m, . . . ,[m − 1]m}, 30inf(A) (borne inf), 49]E (nombre d’elements de E), 10

sup(A) (borne sup.), 49ϕ(n) (fonction d′Euler), 36a, b (a divise b)21a - b (a ne divise pas b), 21a ∨ b (PPCM), 22a ∧ b (PGCD), 22c ∈ A (c appartient a A), 3deg(p(x)) (degre), 40f(A) = {f(x); x ∈ A} (si A sous-

ensemble), 7fn = f ◦ f ◦ . . . ◦ f n − fois, 8f−1(B) = {x t.q. f(x) ∈ B} (si B

sous-ensemble), 8idE (application identite), 8mZ = {mk k ∈ Z}, 9minor(A) (minorants de A), 48s.s.s. (si et seulement si), 3t.q. (tel que), 5xRy (x en relation avec y, 13element neutre, 17element symetrique, 17

abelien, 23algebre de Boole, 19anneau, 32antecedent, 7antisymetrique, 13application croissante, 15arrangement de k elements, 10associative, 17

Bezout, 46bijective, 8borne inf., 49borne sup., 48

caracteristique, 38carcteristique, 34cardinal, 10

53


centre d’un groupe, 24classe dequivalence, 14combinaison, 11commutatif, 17complementaire d’un sous-ensemble,

3corps, 34couple de Bizout, 27

denombrable, 11disjoint, 3distingue, 31distributive, 17diviseur de zero, 33division de polynomes, 44

endomorphisme, 25, 32ensemble d’arrivee, 7ensemble de definition, 7ensemble de depart, 7ensemble quotient, 14Euler, 37extension de corps, 35

Fermat, 37fonction d’Euler, 36fonction polynome, 41formule de Taylor, 43fraction, 35

graphe, 7groupe, 23groupe cyclique, 24groupe homogene, 24groupe produit, 25

Horner, 43homomorphisme de groupe, 25

ideal, 38ideal premier, 38ideal principal, 38Im(f), 25

image, 7injectif, 8integre, 34inverse, 17inverse a droite, 8inverse a gauche, 8inverse, inversible, 8inversible, 33irreductible, 44isomorphisme de groupe, 25

Ker(f), 25

loi interne, 17

majorant, 48maximal, 38maximum, 48minimum, 48minorant, 48monome, 40monoıde, 18morphisme d’anneau, 38morphisme de groupe, 25

nombre premier, 21noyau d’un morphisme, 25

ordre, 15ordre d’un element d’un groupe, 24ordre d’un groupe, 24ordre lexicographique, 16ordre produit, 16

pgcd de 2 polynomes, 45PGCD, (plus grand commun divi-

seur), 22point fixe, 16polynomes premiers, 45ppcm de 2 polynomes, 45PPCM, (plus petit commun mul-

tiple), 22premiers entre eux, 22, 26


produit de groupes, 25

reflexive, 13racine d’ordre k, 41, 46racine d’un polynome, 41relation binaire, 13relation d’equivalence, 13

scinde, 44semi-groupe, 18simplifiable, 18sous groupe, 23sous-anneau, 32sous-corps, 35sous-groupe distingue, 25, 31suite, 12surjectif, 8surjection canonique, 31symetrique, 13

table d’une loi, 18transitive, 13treillis, 50treillis complet, 50

Wilson, 37

zero d’ordre k, 41zero d’un polynome, 41

Documents

Table des mati eres - math.sciences.univ-nantes.frmorame/SYM04/Alg052P.pdfSYM0400, Alg ebre de base. 1 LICENCE 2004/2005 de l’UNIVESITE de NANTES SYM0400 , ALGEBRE de BASE 11 Janvier