Cours de Structures mathématiques au format pdf

Ann´ee universitaire 2004-2005
´ ´UNIVERSITE D’ORLEANS
Olivier GARET
Structures Math´ematiques
(Licence 1`ere ann´ee semestre 2)2Table des mati`eres
Table des mati`eres i
1 Construction deN 1
1.1 Lois de composition interne . . . . . . . . . . . . . . . . . . . 1
1.2 Groupes, sous-groupes . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Axiomes de Peano . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 N, ce mono¨ıde . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4.1 D´efinition de l’addition . . . . . . . . . . . . . . . . . . 3
1.4.2 Propri´et´es de . . . . . . . . . . . . . . . . . . 4
1.4.3 Relation d’ordre surN . . . . . . . . . . . . . . . . . . 5
1.5 Multiplication des entiers . . . . . . . . . . . . . . . . . . . . . 8
1.5.1 D´efinition et propri´et´es . . . . . . . . . . . . . . . . . . 8
1.5.2 Division euclidienne . . . . . . . . . . . . . . . . . . . . 8
1.5.3 Bases de num´eration . . . . . . . . . . . . . . . . . . . 9
1.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2 Z 13
2.1 Relations d’´equivalentes . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 Relations d’´equivalences et partitions . . . . . . . . . . 13
2.1.2 Ensemble quotient . . . . . . . . . . . . . . . . . . . . 14
2.2 ConstruireZ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 La structure d’anneau . . . . . . . . . . . . . . . . . . . . . . 17
2.3.1 vocabulaire . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.2 Propri´et´es deZ . . . . . . . . . . . . . . . . . . . . . . 17
2.3.3 R`egles de calcul . . . . . . . . . . . . . . . . . . . . . . 17
2.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3 Divisibilit´e 23
3.1 Sous-groupes deZ . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 PGCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.1 Compl´ements sur les groupes . . . . . . . . . . . . . . 24
i`ii TABLE DES MATIERES
3.2.2 PGCD de deux entiers . . . . . . . . . . . . . . . . . . 24
3.2.3 Propri´et´es de base . . . . . . . . . . . . . . . . . . . . 24
3.2.4 Algorithme d’Euclide . . . . . . . . . . . . . . . . . . . 26
3.2.5 LemmedeGauss–Application`alar´esolutiondel’´equation
de l’´equation au+bv =n . . . . . . . . . . . . . . . . 27
3.2.6 PGCD de plusieurs entiers . . . . . . . . . . . . . . . . 29
3.3 PPCM de deux ou entiers . . . . . . . . . . . . . . . 30
3.4 Congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4 Nombres premiers 35
4.1 D´efinition et premi`eres propri´et´es . . . . . . . . . . . . . . . . 35
4.2 D´ecomposition d’un nombre en produit de facteurs premiers . 36
4.2.1 Existence et unicit´e de la d´ecomposition . . . . . . . . 36
4.2.2 Application au calcul du PGCD et du PPCM . . . . . 37
4.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5 Z/nZ 41
5.1 Construction de l’anneauZ/nZ . . . . . . . . . . . . . . . . . 41
5.2 Inversibles deZ/nZ . . . . . . . . . . . . . . . . . . . . . . . . 41
5.2.1 Caract´erisation des inversibles . . . . . . . . . . . . . . 41
5.2.2 Groupe des ´el´ements inversibles – indicatrice d’Euler . 42
5.3 Th´eor`eme chinois . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.4 Calcul de l’indicatrice d’Euler . . . . . . . . . . . . . . . . . . 44
5.5 Codage RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47Chapitre 1
Construction deN
1.1 Lois de composition interne
D´efinition: Soit X un ensemble. On appelle loi de composition interne sur
X toute application ? de X×X dans X :
X×X → X
(x,y) 7→ x?y :=?(x,y)
Ici, on choisira d’utiliser la x?y plutˆot que ?(x,y). Voici pourquoi :
D´efinition: Soit X un ensemble et ? une loi de composition interne sur X.
On dit que ? est associative si on a
∀(x,y,z)∈X×X×X (x?y)?z =x?(y?z)
Ainsi, pour une loi de composition interne associative, on peut´ecrire x?y?z
sans que cel`a soit source d’ambigu¨ıt´e.
Exemples: + et× sont des lois de composition internes surR. / est une loi
de composition interne sur ]0,+∞[.
De plus, + et× sont des lois de composition internes associatives surR.
Cependant,/n’estpasuneloidecompositioninterneassociativesur]0,+∞[
car 1/(1/2)=2 n’est pas ´egal `a (1/1)/2=1/2.
D´efinition: On dit qu’un ´el´ement e est neutre pour la loi de composition
interne ? sur X si
∀x∈X e?x =x?e =x.
0Ilyatoujoursauplusun´el´ementneutre,carsieete sontdeux´el´ements
0 0neutre e=e?e =e.
D´efinition: Le couple (X,?) form´e par un ensemble X et une loi de com-
position interne associativesur X poss´edant un´el´ement neutre est appel´e un
mono¨ıde.
12 CHAPITRE 1. CONSTRUCTION DEN
Exemples: Si G est une famille d’applications d’un ensemble E dans lui
mˆeme telle que
– Id ∈G.E
– ∀(f,g)∈G×G f◦g∈G,
alors (G,◦) est un mono¨ıde
Par exemple, l’ensemble des applications affines surR forme un mono¨ıde.
D´efinition: On dit qu’un ´el´ement x d’un mono¨ıde (X,?) dont l’´el´ement
neutre est not´e e est inversible s’il existe un y∈X tel que
x?y =y?x =e.
S’ilexiste,untel´el´ementestn´ecessairementunique:eneffetsix?y =y?x =e
0 0et x?y =y ?x=e, alors
0 0 0 0y =y ?e=y ?(x?y)=(y ?x)?y =e?y =y.
−Usuellement,onnotex 1l’inversedexlorsqu’ilexiste.(Ontrouveraplus
?−1rarement x ) : cette notation n’est employ´ee que si plusieurs structures de
groupepsontmisessurl’ensembleconsid´er´eetqu’uneambiguit´eestpossible.)
l
1.2 Groupes, sous-groupes
D´efinition: Un mono¨ıde (G,?) dont tous les ´el´ements sont inversibles est
appel´e un groupe.
Exemples: SiG estunefamilledebijectionsd’unensembleE dansluimˆeme
telle que
– Id ∈G.E
– ∀(f,g)∈G×G f◦g∈G,
alors (G,◦) est un groupe.
Lorsque X est un ensemble fini, on note S(X) le groupe form´e par l’en-
semble des bijections de X dans lui-mˆeme muni de la composition
Traditionnellement, on appelle “permutations” les ´el´ements deS(X), et,
fort logiquement, on appelle ce groupe le groupe des permutations.
D´efinition: Soit (G,?) un groupe, H une partie de G. On dit que H est un
sous-groupe de G si (H,?) un groupe.
On montre (le faire!) que H est un sous-groupe de G si et seulement si
−1pour tous x,y de H, x?y ∈H.
On dit souvent d’un sous-groupe deS(X) qu’il est un “groupe de permu-
tations”. Historiquement, c’est l’´etude de groupes de permutations qui ont
amen´e `a l’invention de la notion de groupes1.3. AXIOMES DE PEANO 3
1.3 Axiomes de Peano
Les axiomes de Peano postulent l’existence d’un ensemble N contenant
un ´el´ement 0 et d’une application injective
s:N → N\{0}
x 7→ s(x)
et v´erifiant la propri´et´e suivante : si A⊂N, 0∈A et s(A)⊂A, alors A=N.
Cette propri´et´e est appel´ee principe de r´ecurrence.
Notation : on note couramment 1 = s(0), 2 = s(1), 3 = s(2), 4 = s(2),
5=s(4), 6=s(5), 7=s(6), 8=s(7), 9=s(8).
Dans la suite, on verra que s(n) est ce que nous avons l’habitude n+1,
ou` plus pr´ecis´ement que l’on peut d´efinire une addition “+” (en fait une loi
de composition interne) de telle mani`ere que n+1=s(n).
Onconnaitplussouventlapropri´et´eder´ecurrencesouslaformesuivante:
si P(n) → P(n + 1) et que P(0), alors P(n) est vraie pour tout n. Pour
d´emontrer cel`a, il suffit d’appliquer le principe de r´ecurrence `a l’ensemble
A={n∈N;P(n) est vrai}.
Uneautrecons´equencesimpleduprincipeder´ecurrenceestquepourtout
n=0, exists k∈N;n=s(k). En effet notons A={0}∪{s(k);k∈N : il est
facile de voir que 0∈ A et que s(A)⊂ A. On en d´eduit que A =N, ce qui
signifie que tout entier naturel est soit 0, soit l’image d’un entier naturel par
s.
1.4 N, ce mono¨ıde
1.4.1 D´efinition de l’addition
Il est possible de d´efinir une loi de composition interne + sur N ca-
ract´eris´ee par les identit´es
n+1=s(n)
n+s(p)=s(n+p)
Il n’est pas ´evident d’´ecrire une preuve rigoureuse de l’existence d’une
telle loi de composition interne. Donnons juste quelques id´eees. Si on met
ensemble les deux propri´et´es ci-dessus et que l’on fait p = 0, on a s(n) =
n+1 = n+s(0) = s(n+0). Comme s est injective, on doit n´ecessairement
d´efinirn+0=n.Onsaitdonccommentd´efinirn+0etn+1.Voyonscomment
d´efinir n+2 : comme 2 = s(1), il faut d´efinir n+2 = n+s(1) = s(n+1),
8<6:4 CHAPITRE 1. CONSTRUCTION DEN
ce qui est bien une d´efinition correcte puique s+1 est d´efinie. De mˆeme on
d´efinit n+3 par n+3 = s(n+2), etc. Toute la difficult´e consiste `a donner
unsensrigoureuxa`ce“etc.”Nouspr´ef´eronsrenvoyerlelecteura`unouvrage
de r´ef´erence pour cette preuve assez technique.
1.4.2 Propri´et´es de l’addition
Nousallonsmontrerquelaloidecompositioninterned´efiniec