Cette publication est uniquement disponible à l'achat
Lire un extrait Achetez pour : 14,99 €

Téléchargement

Format(s) : PDF

avec DRM

Partagez cette publication

Vous aimerez aussi

Arithmétique
François Liret
Arithmétique
Couverture © Petr Vaclavek/Fotolia
© Dunod, Paris, 2011 ISBN 978-2-10-056726-3
TABLE
DES
MATIÈRES
Chapitre 1 • Relation d’équivalence et ensemble quotient 1.1 Partition et relation d’équivalence 1.2 Ensemble quotient 1.3 Passage au quotient d’une application Exercices Solutions
Chapitre 2 • Divisibilité dansZ 2.1 Multiple et diviseur 2.2 Division euclidienne 2.3 PGCD 2.4 Équationax+by=c,(x,y)Z×Z 2.5 PPCM 2.6 Décomposition en facteurs premiers Exercices Solutions
Chapitre 3 • Congruence 3.1 Relation de congruence 3.2 Règles de calcul 3.3 Résolution d’équations 3.4 Triplets pythagoriciens Exercices Solutions
Chapitre 4 • Groupes 4.1 Notion de groupe 4.2 Sous-groupe 4.3 Morphisme de groupe 4.4 Sous-groupe engendré par un élément 4.5 Ordre d’un élément 4.6 Classes modulo un sous-groupe © Dunod. La photocopie non autorisée est un délit.
1 4 5 7 8
11 13 14 18 19 20 22 24
29 31 33 35 36 37
43 46 48 51 52 54
V
Table des matières
VI
4.7 Sous-groupe distingué Exercices Solutions
Chapitre 5 • Groupes cycliques 5.1 Définition et premières propriétés 5.2 Sous-groupes d’un groupe cyclique 5.3 Morphismes Exercices Solutions
Chapitre 6 • Anneaux et corps 6.1 Notions générales 6.2 Anneau quotient 6.3 AnneauZ/nZ 6.4 Le corpsFp Exercices Solutions
Chapitre 7 • Polynômes 7.1 Polynômes à coefficients dans un anneau 7.2 AnneauK[X] 7.3 Polynômes à coefficients dansFp 7.4 Calcul des coefficients binomiaux modulop Exercices Solutions
Chapitre 8 • Le corpsFp 8.1 Les carrés dansFp 8.2 Le groupeF p 8.3 Le calcul des puissances modulo 8.4 Applications à la cryptographie Exercices Solutions
Chapitre 9 • Anneaux principaux, anneaux euclidiens 9.1 Anneau principal 9.2 Polynômes irréductibles deK[X] 9.3 Anneau euclidien 9.4 Des anneaux pour l’arithmétique
58 63 64
69 72 73 75 77
83 89 91 96 97 98
103 108 110 113 115 116
119 124 126 126 128 130
135 140 145 146
Exercices Solutions
Chapitre 10 • Deux problèmes classiques 10.1 Entiers somme de deux carrés 10.2 L’équation de Pell-Fermat Exercices Solutions
Chapitre 11 • Construction de corps 11.1 Caractéristique d’un corps 11.2 Sous-corps 11.3 Quotient d’un anneau de polynômes 11.4 Extension de corps Exercices Solutions
Chapitre 12 • Corps finis 12.1 Structure des corps finis 12.2 L’automorphisme de Frobenius 12.3 Sous-corps 12.4 Polynômes irréductibles et corps finis 12.5 Polynômes irréductibles deFp[X] 12.6 Applications à la cryptographie Exercices Solutions
Chapitre 13 • Réciprocité quadratique 13.1 Symbole de Legendre 13.2 La loi de réciprocité quadratique Exercices Solutions
Principales notations
Index
© Dunod. La photocopie non autorisée est un délit.
Table des matières
151 152
157 160 165 167
173 174 177 181 185 187
195 199 200 202 205 207 208 210
215 217 221 222
227
229
VII
RELATION DÉQUIVALENCE ET ENSEMBLE QUOTIENT
1.1 Partition et relation d’équivalence 1.2 Ensemble quotient PLAN 1.3 Passage au quotient d’une application
1
On est souvent amené à partager les éléments d’un ensemble en différentes classes, c’est-à-dire à définir une partition de cet ensemble. Il devient alors possible de raison-ner et de calculer sur les classes : c’est un puissant procédé algébrique. OBJECTIF
1.1
PARTITION ET RELATION DÉQUIVALENCE
Définition SoitEun ensemble. UnepartitiondeEest la donnée de partiesCideE, non vides, deux à deux disjointes et dont la réunion estE. On dit que les partiesCi sont desclasses.
Exemple NotonsC0l’ensemble des entiers impairs,C1l’ensemble des entiers multiples de 2 mais pas de 4 et plus généralement, pour tout entiern0, notons n n+1 Cn.l’ensemble des entiers multiples de 2 mais pas de 2 Les parties(Cn)nNforment une partition deZ. © Dunod. La photocopie non autorisée est un délit.
1
Chapitre 1 • Relation d’équivalence et ensemble quotient
2
1.1.1 Comment définir une partition d’un ensembleE? Il y a essentiellement deux procédés.
1. Au moyen d’une application définie surE Soitf:E−→Fune application surjective. Rappelons que pour tout élémentbF, la partie deEdéfinie par 1 f(b)= {xE|f(x)=b} 1 s’appellel’image réciproque de b par f. Puisquefest surjective,f(b)est non vide. 1 Les partiesCb=f(b)sont deux à deux disjointes, car s’il existexcommun à CbetCb, alorsb=f(x)=b; leur réunion estE, car pour toutxE, on a   1 xff(x), doncxCf(x). Les partiesCbforment donc une partition deE.
Exemple Soitf:Z×Z−→Zl’application définie parf(x,y)=2x+3y. L’applicationfest sur-jective car pour tout entierkZ, on af(k,k)= −2k+3k=k. Ainsi par exemple, les parties
C0= {(x,y)Z×Z|2x+3y=0}etC5= {(x,y)Z×Z|2x+3y=5} sont des classes de la partition deZ×Zdéfinie parf.
2. Au moyen d’une relation d’équivalence surE
Définition Une relationsur un ensembleEest unerelation d’équivalencesi elle est (i)réflexive :aE,aa (ii)symétrique :a,bE,(ab)⇒(ba) (iii)transitive :a,b,cE,(abetbc)⇒(ac) Pour toutaE, l’ensemble cl(a)= {xE|xa}s’appellela classe (d’équi-valence) de a.
Proposition
Soitune relation d’équivalence surE. Pour toutaE,acl(a). Pour tousa,bE, on a l’équivalence :ab⇐⇒cl(a)=cl(b). Pour tousa,bE, si cl(a)=/cl(b), alors cl(a)cl(b)= ∅.
DÉMONSTRATION. Soienta,bE. Puisqueaad’après(i), on aacl(a). Supposonsab. Alors pour toutzcl(a), on azaet puisqueab, il s’en-suit (transitivité)zb, donczcl(b). Cela montre que cl(a)cl(b); mais