Source: https://pl.b-ok.org/book/703250/6bc0a2?dsource=recommend
Timestamp: 2020-06-05 06:47:42+00:00

Document:
Exercices résolus d'algèbre du cours de mathématiques, tome 1 | Jean Marie Arnaudiès, Pierre Delezoide, Henri Fraysse | download
Strona główna Exercices résolus d'algèbre du cours de mathématiques, tome 1
2100014706
9782100014705
Pobierz (djvu, 5.07 MB)
est3622
que3130
donc1641
les1454
dans1276
soit1143
par1081
sont951
nous910
pour tout900
une795
groupe661
sous615
est donc594
qui578
comme572
alors510
voit485
sur429
pas429
matrice422
exercice415
l'ensemble404
est un386
deux374
que pour320
voit que314
la matrice310
il existe307
nous en296
nous en déduisons295
n'est290
nombre287
chapitre278
que pour tout273
l'application265
tous261
cette261
il est251
c'est242
corps233
seulement si224
et seulement si223
tels que218
est pas215
montrer que214
est une212
n'est pas210
l'ensemble des208
et que201
aussi199
entiers198
qu'il198
John Daintith, Derek Gjertsen
Exercices résolus d'algèbre du cours de mathématiques -1 Classes préparatoires 7er cycle universitaire DUNOD
Exercices résolus d'algèbre
Exercices résolus d'algèbre du cours de mathéntatiaues ■ 1 J.M. Arnaudiès P. Delezoide Maître de conférences Professeur de Mathématiques supérieures Université Paris VI au Lycée louis le Grand, Paris H. Fraysse Professeur honoraire de Mathématiques spéciales au lycée Pierre de Fermât, Toulouse Classes préparatoires 1er cycle universitaire DUNOD
Ce pictogramme mérite une explication. Son objet est d'alerter le lecteur sur la menace que représente pour l'avenir de l'écrit, particulièrement dans le domaine de l'édition technique et universitaire, le développement massif du photocopillage. Le Code delà propriété intellectuelle du 1er juillet 1992 interdit en effet expressément la photocopie à usage collectif sans autorisation des ayants droit. Or, cette pratique s'est généralisée dans les établisse- 75006 Paris). ments d'enseignement supérieur, provoquant une baisse brutale des achats de livres et de revues, au point que la possibilité même pour les auteurs de créer des oeuvres nouvelles et de les faire éditer correctement est aujourd'hui menacée. Nous rappelons donc que toute reproduction, partielle ou totale, de la présente publication est interdite sans autorisation du Centre français d'exploitation du droit de copie (CFC, 3 rue Hautefeuille, © Dunod, Paris, 1994 ISBN 2 10 001470 6 Toute représentation ou reproduction, intégrale ou partielle, faite sans le consentement de l'auteur, ou de ses ayants droit, ou ayants cause, est illicite (loi du 11 mars 1957, alinéa 1er de l'article 40). Cette représentation ou reproduction, par quelque procédé que ce soit, constituerait une contrefaçon sanctionnée par les articles 425 et suivants du Code pénal. La loi du 11 mars 1957 n'autorise, aux termes des alinéas 2 et 3 de l'article 41, que les copies ou reproductions strictement réservées à l'usage privé du copiste et non destinées à une utilisation collective d'une part, et d'autre ; part, que les analyses les courtes citations dans un but d'exemple et d'illustration.
To Donald E. Knuth, for his typesetting System T^K
TABLE DES MATIÈRES Introduction CHAPITRE I Vocabulaire de théorie des ensembles 1 § Il Un peu de logique, exercices 1, 2, 7 1 §1.2 Construction d'ensembles, exercices 2,6 2 §1.3 Correspondances et applications, exercices 2, 6, 8 3 §1.4 Familles, exercice 2 4 §1.5 Relations d'équivalence. Ensemble quotient, exercices 5 4, 5, 11 §1.6 Relations d'ordre, exercices 2, 3, 5, 7 7 CHAPITRE II Nombres entiers, nombres rationnels 10 § III Axiomes de Peano ; récurrence, exercices 1, 3, 7, 9 10 §11.2 Ordre naturel dans N , exercices 1, 3, 5 13 §11.3 Ensembles finis, infinis, dénombrables, 17 exercices 1, 4, 5 §11-4 Lois de composition. Structure de groupe, exercices 19 4, 7, 9, 11 §11.5 L'anneau des entiers relatifs, la structure d'anneau, 21 exercices 5, 7, 8, 10, 13 §11.6 Les nombres rationnels, la structure de corps, 25 exercices 4, 5, 9, 13, 17 CHAPITRE III Bases du calcul algébrique et combinatoire 31 § HI.3 Composé de familles à support fini, exercice 1 31 § HI.4 Dénombrement, exercices 2, 4, 5, 8, 9, 13 32 § III.5 Formule du binôme, exercices 6, 7, 10 41 § III.7 Notion d'idéal d'un anneau commutatif, exercices 1, 44 2, 3, 7, 9 CHAPITRE IV Notions d'arithmétique 50 § IV.l Congruences dans Z, anneaux Z/n2 , exercices 2, 3, 50 9, 11, 14, 20, 21
VIII Table des matières § IV.2 Arithmétique dans Z et N, exercices 2, 5, 6, 11, 12, 54 18, 19, 24 § IV.3 Eléments inversibles des anneaux Z/n j , exercices 7, 59 8 § IV.4 Nombres premiers, exercices 2, 4, 8, 11, 12 60 § IV.5 Décomposition en facteurs premiers, exercices 1, 2, 4, 62 8, 11, 14, 20, 21, Numération, exercices 2, 5, 7 CHAPITRE V Groupes 74 § V.l Génération de groupes, exercices 1, 3, 5, 7, 8 74 § V.2 Ordre d'un élément, exercices 1, 3, 4, 5, 6 80 § V.3 Classes suivant un sous-groupe. Indice, exercices 3, 5, 87 6, 8, 9 § V.4 Groupes de permutations, exercices 2, 3, 4, 5, 6, 9, 12, 93 13, 16 § V.5 Cycles dans les groupes ( E fini), exercices 1, 2, 102 3, 7, 10, 12 § V.6 Opération d'un groupe sur un ensemble, exercices 5, 108 6, 11, 12 § V.7 Sous-groupes distingués. Groupe quotient, exercices 115 1, 2, 9, 11, 12, 13, 14 CHAPITRE VI Structure d'espace vectoriel et d'algèbre 125 § VI.1 Structure d'espace vectoriel, exercices 1, 7 125 § VI.2 Applications linéaires, exercices 1, 2, 7 127 § VI.3 Combinaisons linéaires ; indépendance linéaire, exer- 129 cices 2, 5, 7 § VI.5 Le corps des nombres complexes, exercices 7, 10 132 § VI.6 Racines carrées d'un nombre complexe, exercices 6, 9 134 § VI.7 Nombres complexes de module 1, exercices 2, 3, 8, 9 135 § VI.8 Arguments d'un nombre complexe, exercices 11, 12, 138 13, 18, 19 § VI.9 Nombres complexes et géométrie, exercices 4, 5 142 § VI. 10 Nombres complexes et similitudes, exercices 1, 2 145 § VI. 11 Nombres complexes, droites et cercles, exercices 1,2 151 CHAPITRE VII Polynômes sur un corps commutatif 154 § VII. 1 Polynômes à une indéterminée, exercices 4, 5, 6 154 § VII.2 L'anneau euclidien K[X] , exercices 1, 2, 5, 7, 10, 11 156
Table des matières IX § VII.3 L'anneau factoriel K[X], exercices 3, 4, 9, 10 161 § VII.4 Fonctions polynômes, racines, exercices 2, 4, 5, 6, 13, 170 24 § VII.5 Racines d'un polynôme. Formule de Taylor, exercices 177 6, 9, 10, 11, 22, 23 § VII.6 Factorisation dans R[X], exercices 2, 3, 4, 6, 7 193 § VII.7 Congruences dans K[X]. Anneaux quotients, exerci- 202 ces 2, 4, 6 CHAPITRE VIII Fractions rationnelles. Séries formelles 204 § VIII. 1 Le corps K(X), exercices 1, 2, 5, 10, 12 204 § VIII.2 Décomposition en éléments simples, exercices 1, 3, 5, 210 7 § VIII.3 Fonctions rationnelles. Dérivation, exercices 2, 3, 6, 224 7, 9, 12 § VIII.5 Applications des séries formelles, exercices 3, 4, 7,10 237 CHAPITRE IX Espaces vectoriels ; dimension 248 § IX. 1 Sous-espaces supplémentaires, projecteurs, exercices 248 2, 3, 6, 8 § IX.2 Produits et sommes d'espaces vectoriels, exercices 2, 251 4, 6, 7, 10 § IX.3 Espaces de dimension finie, exercices 3, 6, 9 255 § IX.4 Propriétés des espaces de dimension finie, exercices 1, 258 2, 4, 8, 13, 14 § IX.5 Hyperplans, exercice 3 264 § IX.6 Endomorphismes. Groupe linéaire, exercices 1, 2, 3, 266 6, 10 § IX.7 Eléments algébriques d'une extension d'un corps, 270 exercices 6, 7, 13 CHAPITRE X Fonctions polynomiales sur Kn ; équations 283 algébriques § X.l Polynômes à n lettres, exercices 1, 2, 5, 12 283 § X.3 Fonctions symétriques, exercices 7, 1, 3, 9 287 § X.4 Formules de Newton, exercices 1, 4, 5 300 § X.5 Equations algébriques. Equations de degré 3, exerci- 306 ces 1, 6, 8, 14, 19 § X.6 Equations de degré 4, équations particulières, exerci- 314 ces 1, 3, 5, 7, 12, 14
X Table des matières CHAPITRE XI Matrices 323 §XI.l Matrices de type (m, n), exercice 3 323 §XL2 Matrices carrées, exercices 1, 2, 4, 8, 13 324 §XI.3 Matrices et applications linéaires, exercices 1, 3, 5, 8 333 §XL4 Rang d'une matrice, exercices 2, 5, 6, 7 339 §XL5 Opérations élémentaires, exercices 3, 4 343 §XI.6 Similitude d'endomorphismes ou de matrices, 345 exercices 11, 6, 7, 9 CHAPITRE XII Dualité. Espaces vectoriels quotients 352 § XII.l Dual ; forme bilinéaire canonique, exercices 2, 3, 6 352 § XIL2 Dualité en dimension finie, exercices 2, 3, 4, 5, 7, 8 355 § XII.3 Quotients d'espaces vectoriels, exercices 2, 8, 11, 362 16, 17 § XII.4 Quotients, produits et sommes directes, exercice 2 369 CHAPITRE XIII Déterminants 371 § XIII. 1 Applications multilinéaires, exercices 5, 6 371 § XIIL2 Formes n -linéaires alternées sur E de dimension n , 379 exercice 1 § XIII.3 Déterminant de n vecteurs dans une base, exercices 380 § XIII.4 1, o Déterminant d'une matrice carrée, exercices 1, 4 382 § XIII.5 Exemples de déterminants, exercices 5, 6, 7, 9, 17, 20, 385 23, 25, 26 CHAPITRE XIV Equations linéaires sur un corps 411 § XIV. 1 Langage de la géométrie affine, exercice 3 411 § XIV.2 Systèmes de Cramer, exercices 4, 5, 10 411 § XIV.3 Equations linéaires, cas général, exercices 7, 10, 13, 421 14, 16 CHAPITRE XV Réduction d'endomorphismes 432 §XV.l Valeurs propres et polynôme caractéristique, exercices 432 1, 2, 7, 9 § XV.2 Trigonalisation, exercices 2, 8, 9, 11 439 § XV.3 Sous-espaces propres, exercices 1, 2, 3, 4, 5, 11, 13 445 § XV.4 Polynômes d'endomorphismes ou de matrices, 457 exercices 3, 4, 6, 8, 9
Table des matières XI § XV.5 Sous-espaces caractéristiques, exercices 1, 2, 3, 4, 6, 8, 467 9, 12 § XV.6 Suites définies par une relation de récurrence, exerci- 482 ces 2, 9 CHAPITRE XVI Complément : réduction de Jordan 486 § XVI. 1 Etude des endomorphismes nilpotents, exercices 2, 6 486 § XVI.2 Réduction de Jordan quand XU(X) est dissocié, ex- 487 ercices 1, 2, 3 § XVI.3 Sous-espaces monogènes, exercice 1 491 Bibliographie 493
INTRODUCTION Nous présentons ici le deuxième de la série de quatre livres d'exercices corrigés correspondant au Cours de Mathématiques de J. M. Arnaudiès et H. Praysse, un pour chaque tome. Dans ces livres de cours, nous avons sélectionné environ un exercice sur cinq, en variant les niveaux, mais surtout en les choisissant aussi représentatifs que possible. Nous avons aussi donné la réponse à un assez grand nombre des exercices les plus ardus. Toutefois, nous n'avons pas classé les questions par ordre de difficulté, car un tel classement comporterait une trop grande part de subjectivité. Chacun sait que bien souvent, les énigmes sont loin d'être résolues par ceux que l'on attend, et qu'inversement, ce ne sont pas toujours ceux que l'on aurait cru qui "sèchent"... donc, au lecteur d'apprécier le prix de son effort ! Pour chaque exercice, nous avons tenu à donner une solution très développée, en l'ouvrant au maximum sur son environnement mathématique ; car il est bien plus bénéfique à tous égards d'étudier un exercice en relation avec cet environnement que l'exercice pour lui-même, isolément. Le rôle de l'association d'idées en mathématiques est bien connu. Le grand mathématicien Hadamard disait que pour résoudre une question épineuse, après avoir bien "séché" sur elle il faut l'abandonner, puis "penser à côté". Les exercices de mathématiques évoquent l'art des illusionnistes : un spectateur passif pourrait s'extasier toute sa vie devant ces tours de magie sans jamais en percer le secret. De même, un "bachoteur" naïf pourrait lire des centaines d'exercices de mathématiques sans augmenter sa capacité à en résoudre de nouveaux, s'il n'essayait de comprendre un peu ce qui se passe dans les coulisses, c'est-à-dire de bien situer la question dans son environnement. L'idéal serait d'apprendre à en composer de nouveaux, ou même plus simplement à en présenter de connus sous un jour original, qui les rende méconnaissables au spectateur passif... Nous avons voulu la plus grande rigueur dans la rédaction des solutions, au moins autant que pour les livres de cours. Le résultat, nous l'espérons, est un outil de travail de fond, pour les préparations de longue haleine, qui au-delà du souci immédiat de la réussite à tel ou tel concours, préserve le plus large contact avec la science. Il va de soi que nous remercions d'avance ceux de nos lecteurs qui voudront bien nous faire part de leurs remarques et suggestions. Nous remercions vivement les Éditions Dunod, et tout particulièrement Gisèle Maïus, d'avoir entrepris la publication de ces ouvrages, qui s'imposaient pour donner leur pleine efficacité aux quatre livres de cours. Les auteurs
Chapitre I VOCABULAIRE DE THÉORIE DES ENSEMBLES §1.1 UN PEU DE LOGIQUE Exercice 1 : L'implication (3x | Vy,A(x,y)) (Vy, (3x | A(x,y))) est vraie. Etudier l'implication réciproque. Indication : On montrera à l'aide d'un exemple que l'implication réciproque est fausse. ■ Supposons que l'assertion A(x, y) soit (x = y). Dans ce cas l'assertion (3x | Vy, A{x,y)) est fausse (s'il y a au moins deux objets différents). Au contraire, l'assertion (\/y,{3x \ A(x1y))) est vraie: il suffît de prendre y pour valeur de x. L'implication réciproque de l'implication de l'énoncé ne peut donc être vraie. Exercice 2 : Montrer, par disjonction des cas, que l'équation : 5x3 + llt/3 + 13z3 =0, n'admet dans Z3 que la solution (0,0,0). ■ S'il y a une solution (x,y,z) ^ (0,0,0), alors en divisant ces trois nombres par leur pgcd, qui n'est pas nul, on trouve une solution (x', y', z') en nombres premiers entre eux dans leur ensemble. Les nombres x' et y' ne peuvent pas être tous les deux divisibles par 13, sinon z'3 serait divisible par 132 , donc z1 serait divisible par 13 ; il est de même clair qu'ils ne sont ni l'un ni l'autre divisible par 13 . Mais alors comme : 5x/3 + lly'3 = 0 [13] soit 5x'3 = 2y'3 [13], soit encore, puisque —6 est l'inverse de 2 modulo 13, et que —30 = -4 [13], -4x'3=y'3 [13].
2 Chapitre I Vocabulaire de théorie des ensembles Le nombre -4 devrait être un cube modulo 13. Cela est faux comme le montre la table ci-dessous. Nous utiliserons comme ensemble de représentants dans la congruence modulo 13, les entiers entre —6 et +6 . 1 2 3 4 5 6 1 4-4 3-1-3 1-5 1-1 -5 -5 Les cubes non nuls sont donc —5, —1,1,5 ; l'équation 5 x3 +11 t/3 + 13 z3 = 0 , n'admet donc pas de solutions entières non nulles. Exercice 7 : «Montrer qu'il existe une infinité de nombres premiers de la forme An — 1 (resp. 6n — 1 ). ■ Supposons qu'il y ait un nombre fini k de nombres premiers congrus à — 1 modulo 4 ; notons ces nombres pi,P2> • • • iPk • Considérons le nombre n = 4pi x p2 x ... x pk — 1. Ce nombre est > 1 (3 est l'un de ces nombres premiers) ; il n'est divisible par aucun des nombres premiers congrus à —1 modulo 4 et il est impair ; sa décomposition en nombres premiers ne comporte donc que des facteurs qui sont congrus à 1 modulo 4, et il est donc congru à 1 modulo 4, ce qui est évidemment contradictoire. Supposons qu'il y ait un nombre fini k de nombres premiers congrus à — 1 modulo 6 ; notons ces nombres pi,P2> • • • ,Pk • Considérons le nombre n = 6 pi x p2 x ... x pk — 1. Ce nombre est > 1 (5 est l'un de ces nombres premiers ) ; il n'est divisible par aucun des nombres premiers congrus à — 1 modulo 6 et il est impair ; sa décomposition en nombres premiers ne comporte donc que des facteurs qui sont congrus à 1 ou 3 modulo 6 ; comme 32 = 3 [6], il est congru à 1 ou 3 modulo 6 , ce qui est évidemment contradictoire. § 1.2 CONSTRUCTION D'ENSEMBLES Soit Çt un ensemble ; pour toutes parties A, B de Vt, on définit A*B = (ZqA) n (Cn-B) • Montrer que £nA , A U B , An B s'expriment en utilisant le seul symbole * . ■ Exercice 2 :
1.3 Correspondances et applications 3 On vérifie facilement les égalités suivantes : A U B = Crt (Cn(A) n Cn(B)) = (A * S) * 0. An5 = Cn(A) * Cn(B) = * 0) * (B * 0). Exercice 6 : || Montrer que pour tout ensemble E,ona 3P(J5) (jLE .m Considérons l'ensemble -A = {x E E, x $ x}. Soit 4 G 4, mais alors A $ A , ce qui est contradictoire, soit A ^ A , mais alors A $ E ou A G A , la deuxième possibilité étant exclue, nous en déduisons A £ E. L'ensemble A est une partie de E, donc un élément de &(E), qui n'est pas élément de E . L'ensemble ^(E) n'est donc pas inclus dans E. § 1.3 CORRESPONDANCES ET APPLICATIONS Exercice 2 : Soit / : E —> F,g : F —> G, et h : G —> E des applications. On considère les trois applications h o g o f , g o f o h , / o h o g. Montrer que si deux d'entre elles sont injectives (resp. surjectives) et la troisième surjective (resp. injective), alors f,g , et h sont bijectives. ■ Démontrons le lemme suivant : Lemme : Soient E, F, G trois ensembles et / : E —> F , g : F —> G . Si <7 o / est injective, alors / est injective ; si go f est surjective, alors g est surjective. ■ Supposons g o f injective ; si x et y sont éléments de E, et que /(x) = /(y), alors g(f(x)) = g(f(y)) ; comme g o f est injective, nous pouvons en déduire x — y \ l'application / est donc injective. Supposons go f surjective, pour tout élément z de G il existe un élément x de E tel que z = g(f(x)) ; l'application # est donc surjective. Fin du lemme. Une permutation circulaire sur les lettres /,#, h produit une permutation circulaire sur les applications ho g o f, g o f o h , / o ho g . On peut donc
4 Chapitre I Vocabulaire de théorie des ensembles supposer, dans la première hypothèse, que les deux premières sont injectives et que la dernière est surjective. Comme (hog)of est injective, nous pouvons en déduire que / est injective (lemme) ; comme f o (ho g) est surjective, on voit que / est surjective ; l'application / est donc bijective. Comme f o (h o g) est surjective et que / est bijective, ho g est surjective ; donc h est surjective ; comme (go f) oh est injective, h est aussi injective, donc bijective. Les applications f et h étant bijectives, il est alors clair que g est bijective. Supposons maintenant que les deux premières applications sont surjectives et la dernière injective. Comme g o (/ o h) est surjective, nous pouvons en déduire que g est surjective ; comme (f o h) o g est injective, on voit que g est injective ; l'application g est donc bijective. Comme (/ o h) o g est injective et que g est bijective, f o h est injective ; donc h est injective ; comme ho (g o f) est surjective, h est aussi surjective, donc bijective. Les applications g et h étant bijectives, il est alors clair que / est bijective. Exercice 6 : Soit / une application de E dans F, A C E et B C F. Montrer que : f(Anf-1(B)) = f(A)nB. m Il est évident que f(Anf~l(B)) C f(A)C\B . Montrons l'inclusion opposée. Si y G f(A) H B , alors il existe x e A, tel que y = f(x) ; mais comme y G B , par définition x G f~l(B), donc x G A D f~l(B) ; par conséquent, y G f(A fi f~x(B)), ce qu'il fallait démontrer. Exercice 8 : Soit ÇP(E) l'ensemble des parties d'un ensemble E, non vide, A et B deux de ces parties, et / : ^(E) —> 9(E) l'application définie par f(X) = (A H X) U (B D X) où X désigne E \ X . Résoudre et discuter l'équation f(X) = 0. ■ L'ensemble X est solution si, et seulement si, Af)X = 0 et Bn(E\X) = 0. La première condition s'écrit : X C E\ A , la deuxième B C X . L'ensemble des solutions est l'ensemble des parties X de E telles que B C X C E \ A . L'ensemble des solutions n'est pas vide si, et seulement si, B C E \ A, c'est-à-dire A D B = 0 . §1.4 FAMILLES || On appelle recouvrement d'un ensemble F toute famille (Fi)iei Exercice 2 :
1.5 Relations d'équivalence. Ensemble quotient 5 de parties de E telles que: [j Fi = E. Si (Fi)iei et (Gj)jej sont deux recouvrements de E, le second est dit plus fin que le premier ssi (Wj G J) (3z G /) | Gj C F*. Montrer qu'étant donnés deux recouvrements quelconques de E il en existe un troisième plus fin que chacun des deux. ■ Soient (Fi)iej et (Gj)jej deux recouvrements de E. Montrons que la famille (Fi D GjO^e/x J est un recouvrement plus fin que chacun de ces deux recouvrements. C'est un recouvrement : U flnG^UU (FinG^ = U n U Gi (ij)eixj tel jeJ iei \ jeJ = [j (Fi n E) = j (J Fi ) H E = E n E = E. te/ \2€/ / Il est plus fin que les recouvrements (F^)^/ et (Gj)jçj car : V(i,j)eIxJ Fi D G j C Fi et Fi^GjCGj. §1.5 RELATIONS D'ÉQUIVALENCE. ENSEMBLE QUOTIENT. Exercice 4 : Soient E et F deux ensembles non vides, munis respectivement de relations d'équivalence 2ft et if. On définit la relation binaire 2T sur E x F ainsi: (V(x,j/) G F x F), (\/(x',yf) e E x F) (x,y) 2T (x',2/') ssi x 91 x; et y if y'. Montrer que 3" est une relation d'équivalence. Montrer qu'il existe une bijection naturelle de (F x F)/g- sur F/g^ x F/cf . ■ Soient <p : F —► F/g^ et i/> : F —► F/y les projections canoniques sur les quotients. Considérons l'application ^> : F x F —» F/g^ x F/y , définie par <P(x,y) — (<p(x)y ip(y)). On voit que si c et c' sont deux éléments de F x F, c £T c' si, et seulement si, $(c) = #(c') ; il est donc clair que la relation est une relation d'équivalence. Comme l'application ^ est surjective, l'application factorisée 4> est une bijection entre (F x F)/g- et
6 Chapitre I Vocabulaire de théorie des ensembles Exercice 5 : Soit E un ensemble non vide muni d'une relation d'équivalence 91, A une partie non vide de E, et ÇJIa la relation d'équivalence induite par 91 sur A. Condition nécessaire et suffisante pour que l'injection canonique A/giA —► E/cfa soit bijective ? Appliquer à l'exercice 2. ■ L'application est toujours injective, car deux éléments de A sont équivalents pour la relation 91^ si, et seulement si, ils sont équivalents pour la relation 91. Elle est surjective si, et seulement si, toute classe pour la relation 91 a un représentant dans A , c'est-à-dire rencontre A . C'est le cas dans l'exercice 2 : pour tout vecteur x non nul de E, il existe un scalaire À > 0 tel que \x G S. Exercice 11 : Soit E un ensemble non vide et si un ensemble de parties de E. On définit la relation binaire 2ft dans E par : x 91 y ssi \/A G si, {x, y} C A ou {x, y} C E \ A . Montrer que 91 est une relation d'équivalence. Décrire les classes d'équivalence. ■ Notons \a la fonction caractéristique d'une partie A de E . On voit que : (V(x, y)eExE) (x 91 y) (VA G d xa(*) = Xa (</)). Sous cette forme, il est clair que la relation 91 est symétrique, réflexive et transitive ; c'est donc bien une relation d'équivalence. Soit # l'application qui à x élément de E fait correspondre l'application A \-+ xa(x) i si —► {0,1} . On voit que pour tous x et y dans E , x 2ft y si, et seulement si, $(x) = $(y). L'application factorisée # est donc une injection de E/qj^ dans l'ensemble des applications de si à valeurs dans l'ensemble {0,1} . Caractérisons maintenant l'image de #. Soit / G Im (#) = Im ($) , la classe correspondante est {x e E \$(x) = /} , c'est donc aussi {x G E \ (VA G si) Xa(x) — f(A)} ; cette classe est donc l'ensemble des éléments x de E qui appartiennent à toutes les parties A de si telles que /(^4) = 1, et qui n'appartiennent à aucune des parties A telles que f(A) = 0 , c'est l'intersection de f] A et de p| E \ A . f(A) = l f(A)=0 Inversement, si / : si —» {0,1} est telle que l'intersection C de f] A et f(A) = l de p) F \ ^4 est non vide, on voit que C est la classe de chacun de ses f(A)=0 éléments.
1.6 Relations d'ordre 7 Intuitivement, pour définir une classe, on choisit pour chaque élément A de si une valeur f(A) qui est 0 ou 1 ; la classe correspondante est l'intersection des parties A telles que f(A) = 1, et des complémentaires des parties A telles que f(A) = 0 ; il faut évidemment éliminer les fonctions / qui conduiraient à des classes vides. Si si est fini de cardinal n, le nombre de classes est au maximum 2n , et dépend de la configuration des différentes parties A , éléments de si §1.6 RELATIONS D'ORDRE Exercice 2 : Soit E et F deux ensembles ; on considère l'ensemble 3<e,f des couples (X, f) où X C E et où / : X —> F est une application. Si (X,/) G 9e,f et (Y, g) G 9E%F , on écrit (X,/) ■< (Y, g) ssi on a à la fois X C Y et f = g\x . Vérifier que (<Fe,f, ^) est un ensemble ordonné. Quels sont ses éléments maximaux ? ■ On vérifie très facilement les propriétés de réflexivité, antisymétrie et transi- tivité pour la relation -< . On pourrait aussi identifier une application de X , partie de E , à valeurs dans l'ensemble F, à son graphe, partie de E x F . On obtient alors un isomorphisme entre (S^f, ^) et l'ensemble des graphes fonctionnels inclus dans E x F, muni de l'ordre de l'inclusion. Eliminons le cas très particulier où E ou F seraient vides, et montrons que les éléments maximaux de l'ensemble ordonné (<Fe,f<> ^) sont les couples (E, /), où / est une application E —► F . Ce sont des éléments maximaux : Si (E,f) et (Y,g) sont deux éléments de &e,f et que (£,/) ^ (Y,g), alors F C Y, donc F = Y, et comme g\E = /, nécessairement g = f ; donc (E, /) = (y, . L'élément (F, /) est maximal. Ce sont les seuls : Si (X, f) G &e,f et que X est une partie stricte de E, soit x' un élément de E qui n'est pas dans X , et y un élément quelconque de F ; on peut définir sur Xf = X U {x'} , la fonction g par : g(x) = /(x) si x G X , et ^(x;) = 2/. On obtient ainsi un couple (X*,g) élément de 3Fe,f qui majore strictement (X, /) pour la relation d'ordre •< . Le couple (X, /) n'est donc pas maximal. Dans l'exercice précédent on prend E = F — C. On note $ le sous-ensemble de SFc.c formé des (X, /) tels que / soit rationnelle, c'est-à-dire telle qu'il existe ip G C(X) pour laquelle X Exercice 3 :
8 Chapitre I Vocabulaire de théorie des ensembles Ine contient aucun pôle de <p et cp\x = f • Trouver les éléments maximaux de l'ensemble ordonné ^). ■ Notons D((p) le complémentaire de l'ensemble des pôles de la fraction rationnelle (p (<f e C(X) ). Nous allons démontrer que les éléments maximaux de ^ sont les couples (D((p),p), où (p est un élément de C(X) qu'on identifie à une fonction de domaine D(ip). Supposons que le couple (X, /) soit maximal dans # ; il existe une fraction rationnelle (p telle que X C D(ip) et / = y>\x ; comme le couple (D(ip),ip) majore (X,/) et que (X,/) est supposé maximal, les deux couples sont égaux. Supposons maintenant que i/j soit une fraction rationnelle et que ^ (X,/) ; il existe une fraction rationnelle (p telle que X C D(ip) et / = <p\x ; les deux fractions rationnelles (p et t/> coïncident sur la partie infinie D(ijj) donc sont identiques ; comme D(i/j) C X C D((p), nous pouvons en déduire que X = D(ip) et f = tp (considérée comme fonction de domaine D(^) ). Le couple (D(ip),ip) est donc maximal. Exercice 5 : Des hussards de tailles variées sont disposés en rectangle. On repère le plus grand de chaque rangée et l'on retient le plus petit de ces plus grands, soit X. Puis on repère le plus petit de chaque colonne et on retient le plus grand de ces plus petits, soit Y . comparer les tailles de X et de Y . ■ Soit Z le hussard qui est sur la même rangée que X et sur la même colonne que Y . La taille du hussard Z est inférieure (ou égale) à celle de X , puisque X est le plus grand de sa rangée ; mais le hussard Z est de taille supérieure (ou égale) à celle du hussard Y , qui est le plus petit de sa colonne ; nous en déduisons que le hussard X est plus grand que le hussard Y . On peut aussi formaliser ce résultat de la manière suivante. Soient E et F des ensembles non vides et / : E x F —► G une application, l'ensemble G étant fini et muni d'un ordre total ^ . Toute partie non vide A de G a donc un plus petit élément que nous noterons min (A) et un plus grand élément que nous noterons max (A). Nous pouvons alors écrire : (Vu G F, Vu G F) max/(x,u) ^ f(u,y). X D'où: (Vu G E) min(max/(x, y)) ^ min/(u, u), y x y donc : min(max/(x,u)) ^ max(min/(u,u)). y x u y
1.6 Relations d'ordre 9 La variable u étant muette, nous obtenons le résultat attendu : min(max/(x,y)) ^ max(min/(x, y)). y x x y Exercice 7 : On munit (Rn (où n ^ 1 ) de V ordre produit relatif à Tordre usuel de U. (Par définition, si x = (xi,X2,... ,xn) et y = (yi, V2, • • • > Un) appartiennent à Un , on a donc x <y ssi (Vi G {l,...,n}) Xi ^ yi). Soit B le sous-ensemble ordonné de (Rn, ■<) défini par : B={(xux2,...,xn)enn | x2+x| + ...+x2 ^ 1} . Etudier les éléments maximaux de B . ■ Montrons que l'ensemble des éléments maximaux de B est l'ensemble : M = {(xi,x2,...,xn) G Rn | x? + ...+x2 = 1 et (Vi G {1,2,...,n} X* ^ 0) } . Soit x = (xi,X2,... ,xn) un élément de B. Supposons qu'il existe j G [l,n] , tel que Xj < 0, alors le n-uplet x' = (xi,... ,£j_i,0,£j+i,... ,xn) est un élément de B qui majore strictement x pour la relation ^ ; le n- uplet x n'est donc pas maximal. Supposons maintenant que x\ 4- x\ 4- ... 4 x2 < 1 ; posons xi = <y/l - (x| 4-... -f x2), on voit que le n-uplet x' — (x'x,X2,... ,xn) est un élément de B qui majore strictement x pour l'ordre -< ; le n-uplet x n'est donc pas maximal. L'ensemble des éléments maximaux de B est donc inclus dans M. Soit maintenant un n-uplet x = (xi,X2,... ,xn) élément de l'ensemble M . Si le n-uplet y = (j/i, y2,..., 2/n) » élément de JB , majore x , alors pour tout i G [1, n] , 0 ^ Xi ^ yi, donc y? ^ x? ; comme y? -f- y\ 4-... 4- y2n ^ 1 = x\ 4 x2 4 ... 4 x2 , on voit que pour tout i G [l,n] , y\ = x2 ; comme d'autre part pour tout i, 0 ^ Xi ^ y* , nous pouvons en déduire x = y. Le n-uplet x est donc maximal. L'ensemble des éléments maximaux de B est donc bien M .
Chapitre II NOMBRES ENTIERS, NOMBRES RATIONNELS § II. 1 AXIOMES DE PEANO; RÉCURRENCE Exercice 1 : Démontrer en détail le corollaire du théorème II. 1.2 : Soit % et 8F deux ensembles non vides, g : 2F —> 3* et tp : % —» 2F deux applications. Il existe une, et une seule, application (p: % x N -* 9 vérifiant : (I) (VeG^S) ¥>(e,0)=tf(e) (II) (Ve G %, Vn G N) <p(e, 5(n)) = #(</?(e, n)). ■ Soit 9 l'application de (#*)N dans 3*xN définie par : (V* G (**)N Vn G N Ve G «) 0(*)(e, n) = *(n)(e). Il est clair qu'il s'agit d'une bijection dont la réciproque est l'application r définie par : (Vmg3^xN Vn G N VeG^) r{u)(n)(e) = u(c,n). Soit maintenant l'application G : SF* —> SF* définie par : (V/e**) G(f)=gof. En utilisant le théorème II. 1.2 en remplaçant "S par 2F*8 et g par G, on prouve l'existence (et l'unicité) d'une application 3> : M —» 2F<ig telle que : (/) *(o) = V (JJ) (Vn € N) #(5(n)) = G(#(n)) =50 *(n). Ces propriétés s'écrivent aussi : (") (Vee«) #(0)(e) = V(e) (Vn e N Ve € «) *(S(n))(c) = $(*(n)(e)).
II.l Axiomes de Peano ; récurrence 11 L'application ip = ©(#) vérifie donc : (I) (II) (VeG<g) cp(e,0) = */j(e) (Vee% Vn G N) <p(e,S(n)) = g(tp(e,n)). Il est clair que c'est la seule application qui convienne. Exercice 3 : On appelle chaîne simple tout triplet % = (a,%, f) où % est un ensemble, a un élément de %, et / : % —> % une application vérifiant (Ci) a £ f(%) ; (C2) / est injective; (C3) la seule partie E de % telle que a G % et (Vx G «) (x G £) =^ (/(x) G F) est E = % . a) Montrer que si ^ = (a,^, /) est une chaîne simple, on a : b) Montrer que si °ê = (a,%,f) est une chaîne simple, si 2F est un ensemble non vide, b un élément de 2F, et g : 2F —► 2F une application, alors il existe une, et une seule, application ip : % —► 2F telle que (£>(a) = bet(pof = go(p [ s'inspirer de la preuve du théorème II. 1.2 ]. c) Montrer que si % — (a,%,f) est une chaîne simple, il existe une, et une seule, application (p : N —► % , telle que ip(0) = a et ip(n + 1) = f((p(n)) pour tout n G f^l, et montrer que cette application c/? est bijective. ■ a) Le théorème II. 1.2 nous permet d'affirmer l'existence et l'unicité d'une application ip : N —> % telle que : L'ensemble ip(N) est stable par l'application / et contient a, c'est donc l'ensemble % . L'application (p est donc surjective. De plus : = {a} U <p(S(\)) = {a} U /(V(N)) = {a} U /(*). 6) D'après ce qui précède, si le triplet (a,^,/) est une chaîne simple, il vérifie les axiomes de Peano. Tous les résultats démontrés pour le triplet (0, S) sont aussi vrais pour le triplet (a,^8, /) ; en particulier le théorème II. 1.2 qui peut s'énoncer sous la forme : « = {a}U/(«). (I) (II) ip(0) = a (Vn G N) <p{S(n)) = f{fp{n)).
12 Chapitre II Nombres entiers, nombres rationnels Théorème : Soit 3F un ensemble non vide, 6 G 3F, et g : 3F —> 3F une application. Il existe une application, et une seule, ijj : % —> 3F telle que : ^(a) = 6 et ipo f = goij; .m Ce qui est le résultat demandé. c) L'existence et l'unicité de l'application tp utilisée dans le a) se déduisent facilement du théorème II. 1.2. On peut utiliser le résultat du b) avec SF = f^J et g = S, 6 = 0. Il existe donc une unique application ip : % —► N telle que ^(a) = 0 et (Ve G %) ip(f(e)) = S(^(e)). Montrons que ip et ip sont réciproques l'une de l'autre, et donc bijectives. On vérifie que : ip((p(0)) = 0 et (^ o (p) o S = r/j o / o ip = S o (xjj o <p). Par unicité nous en déduisons que ip o cp = Id^ . De même : ip(ijj(a)) — a et ((poijj)of = (poSoip = fo(<ipoip). Par unicité nous en déduisons que ip o -0 = Id$ . Exercice 7 : Montrer que Vra G N*, Vn G N*, Vr G N, ra2r+1 + n2r+1 est divisible par m + n . ■ Le résultat est évident si r = 0 ; nous supposerons dans la suite r > 0. On peut écrire : m2r+1 -f n2r+1 = m2r+1 — (—n)2r+1 ; d'après une identité algébrique bien connue : m2r+l+n2r+l = =(m + n)(m2r - m^n + m2r"2n2 - ... + m2n2r"2 - mn2^1 -f n2r) . Cela prouve bien le résultat demandé. Exercice 9 : Pour quels nombres complexes a peut-on définir une suite (un) de nombres complexes telle que : u0 = a et ( Vn G N) un+i = 1 + — ? ■ Soit oo un élément qui n'est pas dans C . Définissons sur C U {oo} l'application h par : h(0) = oo, ft(oo) = 1, (VzgC\{0}) h{z) = 1 + - .
11.2 Ordre naturel dans N 13 Il est clair que l'application h est une bijection de C U {00} vers C U {00} . Pour tout complexe a, il existe une et une seule suite (un) d'éléments de C U {00} telle que uo = a et (Vn G N) un+i = h(un). On peut aussi écrire: (Vn G N) un = hn(a). On voit qu'on peut définir une suite de complexes vérifiant les conditions de l'énoncé si, et seulement si, pour tout n entier n > 0, hn(a) ^ 00. Comme l'application h est bijective, cette condition s'écrit : (Vn G N*) h~n(oo). On vérifie facilement que ft-1(oo) = 0, h~2(oo) = —1, h~3(oo) = —1/2 etc. Montrons que pour tout entier n, n > 0, h~n(oo) = —an_i/an , où (an) est la suite de Fibonacci, définie par les conditions : ao = 0, a\ = 1 et (Vp G N) ap+2 = ap+i + ap (on peut remarquer qu'il s'agit d'une suite d'entiers tous strictement positifs, sauf ao ). C'est vrai pour n = 1, et si c'est vrai pour n > 0, alors : = /rn(oo), donc : l'égalité est donc vraie pour tout entier n, n > 0. L'ensemble des nombres complexes vérifiant les conditions de l'énoncé est donc l'ensemble : C \ {—(an_i/an), n G N*} . §11.2 ORDRE NATUREL DANS N Exercice 1 : Soit (F, ^) un ensemble totalement ordonné non vide tel que (I) (E, ^) est bien ordonné ; (II) E n'a pas de plus grand élément ; (III) toute partie de E non vide et majorée admet un plus grand élément . Montrer qu'il existe une, et une seule, bijection croissante xp de (N, =s=) sur (E, ^). ■ Montrons qu'un ensemble bien ordonné (F, ^) n'a pas d'automorphismes autres que l'identité. En effet si / était une bijection strictement croissante de (F, ^) vers (F, ^), de réciproque strictement croissante, et différente de l'identité, l'ensemble D = {x G E, f(x) ^ x} ne serait pas vide et aurait un plus petit élément m. Si on suppose /(m) < m , alors f(f(m)) = f(m), d'où /(m) = m, il y a contradiction. Si on suppose /(m) > m, alors m > f~l{m), donc f(f~1(m)) = /-1(m), c'est-à-dire m = f~l{m), ce qui est la même contradiction.
14 Chapitre II Nombres entiers, nombres rationnels Il est alors clair qu'il ne peut exister entre deux ensembles bien ordonnés qu'au plus un isomorphisme, car si f\ et f2 sont deux isomorphismes, f\ o f2~l est un automorphisme de l'un des ensembles bien ordonnés, et est donc égal à l'identité de cet ensemble. Dans le problème posé ici, les deux ensembles sont bien ordonnés, donc totalement ordonnés et par conséquent toute bijection croissante de l'un vers l'autre est un isomorphisme d'ensembles ordonnés. Le lecteur évitera d'étendre indûment ce résultat. Par exemple on peut numéroter les parties d'un ensemble fini E de cardinal n, de telle sorte que l'application ainsi obtenue, de (E) muni de l'ordre de l'inclusion vers l'intervalle des entiers [1,2n] muni de son ordre naturel, soit bijective croissante ; il suffit de numéroter la partie vide, puis les singletons, les paires etc., et terminer par l'ensemble entier; cette bijection croissante n'est évidemment pas un isomorphisme d'ensembles ordonnés. Montrons maintenant l'existence de cet isomorphisme. Soit if l'ensemble des parties non vides de E qui n'ont pas de plus grand élément ; cet ensemble n'est pas vide puisque E G if. Soit (p : if —► if, A h-+ A \ {Min (A)}. L'élément Min (A) existe puisque l'ensemble E est bien ordonné et que la partie A n'est pas vide; la partie A \ {Min(A)} , n'est pas vide, sinon on aurait A = {Min (A)} et A aurait un plus grand élément, et elle n'a pas de plus grand élément, sinon la partie A aurait le même plus grand élément. On a donc bien défini une application de if vers if. Posons pour n entier En = <pn(E), (E0 = E), et %p(ri) = Mm{En). Montrons que l'application ip est une bijection croissante entre (N, ^) et (E,^) , donc un isomorphisme entre ces deux ensembles ordonnés. Comme pour tout entier n , Un+i C En , nous pouvons en déduire que pour tout entier n, ip(n -f 1) = Min(Fn+i) ^ ip(n) = Min(Fn), et il n'y a pas égalité car Min(i£n) ^ Fn+i . L'application xf) est donc strictement croissante. Montrons maintenant que l'application tp est surjective. Comme l'ensemble Im (ip) = {ip(n), n€ N} n'admet pas de plus grand élément (puisque ip(n) est majoré strictement par ^(n + 1) ), il n'est pas majoré. Soit x un élément de E, ce n'est pas un majorant de Im (ip), il existe donc un entier N tel que x < ip(N), donc x £ E^ ; l'ensemble des entiers n tels que x G En n'est pas vide car x G Eo = E , et est majoré par N , puisque la suite (En) est décroissante pour l'inclusion, cet ensemble a donc un plus grand élément p ; mais alors x G Ep et x £ Fp+i , comme Ep+\ = Ep\ {ip(p)} , nous pouvons en déduire x = ip(p). L'application ip est donc surjective. Nous avons bien établi que l'application ip était un isomorphisme d'ensembles ordonnés. a) Soit (E, ^) un ensemble bien ordonné non vide sans plus grand élément. Montrer que l'application S : E —» E, x »-> Exercice 3 :
11.2 Ordre naturel dans N 15 Min ({y G E | y > x}) est bien définie (c'est l'application successeur ). Si 0 désigne le plus petit élément de F, montrer qu'en général Im (S) ^ E \ {0} (cf. exercice 2) . b) On note E' — (E\ {0}) \ Im(5). En remarquant que tout sous-ensemble ordonné d'un ensemble bien ordonné est bien ordonné, étudier si on peut définir E", = (E^"1))', pour k G . c) Donner un exemple d'ensemble bien ordonné E tel que tous les E^ soient définis pour k eN* .m a) Soit x G E , comme x n'est pas le plus grand élément de E , l'ensemble {y e E, y > x} n'est pas vide et a donc un plus petit élément, c'est le successeur de x , S(x). Soit (un) la suite vérifiant les conditions uq = 0e et (Vn G N) un+i = S(un). Cette suite est strictement croissante et donc injective. Montrons que si Im(5) = E\ {0e} , la suite (un) est surjective; nous pourrons en déduire que dans ce cas les ensembles bien ordonnés (N, ^) et (E, ^) sont isomorphes. Si on suppose que la suite (un) n'est pas surjective, soit a le plus petit élément de E qui n'est pas l'un des termes de cette suite ; ce n'est pas 0e car u0 = 0e , et comme nous supposons Im(5) = E \ {0e} , l'élément a a un prédécesseur b , c'est-à-dire a = S(b) ; l'élément b est l'un des termes de la suite : 3n G M | b = un , donc a = S(un) = un+\ , l'élément a est donc l'un des termes de la suite, ce qui est contradictoire. L'égalité : Im (S) = E\{0e} n'est donc vraie que dans le cas où les ensembles ordonnés (M, et (F, ^) sont isomorphes, ce qui n'est pas le cas général. b) On peut définir l'ensemble E" si l'ensemble E' est non vide et n'a pas de plus grand élément ; de même pour les ensembles suivants. Etudions le problème dans l'exemple ci-dessous. Munissons l'ensemble N x N de l'ordre lexicographique, c'est-à-dire posons (n, m) =^ (n',mf) si n < nf, ou n = n' et m ^ m'. On vérifie facilement qu'on définit ainsi un ordre total sur l'ensemble NxN. Montrons que c'est un bon ordre. Soit A une partie non vide de M x f^J. Considérons l'ensemble {n G N | 3m G (n, m) e A} ; c'est une partie non vide de f^J puisque A n'est pas vide, et elle a donc un plus petit élément no ; l'ensemble {m G M | (no, m) G A} n'est alors pas vide et a donc un plus petit élément rao ; le couple (no,mo) est le plus petit élément de A, en effet, c'est un élément de A, et si (n,m) est élément de A, alors no ^ n et si no = n , alors mo ^ m . Toute partie non vide A de f^J x f^J a donc un plus petit élément ; l'ensemble NxN est donc bien ordonné par cet ordre
16 Chapitre II Nombres entiers, nombres rationnels lexicographique. Il est clair que le successeur du couple (n, m) est le couple (n, m -f 1) ; par conséquent les éléments qui n'ont pas de prédécesseurs sont les couples de la forme (n,0). Le plus petit élément de l'ensemble est le couple (0,0) ; l'ensemble Ef est donc ici l'ensemble des couples (n, 0) où n G N* , c'est un ensemble ordonné isomorphe à (N,^). On peut donc définir l'ensemble E" , mais il est vide. L'exercice 2 donne d'autres exemples d'ensembles bien ordonnés. On peut aussi étudier l'ordre lexicographique sur Np, où p G N* , qui est un bon ordre. c) Soit E l'ensemble des polynômes non nuls à coefficients entiers ^ 0 ; si P et Q sont des éléments de E, nous dirons que P ^ Q si, et seulement si, P = Q ou si le coefficient dominant du polynôme Q — P est > 0. On vérifie facilement qu'on définit ainsi un ordre total ; cela tient principalement au fait que l'ensemble des polynômes, nul ou de coefficient dominant ^ 0, est stable par l'addition. Observons que si P et Q sont deux éléments de E et que deg (P) < deg (Q), alors P < Q . Montrons qu'il s'agit d'un bon ordre. Soit A une partie non vide de E . L'ensemble D des degrés des polynômes éléments de A est une partie non vide de N et a donc un plus petit élément d. L'ensemble Ai = {P G A | deg (P) = d} n'est pas vide et d'après la remarque ci-dessus, si l'ensemble Ai a un plus petit élément, c'est aussi le plus petit élément de A. On obtiendra le plus petit élément de Ai en prenant le polynôme élément de Ai dont le coefficient de puissance d est (non nul) le plus petit possible, puis, ce coefficient étant fixé, le coefficient de puissance d — 1 le plus petit possible etc., jusqu'au coefficient de puissance 0. Le plus petit élément de E est le polynôme constant 1. On vérifie facilement que le successeur d'un polynôme non nul P est le polynôme P +1. L'image de la fonction successeur est donc l'ensemble des éléments de E différents de 1, dont la valeur en 0 est > 0. L'ensemble E' est donc ici l'ensemble des éléments P de E tels que P(0) = 0 , c'est-à-dire l'ensemble des polynômes non nuls à coefficients entiers ^ 0 , qui sont divisibles par X . Il est clair que l'ensemble ordonné E' est ici isomorphe à l'ensemble ordonné E ; on peut donc définir les ensembles E^ pour tout entier A:, k > 0, et ils sont tous isomorphes entre eux. Exercice 5 : Soit / : —► N* une application qui vérifie la propriété (Vn G N*) /(n + 1) > /(/(n)). Montrer que (Vn G N*) f(n) = n. [Olympiades 1977.] m Montrons d'abord par récurrence sur l'entier p que : (Vn > p) f(n)>p.
IL3 Ensembles finis, infinis, dénombrables 17 La propriété est vraie si p = 0 puisque l'application / est à valeurs dans N* . Supposons que la propriété soit vraie pour p. Si n > p -f 1, alors n - 1 > p, donc /(n - 1) > p et f(f(n - 1)) > p (récurrence) ; nous déduisons alors de l'hypothèse: /(n) = /(n — 1 -h 1) > /(/(n — 1)) > p, donc f(n) > p + 1. La propriété est donc vraie pour p + 1. Cette propriété est donc vraie pour tout entier p. En particulier nous en déduisons: (Vn G N*) /(n) > n — 1, soit encore f(n) ^ n ; d'où (Vn G N*) /(n + 1) > /(/(n)) ^ /(n) ; l'application / est donc strictement croissante et comme (Vn G N*) /(n H- 1) > /(/(n)), on en déduit que (Vn G N*) n -f- 1 > /(n) ; pour terminer (Vn G N*) n -h 1 > /(n) ^ n, soit /(n) = n, ce qu'il fallait démontrer. § II.3 ENSEMBLES FINIS, ENSEMBLES INFINIS; ENSEMBLES DÉNOMBRABLES Exercice 1 : Montrer que, pour qu'un ensemble E soit fini, il faut et il suffit que toute partie non vide de (E) possède un élément maximal pour l'inclusion. ■ Si E est fini et P C ?P(E), un élément de P de cardinal maximum est maximal dans P , pour l'ordre de l'inclusion. Supposons que toute partie non vide de (E) possède un élément maximal pour l'inclusion. C'est vrai en particulier pour l'ensemble F des parties finies de E (F n'est pas vide, car 0 est fini ) ; il existe donc une partie finie A de E , maximale pour l'ordre de l'inclusion parmi les parties finies de E. Si x est un élément quelconque de E la partie A U {x} est finie et contient A, par conséquent c'est A et x G A. Donc A — E et E est fini. Exercice 4 : d) Z = N U Z_ est évidemment dénombrable. Construire une bijection explicite de Z sur N. b) Soit (pn)n€N* la suite croissante des nombres premiers dans N* (pi = 2,p2 = 3,etc.). On note / l'ensemble N<N*> des suites (an)n€N* d'éléments de N, à support fini , c'est-à-dire telles que l'ensemble {n G N* | an ^ 0} soit fini. De même on note J l'ensemble des suites (an)n€^j* d'éléments de Z à support fini. On démontrera au chapitre sur les nombres premiers que l'application (p : I —► N* , (an)n^i h-> Yl Pnn est bijective. De même, l'application ip : J —» Q* , (an)n^i i-> p£n est
18 Chapitre II Nombres entiers, nombres rationnels bijective. En déduire une bijection explicite de N* sur Q* , à l'aide du a). c) Construire une bijection explicite de N sur Q . ■ a) Posons f(n) = —2n si n est entier relatif ^ 0 et f(n) = 2n — 1 si n est entier > 0. On voit que / induit une bijection entre Z_ et l'ensemble des entiers naturels pairs, et une bijection entre et l'ensemble des entiers naturels impairs. C'est donc une bijection entre Z = Z_UN* et N . b) Remarquons que /(O) = 0 , et que par conséquent si la suite (an)n5si est élément de J, la suite (/(an))n2si est élément de J. Soit # l'application de J dans J définie par # ((an)n5si) = (/(û:n))n5sl ; il est clair que cette application est une bijection de J sur J . L'application 6 = ip o o ip~l est donc une bijection de N* sur . c) Définissons l'application G de Z vers Q de la manière suivante : 6(n) = -e(-n) si n < 0, 9(0) = 0, et 9(n) = 0(n) si n > 0. L'application 9 induit une bijection entre N!_ et Q*_ et induit aussi une bijection entre et Q+ ; comme de plus 9(0) = 0, il est clair que l'application 9 est une bijection. L'application 9 o/-1 est alors une bijection de N vers Q. Exercice 5 : Utiliser les théorèmes II.3.8 et II.3.10 pour prouver: si E est une ensemble infini et si a G E , alors E \ {a} est équipotent à E . Construire une bijection explicite de [0,1] sur [0,1[. ■ Si A et B sont des ensembles disjoints, leur union sera notée ici A U B . L'ensemble E \{a} étant infini, il existe une injection (p : N —> E\{a] . Notons F = (E\ {a}) \ ip(N). Nous pouvons écrire : E\'{a} = FU(p(N) et E = F U {a} U <p(N). L'ensemble </?(N) est équipotent à N et donc à N* ; l'ensemble {a}l_l</?(N) est par conséquent équipotent à {0} U N* = N . Les deux ensembles </?(N) et {a} U </>(N) sont donc équipotents entre eux, et à l'ensemble N . Les ensembles E et E \ {a} sont donc équipotents. Il suffit dans le cas particulier d'appliquer la méthode générale avec une injection explicite ip : N —> [0,1[. Prenons par exemple ip(n) = l/(n 4- 2). On obtient une bijection de 6 : [0,1] —► [0,1[ en posant: 6(x) = x si
II.4 Lois de composition. Structure de groupe 19 x G [0,1] et x n'est pas l'inverse d'un entier, et si x — 1/n, n entier > 0, 6(x) = l/(n + l). § II.4 LOIS DE COMPOSITION . STRUCTURE DE GROUPE Exercice 4 : Soit n et p G N* , n ^ p. Démontrer que les monoïdes (Nn, +) et (Np,+) ne sont pas isomorphes. Montrer également que (Nn, +) et (N*, x) ne sont pas isomorphes. ■ Pour p entier > 0 donné, notons 9lp la relation binaire sur Np définie par : (xi, x2,. •., xp) 2ftp (2/1,2/2» • • • > Dp) si, et seulement si, pour tout i dans , Xi et 2/i ont la même parité. Il est clair qu'il s'agit d'une relation d'équivalence. L'ensemble quotient a 2P éléments, nous le noterons Ep . Supposons que # soit un isomorphisme de monoïde entre (Nn,+) et (Np,+). Si (#i, #2,..., #n) e^ (yVi-> - • • > Un) sont deux éléments de Nn équivalents pour la relation 9ln , alors pour tout i dans [l,nj l'entier Xi + yi est pair, notons le 2 ^ . Nous pouvons alors écrire : #((xi,X2,...,Xn)) +#((2/l,î/2,...,2/n)) = = *((xi +yi,x2 + y2,...,a:nH-î/n)) = = *((2*i, 2*2, • •., 2zn)) = 2#((zi, z*,..., zn)) ; cet élément de Np est donc un p-uplet constitué de nombres pairs. Notons #((xi,x2,...,xn)) = (ai,a2,...,ap) et #((2/1,2/2,... ,2/n)) = (&i,&2,. • •, bp) ; nous avons montré que pour tout j dans , Q>j+bj est pair, donc aj et 6j ont la même parité. Les p-uplets (ai, 02,..., ap) et (61,62,..., bp) sont donc équivalents pour la relation 2&p . On peut donc définir une application de l'ensemble quotient En vers l'ensemble quotient Ep qui est surjective puisque # l'est. Nous en déduisons 2n ^ 2P. On démontrerait de manière analogue 2P ^ 2n en utilisant l'isomorphisme <P~l . Les monoïdes (Nn,+) et (Np,+) ne sont donc isomorphes que si n = p. Soit Si le n-uplet dont toutes les composantes sont nulles, sauf celle d'indice i qui vaut 1. Soit, s'il en existe, (p un homomorphisme de (Nn,+) vers (N*, x) ; posons pour tout i dans , ki = (p(ei). On voit facilement que : (V(ai, a2,..., On) G Nn) <p((ai, a2,..., an)) = fc?1 k? ... . On peut alors prouver de multiples façons que cp ne peut pas être surjective. Par exemple un entier différent de 1 qui n'est divisible par aucun des nombres fci, /c2,..., kn (c'est le cas de l'entier fcifc2 ... kn + 1 ) ne peut être dans
20 Chapitre II Nombres entiers, nombres rationnels l'image. Il ne peut donc pas exister d'homomorphisme surjectif du monoïde (Nn, -f) vers le monoïde (N*, x) ; a fortiori pas d'isomorphisme. Exercice 7 : || Montrer qu'un monoïde fini et régulier est un groupe. ■ Notons (M, ★) le monoïde, et e son élément neutre. Pour un élément x de M donné, l'application M—►M, y m x^y est par hypothèse injective . Comme l'ensemble M est fini, cette application est aussi surjective. Nous pouvons en déduire en particulier que l'élément x a un inverse à droite x'd . De même cet élément a un inverse à gauche que nous noterons x'g . Ces deux inverses sont nécessairement identiques, en effet : (Xg * x) * x^ = e * Xj = Xj = Xg ★ (x ★ x'd) = Xg ★ e = Xg . Tout élément x de M est donc inversible. Le monoïde (M, ★) est donc un groupe. N.B. : si (M, ★) est un ensemble fini non vide muni d'une loi de composition associative et régulière, alors (M, ★) possède un élément neutre (c'est donc, d'après ce qui précède, un groupe). En effet, soit x un élément de M (qui est non vide), l'application y y ★ x de M vers M est injective, donc surjective ; il existe donc un élément e dans M tel que e*x = x ; pour tout élément y de M, y*e*x = y*x , d'où par régularité de la loi, y*e = y ; en particulier x ★ e = x , donc pour tout y dans M, x* e*y = x*y ; nous en déduisons que pour tout y dans M, e*y = y. L'élément e de M est donc l'élément neutre bilatère de (M, ★). Exercice 9 : Si G est un groupe et si i G Z, l'application fk : G —► G, xhx^ est-elle un homomorphisme de groupes ? ■ Nous noterons ★ la loi du groupe G. Si l'entier k est 0 ou 1, l'application fk est évidemment un homomorphisme de groupes. Dans le cas général, c'est homomorphisme de groupes si, et seulement si : (V(x,y)€GxG) XV = (*!,)*• Cette condition est réalisée si le groupe G est abélien. Pour k = 2 la condition s'écrit : (V(x,y) G G x G) x*x*y*y = x*y*x*y.
II.5 L'anneau des entiers relatifs, la structure d'anneau 21 En simplifiant nous obtenons : (V(x,y) eG x G) x*y = y*x. L'application fi est donc un homomorphisme de groupes si, et seulement si, le groupe est abélien. Pour k = -1 la condition s'écrit : (V(x, y) e G x G) x-1 * y-1 = (x ★ y)~l = y-1 * x'1 . Il est donc clair que /_i est un homomorphisme de groupes si, et seulement si, le groupe est abélien. Exercice 11 : 4 Soit G un groupe. On suppose qu'il existe k e N* tel que, pour tous aeG et beG : (ab)1 = pour i e {k - 1, fc, k + 1} . Démontrer que G est abélien. ■ Pour k = 1 la seule condition est (V(a, 6) G GxG) {ab)2 = o?b2 . Nous avons déjà vu dans la résolution de l'exercice 9 que cette condition est réalisée si, et seulement si, le groupe est abélien. Nous supposerons dans la suite k > 1. Si a et b sont des éléments quelconques de G, comme ak~1bk~l = (ab)k~l , et (ab)k — akbk , nous en déduisons : akbk = (ab)k = {ab)k~lab = ak~lbk-lab, donc en simplifiant à gauche par ak~l et à droite par 6, nous obtenons abh~l = bk~la. En remplaçant dans le raisonnement ci-dessus k par k + 1, nous obtenons de manière analogue abk = bka ; donc a6fc = bbk~la = babk~l , soit encore abbk~l = babk~l ; en simplifiant par bk~l à droite, nous obtenons finalement ab = ba . Le groupe G est donc abélien. §11.5 L'ANNEAU DES ENTIERS RELATIFS, LA STRUCTURE D'ANNEAU Exercice 5 : Pour n E N* trouver les homomorphismes d'anneaux de Zn dans Z. ■ Pour i dans [l,nj notons Si le n-uplet élément de Zn dont toutes les composantes sont 0 , sauf celle d'indice i qui vaut 1 ; la multiplication dans
22 Chapitre II Nombres entiers, nombres rationnels Zn est telle que e^x^ = , et si j est un indice différent de i, ^x^- =0. Soit y? : Zn —► Z un homomorphisme d'anneau ; posons pour tout 2 dans [l,n| , ip(£i) — • Nous pouvons déduire de ce qui précède que pour tout i dans [l,n] , k2 = ki, donc fc* = 0, ou ki = 1, et si j est un indice différent de i, = 0. On voit alors que soit tous les nombres ki sont nuls, soit un seul d'entre eux n'est pas nul, et vaut 1. D'autre part : n V(ai,a2,... ,an) G Zn (ai, a2,..., an) = - e». 2=1 Comme y? est un homomorphisme pour l'addition, on voit que : n n V(ai,a2,... ,an) G Zn <p((ai,a2,... ,an)) = • </>(£*) = ^a* • fc». i=l i=l Il est impossible que tous les nombres ki soient nuls, car l'application ip serait nulle, ce qui contredit <£>((1,1,..., 1)) = 1 ; donc un et un seul des ki n'est pas nul et vaut 1. L'homomorphisme <p : Zn —► Z est donc nécessairement la projection sur l'une des composantes. Ces n applications étant bien des homomorphismes d'anneaux, ce sont les homomorphismes d'anneaux de Zn dans Z. Exercice 7 : Dans un anneau A, on suppose (Vx G A) x2 = x . Montrer que A est commutatif. Si A contient au moins 3 éléments distincts montrer qu'il a nécessairement des diviseurs de zéro. Montrer qu'en fait A ne peut avoir exactement 3 éléments. Nota : A est appelé un anneau de Boole. m Soit n un entier relatif, nous noterons aussi n , l'élément n • \a de l'anneau A. De l'égalité 4 = 22 = 2, nous déduisons 2 = 0; l'anneau A est donc de caractéristique 2. D'autre part, pour tous x. et y éléments de A nous pouvons écrire : (x + y)2 = xx -f xy + yx -f = x -f xy -h yx -f 2/ = x -h y. Donc (V(x, y) G ^4 x A) xy = —yx = yx ; l'anneau A est par conséquent commutatif, et de caractéristique 2. Si A a au moins trois éléments distincts, ce n'est pas l'anneau nul, donc 1^0 , et il a au moins un élément x, distinct de 0 et de 1. De l'égalité xx = x = x x 1, nous déduisons x(x — 1) = 0 ; comme les éléments x et x — 1 ne sont pas nuls, l'anneau A a des diviseurs de zéro. Supposons que l'anneau A ait au moins 3 éléments, alors 0 ^ 1, et il existe
II. 5 L'anneau des entiers relatifs, la structure d'anneau 23 Soit ift le sous-ensemble de l'anneau ZN formé des suites stationnâmes d'entiers relatifs, a) Vérifier que $ft est un sous-anneau de ZN . Exercice 10 : un élément c différent de 0 et de 1. L'élément c — 1 de A ne peut être ni 0, ni c, ni 1 = — 1 . L'anneau A a donc au moins 4 éléments. L'anneau (Z/22)2 est un anneau de Boole à 4 éléments (voir chapitre IV). Exercice 8 : Dans un anneau A, on suppose (Vx G A) x3 = x . Montrer que A est commutatif. ■ Soit n un entier relatif, nous noterons aussi n , l'élément n • 1^ de l'anneau A . De l'égalité 8 = 23 = 2 , nous déduisons 6 = 0 ou encore 3 = — 3 . Pour tout x dans A nous obtenons : (x - l)3 = x3 - Sx2 + Sx - 1 = x - Sx2 4- Sx - 1 = x - 1 soit Sx2 = Sx. D'où, pour tous x et y éléments de A : S(x 4- y)2 = 3x2 4- 3(xy 4- yx) -h 3y2 = 3x 4- 3(xy 4- yx) + Sy = S(x -h y) soit 3xy = — Syx = Syx. Nous obtenons aussi : (x 4- y)3 = x3 4- xyx 4- yx2 4- y2x 4- x2y 4- xy2 4- yxy -f y3 = x 4- y et (x - y)3 = x3 — xyx — yx2 -I- y2x — x2y -f xy2 4- yxy — y3 = x — y, d'où par différence : (x-hy)3-(x-y)3 = 2(xyx4-yx24-x2y4-y3) = 2y soit 2(xyx4-yx2+x2y) = 0. Posons z — xyx -h yx2 -h x2y . On voit que : xz — zx = x2yx -h xyx2 -h x3y — xyx2 — yx3 — x2yx = xy — yx. Comme 2z = 0, nous en déduisons 2xy = 2yx. Nous avions démontré plus haut que 3xy = 3yx , donc par différence xy — yx . Ceci étant vrai pour tous x et y éléments de l'anneau A, cet anneau est nécessairement commutatif.
24 Chapitre II Nombres entiers, nombres rationnels b) Pour tout entier naturel i notons Si la suite dont tous les termes sont nuls, sauf le terme d'indice i qui vaut 1 ; ces suites sont stationnaires. Soit V? : ift —> 2 un homomorphisme d'anneaux ; posons pour tout i G N, ip(si) = ki. On vérifie comme dans l'exercice 5 que les nombres ki sont tous 0 ou 1 et que soit tous les ki sont nuls, soit un et un seul d'entre eux n'est pas nul. Notons aussi J la suite constante égale à 1 ; c'est l'élément neutre multiplicatif de l'anneau, donc </?(/) = 1. Si la suite u est stationnaire au moins à partir du rang p, de valeur stationnaire a, nous pouvons écrire : p-i u = - a)ei -ha-/. i=l Donc : p-i ip(u) = ^2,{ui - o)ki + a . i=l Si tous les ki sont nuls, l'application y> est nécessairement l'application qui à une suite stationnaire fait correspondre sa valeur stationnaire ; cette application est effectivement un homomorphisme d'anneau. Si l'un des ki n'est pas nul, posons kq = 1 ; on peut supposer q < p, donc : (f(u) = (uq - a) + a = uq. Dans ce cas l'application (p est nécessairement l'application u*-+ uq . Il est clair que pour toute valeur de l'entier q, on obtient bien ainsi un homomorphisme d'anneaux de Z^ vers Z. En conclusion, les homomorphismes cherchés sont les applications coordonnées et l'application qui à une suite stationnaire fait correspondre sa valeur stationnaire. || Soit A un anneau. On suppose, pour tout couple (a, b) G A x A Exercice 13 : f b) Trouver tous les homomorphismes d'anneaux : ift —* Z . ■ d) La suite constante égale à 1, élément neutre pour la multiplication dans l'anneau Z^ , est stationnaire ; si (un) est une suite d'entiers relatifs sta- tionnaire à partir du rang p, et que (vn) est une suite d'entiers relatifs stationnaire à partir du rang q, alors les suites (un - vn) et (unvn) sont stationnaires à partir de rangs ^ sup(p, q). Le sous-ensemble des suites stationnaires est donc un sous-anneau de ZN .
Les nombres rationnels, la structure de corps 25 Il : (ab)2 — a2b2 . Démontrer que A est commutatif. ■ Pour tous x et y éléments de A : ({x + l)y)2 = (xy 4- y)2 = (xy)2 4- xy2 4- yxy 4- y2 = x2y2 H- xy2 4- yxy -f y2 = (x 4- l)2y2 = (x2*+ 2x 4- l)y2 = x2y2 + 2xy2 -f y2. D'où par différence xy2 = yxy . En appliquant cette égalité à x et y -h 1, nous obtenons : x(y 4- l)2 = xy2 -h 2xy -f x = yxy 4- 2xy -I- x = (y 4- l)x(y -f 1) = yxy -f yx 4- xy -f x. Par différence nous obtenons : xy — yx = 0. L'anneau A est donc néces sairement commutatif. § II.6 LES NOMBRES RATIONNELS, LA STRUCTURE DE CORPS Exercice 4 : Il Trouver tous les triplets (x,y,z) G (N*)3 tels que: 1 1 1 , - + - 4- - = 1. ■ Il x y z Nous pouvons supposer x ^ y ^ z. Comme 1 /x < 1, nous en déduisons x > 1, donc x 5* 2 . Supposons x = 2 . La condition devient : y + ~z = 2 SOlt (y + ^ = y*' Nous pouvons encore écrire cela sous la forme : (y — 2)(z — 2) = 4. Les solutions (y, z), en nombres entiers ^ 1, telles que y ^ z, sont (y, z) = (3,6) et (y, z) = (4,4) ; ce qui correspond aux égalités : 111, 111, 2 + 3 + Gt 2 + 4 + 4=1- Supposons 3 ^ x ^ y ^ z . Nous observons que : - + - = l- -2*l-- = - soit 3(y + *) ^ 2yz. y z x 3 3
26 Chapitre II Nombres entiers, nombres rationnels Posons y' = y — 3 et z1 = z — 3 , on peut écrire la condition ci-dessus sous la forme : 3(y' + z' + 6) ^ 2(2/' + 3)(*' 4- 3) soit 0 ^ 2yV + 3y' 4- 3z'. La seule solution possible en nombres ^ 0 est x' = 0 et y' = 0, d'où y = 3 et z — 3 , ce qui implique x = 3 . On vérifie facilement que le triplet (3,3,3) est solution puisque : 1 1 1 , 3+3+3=L En conclusion, les triplets croissants vérifiant la condition de l'énoncé, sont lestriplets (1,3,6), (2,4,4) et (3,3,3). Exercice 5 Trouver tous les triplets (x,y,z) G (N*)3 tels que xyz = 14- x + y + z . m Nous pouvons supposer 1 ^ x ^ y ^ z. La condition équivaut à : xyxz = x + x2 + xy + xz soit (xy — l)(xz — 1) = 1 4- x -I- x2. En minorant y et z par x nous obtenons : (x2 —l)2 ^ 14-x-hx2 , soit encore x4-3x2-x ^ 0, d'où enfin x3 ^ 3x4-1. Si x ^ 2 , alors 3x-hl < 4x ^ x3 , ce qui est exclu ; donc x = 1. La condition s'écrit alors : (y — l)(z — 1) = 3 . La seule solution (y, z) en nombres entiers où y ^ z est donc (y, z) = (2,4). La seule solution pour (x, y, z) est donc le triplet (1,2,4), ce qui correspond à l'identité : 1x2x4 = 1 + 14-2 + 4. Exercice 9 : Démontrer, pour n G N, n ^ 2, que S'n = i + ^ + ... + — é 2 3 n ™ 1 1 1 N ; généraliser pour Tn = H — + ... H , ou a a + b a + 2b a + nb et b e Nous ne traiterons pas le cas particulier 6 = 1, car sa résolution n'est pas différente de la résolution du cas général b impair. Nous utiliserons des notions d'arithmétique qui seront vues dans le chapitre IV. On peut supposer que les entiers a et b sont premiers entre eux. En effet, posons d = pgcd (a, b), et a = da', b = db'. Si Tn est entier, alors
II.6 Les nombres rationnels, la structure de corps 27 TL — ——r: H—, -f •. • H—7——r; = dTn , est aussi entier, et o! et 6' a' + bf a'+ 26' a' + nb' sont premiers entre eux. On suppose d'abord que b est impair. Les nombres a + 6, a + 26,..., a + nb, sont alternativement pairs et impairs ; comme il y en a au moins 2, l'un d'eux est divisible par 2. Soit a le plus grand entier tel que 2a divise l'un de ces nombres, d'après ce qui précède, a > 0 . Montrons que 2a divise un seul de ces nombres. Sinon, si 2a divise a + ib et a + jb, où 1 ^ i < j ^ n, alors 2a divise (j — ï)b donc divise ( j - i) ; nous en déduisons : l^i<i + 2a^j^n, mais comme a + ib est de la forme (2fc + l)2a , le nombre a+(i + 2a)b est de la forme (2fc + l+6)2a , donc divisible par 2a+1 puisque b est impair, ce qui contredit la définition de a. Le ppcm des nombres a+6, a+26,... ,a+n& est de la forme II = 2a(2/i+l) ; quand on réduit les fractions -, —-,..., à leur dénominateur a + b a + 2b a + nb commun on trouve des numérateurs tous pairs sauf un. La somme Tn est 2p ~\~ IL donc une fraction de la forme : —7- — ( a > 0 ), et ne peut donc être 2a(2a + l) v h F un entier. Supposons maintenant que b est pair, nous poserons b = 2bf. Remarquons que comme a et b sont premiers entre eux, a est impair. On raisonne ici par l'absurde, en supposant que Tn est un entier, donc ^ 1. Etablissons d'abord quelques inégalités. En majorant toutes les fractions par 1 /(a + b), ce qui donne une majoration stricte de Tn , on obtient : n/(a -h b) > Tn ^ 1, donc n > a + b ^ 3 , soit n ^ 4. D'autre part : a + nb b 2b " ' nb 1/11 1\ = b\1+2 + 3+- + n)- On démontre alors facilement par des méthodes d'analyse que 1 ^ Tn < (1/6)(1 + lnn), soit ln(n) > b - 1. 1 + 1 a + b a -f 2b + Soit p le plus grand nombre premier ^ n, donc p ^ 3 ; d'après le théorème de Bertrand, on sait que n < 2p. Le lecteur pourra trouver une démonstra tion de ce théorème dans : HARDY G. H., WRIGHT E. M., An introduction to the theory of numbers, Oxford Un. Press, 1959. Comme n > a + b, d'où n > b, on voit que p > b', donc p est premier avec b', et avec b . Parmi les nombres a -h 6, a -f 26,..., a -h nb , l'un au moins est divisible par p ; en effet l'équation en i entier a -h ib = 0 [p] a exactement une solution dans chaque intervalle de p entiers successifs puisque 6 est
28 Chapitre II Nombres entiers, nombres rationnels premier avec p. Si un seul de ces nombres est divisible par p, en raisonnant comme dans le u cas où 6 est impair, on voit que Tn peut s'exprimer sous la forme , où pav a ^ 1, u et v entiers premiers avec p ; le nombre Tn ne peut donc être entier, il y a contradiction. Dans le cas contraire, exactement deux des nombres a + 6, a + 26,..., a + nb sont divisibles par p, car n < 2p. Ces deux nombres sont a + ib = kp et a + ib-hpb — (k-\-b)p ( k est impair puisque comme a est impair, les nombres a + 6, a + 26,..., a + nb sont tous impairs). Or : 1 1 1 1 2k+ p a + i6 a 4- (î 4- p)6 A;p (A; 4- b)p pk(k + 6) Si p ne divise pas 2fc+6, on peut encore utiliser l'argument du cas précédent, et il y a contradiction. Si p divise 2k -h 6 = 2(fc + 6'), alors p divise k 4- 6', et par conséquent p ^ k + b'. Mais a 4- (i — p)6 = (fc - 6)p <a-h6^a4-i6 = fcp, donc fc-6 < (a + b)/p < 2(a + 6)/n < 2 , soit A: < 6 + 2 ou encore k ^ 6+1. Nous pouvons déduire de ce qui précède : p ^ 36' + 1 et n < 2(36' + 1) = 36 + 2 , soit enfin n ^ 36 + 1. Rappelons que 6 — 1 < ln(n) ; d'où exp(6 — 1) < 36 + 1 soit : e6"1 -1 36 _ 3 Si 6^4, c'est impossible car : e6"1 - 1 e3 - 1 n (en utilisant la convexité de la fonction exponentielle), alors que : 3 3 3+6^3+3=4- Il reste à examiner le cas 6 = 2, soit 6' = 1. Dans ce cas, p ^ 36' + 1 = 4 ; comme p ^ 3 et p premier, nécessairement p = 3. Comme A: ^ 6 + 1, A: ^ 3 et k est impair ; il faudrait donc que le nombre premier 3 divise k + b' égal à 2 ou 4, ce qui est impossible. Le nombre Tn ne peut donc être dans aucun cas entier. Exercice 13 X y 2 Résoudre dans N2 l'équation —r = — , où x et y x2 + xy + y2 67 y ne sont pas tous les deux nuls. ■
IL6 Les nombres rationnels, la structure de corps 29 L'isomorphisme / est donc nécessairement l'identité de Q . L'identité est a fortiori le seul automorphisme du corps Q . La condition s'écrit : 67(x — y) = 2(x2 4- xy 4- y2). Nous voyons que néces sairement x > y et que x — y est pair. Posons x 4- y — 2u et x — y = 2v , d'où u ^ > 0, x = u + u, y = u — v . La condition devient : 67t> = (u 4- v)2 4- (u 4- v)(u -v) + (u- v)2 = Su2 + v2, ce qui s'écrit aussi (67—v)v = 3u2 . Nous pouvons remarquer que (67—v)v = 3u2 ^ 3v2 , donc 4v ^ 67, soit v ^ 16. Un peu d'arithmétique permet d'accélérer cette recherche qui donne une seule solution : u = 8, v = 3 donc x = 11, y = 5 . Les nombres entiers (67 — v) et v sont premiers entre eux, en effet si un nombre premier les divisait tous les deux, il diviserait 67 donc serait 67; mais alors 67 diviserait v , donc v ^ 67, ce qui est exclu. L'un des deux est divisible par 3. Si v est divisible par 3, en posant v = 3v', la condition s'écrit : (67—3v')v' = u2 . Comme 67 — 3vf et v' sont premiers entre eux, chacun d'eux est un carré. L'entier v' est donc un carré plus petit que 16, il ne peut être que 1, 4, 9 ou 16, ce qui donne pour valeurs de 67 — 3v' les nombres 64, 55, 40 et 19. Comme 64 est le seul carré d'entier parmi ces 4 nombres, la seule solution est v' = 1, d'où v = 3 et u = 8. Si w = 67 - v est divisible par 3, posons w = 3w'. L'entier w' est un carré majoré par 67/3 et minoré par (67 — 16)/3 = 17, il est facile de voir qu'il n'y a aucun carré d'entier dans cet intervalle. La seule solution est donc (x,y) = (11,5). Exercice 17 : a) Le seul automorphisme du corps Q est Id<Q , et c'est le seul isomorphisme de Q dans Q. b) Montrer que le seul isomorphisme du corps IR dans lui-même est l'automorphisme Id^ . ■ a) Si / est un isomorphisme de Q dans Q, alors pour tout entier relatif p et tout entier q, q > 0 : q'f(t) = f(9't) =/(p)=p'/(1)=p'1=P) d'où:
30 Chapitre II Nombres entiers, nombres rationnels b) Soit g un isomorphisme du corps (R dans lui-même. Pour tout entier relatif p, tout entier q, q > 0 , et tout réel x , nous pouvons écrire : Nous dirons que l'application g est Q-linéaire. Nous en déduisons facilement, en prenant x = 1, que la restriction de g k Q est l'identité. Si x est un réel > 0, on sait que c'est le carré d'un réel y ; donc g(x) = a(y2) — (a(y))2 > 0. Si maintenant x et y sont deux réels et x > y, alors g(x) — g(y) = g(x — y) > 0, donc g(x) > g(y). L'application g est donc strictement croissante. Supposons que l'application g ne soit pas l'identité ; il existe alors un réel x tel que g(x) ^ x. Si g(x) < x , alors il existe un rationnel r, tel que g(x) < r < x (propriété bien connue des réels) ; comme g est strictement croissante, on obtient r = g(t) < g(x) , ce qui est contradictoire. Si g(x) > x , il existe un rationnel r tel que g[x) > r > x , d'où r = a(r) > g(x) , ce qui est contradictoire. L'isomorphisme g est donc nécessairement l'automorphisme Wr . d'où:
Chapitre III BASES DU CALCUL ALGÉBRIQUE ET COMBINATOIRE §111.3 COMPOSÉ DE FAMILLES A SUPPORT FINI. NUMÉRATION Exercice 1 : (numération anglaise) : Soit (rk)k^i une suite d'entiers > 1 ; on considère l'ensemble $&r des suites à support fini s = (si)ie^ d'entiers tels que Si < r*i+i pour tout i ^ 0. Montrer que l'application : sir -* N, S Si ( II Vk ) = 50 + 5iri + 52^1^2 + . . • ieN \k=i ) est bijective. ■ Associons à tout entier n la suite (p,i)%ç.\ telle que no = n et telle que pour tout i entier, n^+i soit le quotient dans la division euclidienne de n^ par n+i • Montrons que l'application introduite par l'énoncé est injective. Si n = so + s\r\ 4- 52^1^2 4- ..., montrons que pour tout i entier, n^ = Si 4- Sï+iri+i 4- Si+2^i+i^t+2 4-..., la suite (n^)^ étant la suite associée à l'entier n. C'est vrai pour i = 0 et si c'est vrai pour i, comme Si < 7*1+1 , Si est le reste dans la division euclidienne de n* par r^\ et le quotient est ni+\ — Si+\ 4- Si+2^+2 -h Sï+37*i+2^+3 + Cette égalité est donc vraie pour tout i entier. On voit aussi que pour tout i entier, Si est nécessairement le reste dans la division euclidienne de n^ par r^i. Cela démontre l'unicité de la suite (si)^ , l'entier n étant fixé. L'application introduite par l'énoncé est donc injective. Montrons qu'elle est surjective. Il suffit de montrer que la suite (si)ie^ trouvée ci-dessus a bien pour image
32 Chapitre III Bases du calcul algébrique et combinatoire l'entier n . Montrons pour cela que pour tout i > 0 : (E») n = s0 + sin + ... + Si_irir2 • • • -f n^ri^ ... n-ir*. Pour i = 1 cette égalité s'écrit n = so + ^1^1 ? ce qui est vrai. Si l'égalité est vraie pour i, alors en remplaçant dans (E*), par Si + ni+i7*i+i , on obtient l'égalité (Ei+i). L'égalité (E») est donc vraie pour tout entier z. Si pour tout j , rij > 0, alors pour tout i, n» > rii+i (puisque r^+i > 1 ), ce qui est impossible ; il existe donc un entier j tel que rij = 0. On voit facilement que pour tout i ^ j , = = 0 . Les suites (n*)^ et (si)ieM sont par conséquent à support fini, et comme : n = so -h sin + ... + Sj-irir2 ... r^-i on voit que : n = Y,Si \tlrk) ' ieN \k=l / Cela démontre que l'application introduite dans l'énoncé est surjective. Elle est donc bijective, ce qu'il fallait démontrer. §111.4 DÉNOMBREMENT Exercice 2 : Il Pour n G montrer que : f ll! + 22! + ...+nn! = (n + 1)!-1.» On vérifie que pour tout i entier : ii\ = ((i + 1) - l)i! = (z + 1)! - il, donc pour tout n eN* : ll! + 2 2! + ... + nn! = (2!-l!) + (3!-2!) + .. . + ((n + l)!-n!) = (n + l)!-l, ce qu'il fallait démontrer. Exercice 4 : Soit a G C, n et rGN. Montrer que : On sait que (voir l'exemple 3 du paragraphe III.4) pour tout a G C et r eN : (r + !) = (r + l) + (r) "** (" + î) " (r + l) = (r) '
III.4 Dénombrement 33 Nous pouvons donc écrire : En (a — i\ _ ^ (ex — i; + 1\ ^(a — i 1 r y = ^ 1 r +1 J " ^ U + 1 i=o x 7 i=0 x 7 z=0 x /a 4-1\ /a — n\ = \r + l) " Vr + lJ' ce qu'il fallait démontrer. Exercice 5 : Soit p, a, n des entiers tels que 0 q < p ^ n. Etablir la relation : ai vp-(9+i)Jv « J w ' En déduire : £ 2k (2n ~ = 22" . ■ Une partie P de [l,n] , de cardinal p, peut être identifiée à une suite strictement croissante de p entiers (xi, £2, • • • , ..., xp), à valeurs dans [1, n] . Nous dirons que l'élément , où i G [1, nj, est l'élément de numéro i dans P. Pour tout k G [l,n] , notons Afc l'ensemble des parties de [l,n] de cardinal p et dont l'élément de numéro q + 1 est k. Une partie P est élément de Ak si, et seulement si, elle est constituée d'une partie de — 1] qui a q éléments, de l'élément k , et d'une partie de |k + 1, n] qui a p — (q 4- 1) éléments. L'ensemble A^ est non vide si, et seulement si : q ^ k — 1, soit fc ^ g + 1 , et p — (q + l)^n — k soit k^n — p + q + 1. D'après ce qui précède, le cardinal de est ( U, ^ x ) I ) . Comme la famille \p-(q + l)J\ q J (Aiç)kelq+i,n-p+q+i] est un partage de l'ensemble des parties de |l,n] de cardinal p, nous en déduisons : k=n—p+g+l E k=q+l yTv / n-k \fk-l\_fn\ Comme pour tout i entier 2* = ( ) > nous voyons que pour tout m g=o x^7 entier : i=0 x 7 i=0 ç=0 x^7 x 7
34 Chapitre III Bases du calcul algébrique et combinatoire /2m - ï m 2=0 X 7 q=0 i=q X^7 x Ç=0 fc=9+l Pour g e [0, mj , posons p = m + g+1 et n = 2m -f 1, on vérifie que 0 ^ q < p ^ n , que p — (g -f 1) — m , que n — p 4- g +1 = m 4-1, et que pour tout k entier, n — k = 2m 4- 1 — k. En utilisant la formule (1) démontrée ci-dessus, on obtient : ™ V2m-;\ =y> / 2m+ 1 \ = y> /2m 4-1\ = = - 11)1 f2m+= -22m+i = 22m Exercice 8 : Démontrer, pour q eN* et n eN* : ^_l_/g + fc-l\ 1 ^/q + n-l\ f^2k\ k J 2*"1 f-* I Jfc J ' fc=0 x 7 fc=0 x 7 Cas particulier où q = n . m Posons pour q et n entiers > 0, ^ 1 (q + k-l\ 1 ^i/g + „-l\ fc=0 x 7 fc=0 x 7 En utilisant la relation de Pascal, nous obtenons, si n > 1 et q > 1 : En intervertissant l'ordre des sommations nous obtenons :
III.4 Dénombrement 35 1x^i 1 fq + k k=l X n— 1 i / . r «\ n—1 = i + _1_ /g + k - 2\ y4 J_ (q + k - 2\ J^J_fq + k-2\ l1^ l_(q + h-l\ _ 1 2 De manière analogue : — Uq— l,n 0^g,n—1 2n-i+2n-i^l A; 7 2^-x ^ V k-1 J k=l X 7 fc=l x 7 fc=0 x 7 /i=0 x 1 = Vq-l,n + -^,n-l • D'autre part, pour tout n 5? 1 : n-l 1 / 1 \ et: n-l ^ = ^Ë(l) = ^r(2n-1) = ^- On vérifie aussi que pour tout q ^ 1, u^i = 1 = vQyi . Montrons maintenant par récurrence sur l'entier p ^ 2 que pour tous n ^ 1 et g ^ 1, tels que n + q = p, uqyTl = vQyn . Cette égalité est vraie pour p = 2 , car alors n = 1 et q = 1. Si cette relation est vraie pour p ^ 2, et que n et g sont des entiers ^ 1 tels que n + g = p+ l,si n = 1 ou g = 1 alors on a vu que uq,n = vq,n , si q > 1 et n > 1, alors comme g — 1 -f n — p et q + n — 1 = p, par récurrence : I I - ^<7,n — ^q—lyn ~i~ ^^Ç»71-1 — Vq— l,n ^^j71-1 — ^9>™ * L'égalité : ug>n = vq^n est donc vraie pour tous entiers q ^ 1 et n ^ 1, ce qu'il fallait démontrer.
36 Chapitre III Bases du calcul algébrique et combinatoire card 1\JeA =J2(~1)k~1 Ecard f>< ' \i=i ) k=i ie®k \i€/ / où SPfc désigne l'ensemble des parties de [l,n] de cardinal k . 1 Soit E un ensemble fini qui contient (^J Ei. Nous utiliserons les propriétés i=l suivantes de la fonction caractéristique d'une partie de E, considérée comme application de E vers l'anneau Z (mais à valeurs dans {0,1} ) : Pour toute partie A de E : Xe\a = 1 - Xa- Pour toutes parties A et B de E : Xadb =Xa*XB' Et enfin, pour toute partie A de E : card (A) = Y^Xa(x). xeE Nous en déduisons que : n n i=i 1=1 t=i Nous avons maintenant à développer le dernier produit ; pour cela démontrons par récurrence sur l'entier n la formule : n(«<+*i)= e (na')(n6')> i=l PC[l,nJ \i€p / \i<£p / où (az)ze[i,nj et (Mie[i,nl sont des familles à valeurs dans un anneau commutatif A (le produit d'une famille vide est par convention égal à 1). Cette formule est évidemment vraie pour n = 1. Supposons la vraie pour n ; soient (ai)ie[i>n+ij et (&i)ze[i,n+il deux familles à valeurs dans A. Soit: *>= e iH n * PC[l,n+ll \t€P / \ï€[l,n+l]\P Exercice 9 : (formule du crible): Soit Ei, E2,..., En des ensembles finis. Démontrer :
111.4 Dénombrement 37 Nous pouvons écrire : d = E Eh n *+ E Eh II PC|[l,n+lJ, (n+l)ePieP iG[l,n+l]\P Pc[l,n]z€P ie|[l,n+lJ\P En posant, dans la première somme Q = P\{n + l}, partie de Jl, n] , nous obtenons : d = ^2 an+inai n bn+iYiaî n 6* QC[l,nl i€Q i€[l,n]\Q PC[l,n] i€P iÇ[l,n]\P =(an+i -h 6n+i) 5^ n PCll.n] i£p i€[l,n]\P En utilisant l'hypothèse de récurrence nous obtenons : D = (an+i+6n+i) Yl (ai + M= Il (a* + 6*)- t€[l,n] i£[l,n+l] La formule est donc vraie à Tordre n -h 1. Cette formule de développement d'un produit est donc vraie pour tout entier n. En prenant pour anneau a l'anneau des applications de e vers l'anneau Z , nous obtenons : rï(i-xEj= e n c-xs.), i=l PC[l,n]i€P d'où, en notant SPfc l'ensemble des parties de [l,n] de cardinal fc : ri(i-^.)=i+E(-i)feE n^- i=l k=l PG^fc i€P Soit encore : v,K=1-n(i-^)=D-i)fc-iExna,. U ^ i=l fc=i P6^fc igp l-l En faisant la somme des valeurs de ces deux fonctions nous obtenons finalement : card ([J eA = f^i-1)"-1 £ card (f) ,
38 Chapitre III Bases du calcul algébrique et combinatoire ce qu'il fallait démontrer. Exercice 13 (familles spernéennes) : : Soit E un ensemble fini à n éléments et (Ai, A2,..., Ah) une famille de parties de E. On dit qu'une telle famille possède la propriété S si, pour tout couple (i,j) tels que i G , j G fl, ftj et i 7^ j , la relation A» C Aj n'est jamais vérifiée. a) Soit A; fixé G [l,n] . Montrer que la famille des A:-parties de E (prise dans un ordre quelconque) possède la propriété S. b) On prend h = 2. Combien y a-t-il de couples (A\,A>2) qui possèdent la propriété S ? c) On appelle chaîne de E une famille (Ci, C2,..., Cn) de parties de E vérifiant: (Vi G [l,n]) card(Ci) = i et C C^+i pour îG [l,n-lj. Combien y a-t-il de chaînes dans E ? Montrer que si une famille si = (Ai, A2,..., Ah) de parties de E possède la propriété S, pour toute chaîne = (Ci, C2,..., Cn) on a card (a! n^) =^ 1. d) Soit si = (Ai, A2,..., Ah) une famille de parties de E possédant la propriété 5. Soit r& l'ensemble des chaînes % de E telles que card(^îricê) = 1. On définit l'application (f : r& —> ,sd qui, à toute chaîne % G r&, associe ^(^), le seul élément commun à £i et à % . Montrer que (p est surjective et calculer, en fonction de card (A), le cardinal de (p~1({A}), c'est-à-dire le nombre de chaînes dont l'image par ip est A . e) Montrer que : h 1 i=l Vcard-At/ et en déduire que h ^ sup (") , ce dernier nombre étant noté p€[0,n] u(n). Vérifier que u(2n — 1) = u(2n)/2 . Existe-t-il une famille (Ai, A2,..., Aw(n)) de parties de E possédant la propriété S ? f) On pose E — [1, n] et on donne n réels ai, a2,..., an , tous > 0 (non nécessairement distincts). On définit l'application / de 3>(£) dans U par : /(A) = £ a* ; /(0) = 0. Montrer que, pour tout t G B?, le nombre g(t) de parties A de telles que /(A) = t est nécessairement ^ u(n). ■
III.4 dénombrement 39 a) Si A et B sont des parties de E, distinctes, de cardinal k, il est impossible que A c B ou B c A car alors A et B seraient identiques. Toute famille injective de A:-parties de E est donc une famille spernéenne. b) Soit % l'ensemble des couples (A, B) de parties de E telles que A C B . Pour B fixée de cardinal k , le nombre de parties A de E telles que A c B l'ensemble 3F des couples (A, de parties de E telles que 5 C i est 3n ; l'intersection de % et de SF est l'ensemble des couples (A, A), où A est une partie de E, son cardinal est donc 2n . Nous pouvons en déduire que le cardinal de l'ensemble des couples (A, B) de parties de E telles que A c B ou 5 C A est 3n + 3n - 2n . Comme le nombre de couples (A, B) de parties de E est 2n x 2n , on voit que le nombre de couples (A, B) possédant la propriété S est 4n - 2 x 3n + 2n . c) Remarquons que le dernier élément d'une chaîne dans E est nécessairement E lui-même. Montrons par récurrence sur l'entier n 2* 1 , que le nombre de chaînes dans E de cardinal n est n !. C'est évidemment vrai si n = 1. Supposons le résultat vrai pour n ^ 1 et soit E un ensemble de cardinal n + 1. Considérons l'application / qui à une chaîne % = (Ci, C2,..., Cn, Cn+i) dans E , fait correspondre le seul élément de E qui ne soit pas dans Cn ; il est clair que l'ensemble des chaînes % dont l'image est un élément x donné de E est l'ensemble des chaînes (Ci, C2,..., Cn, E), où (Ci, C2,..., Cn) est une chaîne dans E \ {x} . Le nombre de chaînes dans E de cardinal n H- 1 est donc, en utilisant la récurrence, (n H- 1) • n ! = (n -f 1)!. L'égalité est donc vraie pour tout ensemble de cardinal n + 1. L'égalité est donc, par récurrence, toujours vraie. Si % = (Ci, C2,..., Cn) est une chaîne dans E, et que 1 ^ i < j; ^ n, alors Ci est strictement inclus dans Cj ; ces deux parties ne peuvent donc pas être éléments d'une même famille spernéenne. Une chaîne et une famille spernéenne ne peuvent donc avoir qu'au plus un élément commun. d) Reprenons les notations de l'énoncé et posons k = card (A). Si ^ = (Ci, C2,..., Cn) est une chaîne élément de dont l'image est A , comme pour tout i e [l,n] card(Cf) = i, nécessairement A = Ck . On voit alors facilement que % = (Ci, C2,..., Cn) est une chaîne d'image A si, et seulement si, (Ci, C2,..., Ck) est une chaîne dans A , et (C^+i \ A, Cfc+2 \ A,..., Cn \ A) une chaîne dans E \ A ; le nombre de telles chaînes est donc k ! x (n — k) !. Ce nombre n'étant jamais nul, l'application <p est surjective. est 2k ; le nombre de parties B de cardinal k étant % est De même le cardinal de
40 Chapitre III Bases du calcul algébrique et combinatoire e) En posant ki = card (Ai), on vérifie que : h -, h è /„.\ Ë ki ! (n - ki) ! n! 1=1 i=l Comme le nombre de chaînes dans e est n !, ce quotient est ^ 1, ce qu'il fallait démontrer. Pour tout i G fl, n] , ^ u(n), donc : h 1 1>> W> h X{k) ^ d'où /i ^ u)(n). On sait que pour tout n entier > 0 et pour tout /iG[0,ra — lj: / n \ __ ^ — h /n\ On peut en déduire que dans le cas où n est pair, n = 2p, la fonction k i—► (^^j est strictement croissante sur [0,p] et strictement décroissante sur [p, 2p], d'où o;(2p) = • On vo^ de même que dans le cas où n /2p | ]\ est impair, n = 2p H-1, la fonction k f J est strictement croissante sur [0,p| et strictement décroissante sur [p + 1,2p], d'où u;(2p + 1) + P ) = ( 4. i ) ' ^ous voyons alors que pour tout n entier > 0, c ,„ ,v ,Y2n-l\ „ (2n-l)! n (n — 1) ! n! n!n! \ ^ / Soit k tel que ^j^J = uj(n), le nombre de parties de E de cardinal k est u;(n) ; une famille injective dont les éléments sont les A;-parties de E est une famille spernéenne de cardinal u)(n) (voir o)).
IIL5 Formule du binôme 41 J) Comme les nombres a* sont tous strictement positifs, l'application / est strictement croissante, l'ensemble des parties de E étant muni de l'ordre de l'inclusion. Nous pouvons en déduire que si A et B sont des parties de E distinctes et telles que f(A) = f(B) = t, il est impossible que A C B ou que B C A. Toute famille injective composée de parties A de E telles que f(A) — t est donc spernéenne ; d'après le e) le cardinal de cet ensemble de parties est ^ uj(ri) , ce qui signifie ici que : g(t) ^ u(ri). §111.5 FORMULE DU BINOME Exercice 6 : Démontrer par récurrence, en utilisant la formule du binôme, que : Essayer de trouver une solution plus élégante à partir de n-l k=0 Posons pour n entier ^ 1 : Nous obtenons pour tout n > 0 : n + 1 1 D'où en utilisant la relation de Pascal : ^n+l =
42 Chapitre III Bases du calcul algébrique et combinatoire J + Nous pouvons en déduire : f l\j) -n + l\j + l)' *>n+l <.+^g<-<:0- Soit: Un+l =Un + - (1 - l)n+1) = Un + 1 n + 1 n + 1 Comme ui = 1, il est clair que pour tout n entier > 0 , on a bien l'égalité : , 1 1 1 un = l + - + - + ... + -. 2 3 n Autre méthode. Pour tout t réel / O ona l'égalité : n-l fe=0 fc _ 1 - (l-*)n (1-t) En intégrant sur l'intervalle ]0,1], nous obtenons l'égalité de l'énoncé : , 11 1 M 1 /n\ 1 , ,/tA 1 1+2 + 3+--- + » = (1Jï-(2J 2+-(-1) Un" Exercice 7 : Vérifier, pour a G Q* , la formule de Reyley (1825) a6 + 45a4 - 81a2 4- 27 6a(a2 + 3)2 i3 + -a4 + 30a2 - 9 + -6a3 -f 18a L (a2 + 3)2 6a(a2 + 3) (N.B. : Cette formule montre que tout nombre rationnel peut s'écrire comme la somme de trois cubes de nombres rationnels.) ■ On sait que pour tout j € [0, nj :
III.5 Formule du binôme 43 On constate l'égalité : (a4-30a2-h 9)(a2 + 3) = = a6 - 30a4 + 9a2 4- 3a4 - 90a2 -f 27 = a6 - 27a4 - 81a2 + 27 = a6 + 9a4 - 81a2 -f 27 - 36a4 = (a2 + 3)3 - 108a2 - 36a4. Et: a6 4- 45a4 - 81a2 + 27 = a6 + 9a4 - 81a2 -h 27 + 36a4 = (a2 4- 3)3 - 108a2 + 36a4. Le membre de droite de l'égalité de l'énoncé est donc la fraction F égale à : [(a2 4 3)3 - 108a2 4- 36a4]3 - [(a2 + 3)3 - 108a2 - 36a4]3 63a3(a2 - 3)3 63a3(a2 + 3)6 (a2 4- 3)6 ' Comme pour tous rationnels A et B : {A + B)3 -(A- Bf = 6A2B + 2B3 = 2B(3A2 + B2), on voit que : [(a2 4 3)3 - 108a2 4 36a4]3 - [(a2 + 3)3 - 108a2 - 36a4]3 = = 2 • 62a4 [3((a2 + 3)3 - 3 • 62a2)2 4- 64a8] = 63a4 [((a2 + 3)3 - 3 • 62a2)2 4- 24 • 33a8] . On trouve après simplification : ((a2 + 3)3 - 3 ■ 62a2)2 + 2433a8 - 63a2(a2 - 3)3 F~a (a2+ 3)6 Le numérateur N de la fraction est : N = (a2 4 3)6 - 63a2(a2 4 3)3 + 3264a4 + 2433a8 - 63a2(a2 - 3)3 = = (a2 + 3)6 4 63a2 [6 • 32a2 + 2a6 - (a2 + 3)3 - (a2 - 3)3] . Pour terminer on voit que : (a2 4 3)3 4- (a2 - 3)3 = 2a6 + 2 • 27a2 = 6 • 32a2 + 2a6, et donc que N = (a2 4 3)6 , d'où F — a , ce qu'il fallait démontrer. || Dans un anneau commutatif, prouver l'identité : Exercice 10 :
44 Chapitre III Bases du calcul algébrique et combinatoire 2 ]P afc(ai 4- a2 4-... + ak) = f ^ a* ) 4- ]P a£ . On vérifie que : Comme : n n / k \ S = 2 ]T a*, (ai 4- a2 4-... -f ak) = 2 ^ ( a* ^ a^ J = n = 2 ]p akCLh = 2 51 a^a/i+2 Ea* - nous voyons que : s = EahCLk+2 E °%= E ahak + E h^k fc=l (h,fc)€[l,nj2 fc=l «2 Soit enfin : \Jfc=l / \/l=l / fc=l \k=l / jfc=l ce qu'il fallait démontrer. §111.7 NOTION D'IDEAL D'UN ANNEAU COMMUTATIF Exercice 1 : Soit A un anneau commutatif non nul. On appelle nilradi- cal de A l'ensemble des éléments nilpotents de A, c'est-à-dire l'ensemble Çfl(A) formé des x e A tels que xn = 0 pour au moins un n G N* . Montrer que Sft(A) est un idéal de A . ■ Il est clair que $H(A) n'est pas vide car il contient 0. Soit x G $l(A), et a G A ; il existe un entier n > 0 tel que xn = 0, donc (ax)n = anxn = 0 ; l'élément ax est donc aussi nilpotent. En particulier, si x est nilpotent, —x est nilpotent. Soient x et y deux éléments nilpotents, et deux entiers
111.7 Notion d'idéal d'un anneau commutatif 45 n > 0 et m > 0 tels que xn = ym — 0. En utilisant la formule du binôme on obtient : n+ra— 1 _ _ ,,n+m— 1—i n+ra— 1 / n v 2=0 ^ ' Mais si 2 G [0,n — 1], alors n + m- l- i ^ m, donc yn+m~1-1 = o ; de même, si i G [ra,n + m — 1], alors Xe = 0 ; tous les termes dans le développement de (x 4- y^+m-i SOnt donc nuls et (x -f t/)n+m_1 = 0. L'élément (x + ?/) de A est donc nilpotent. L'ensemble <3l(A) des éléments nilpotents de A est donc un idéal de l'anneau A. Exercice 2 Soit a un idéal d'un anneau commutatif A . On appelle racine de a (que l'on peut noter y/â ) l'ensemble des x e A tels que xn G a pour au moins un n G Montrer que y/â est un idéal de A. Que se passe-t-il si a = {0^} ? Montrer que: y/y/o. — y/â et que, si a et b sont des idéaux de A, on a : y/âr)y/b = y/anb ; \AC \/a + & ; et y/a + b = \Jy/â+ y/b . ■ Il est clair que y/â n'est pas vide car il contient 0. Soit x G y/â, et a G A ; il existe un entier n > 0 tel que xn G et, donc (ax)n = anxn G a ; donc ax G \/S • En particulier, si x G \/â alors —x G \/5. Soient x et t/ deux éléments de y/â, et deux entiers n > 0 et m > 0 tels que xn G a et 2/m G a . En utilisant la formule du binôme on obtient : n+ra—1 / lX Mais si i G [0,n — 1], alors n + m- l- i ^ m, donc yn+m-1-i e a ; de même, si i G [n,n + ra — 1], alors x1 G a ; tous les termes dans le développement de (x + y)n+m~1 sont donc dans a et (x 4- y)n+m-1 g a . L'élément (x 4- y) de A est donc dans y^- L'ensemble y/â est donc un idéal de l'anneau A . Dans le cas où a = {0,4} , il est clair que y/â = 2ft(A). On remarque que l'application a h-> y/â est croissante pour l'ordre de l'inclusion et que pour tout idéal a de A , a C \/5 • Montrons que si a est un idéal de A , V\7a = . Comme y/â C \/y/â, il suffit de montrer l'inclusion opposée. Soit x G \/\7g > ^ existe un entier n > 0 tel que xn G et un entier m > 0 tel que (xn)m G a ; donc
46 Chapitre III Bases du calcul algébrique et combinatoire xnm £ Q . noug en déduisons que x G y/â. Cela prouve que \J~\7a C y/â, et donc finalement que yjy/â = y/â. Montrons que si a et b sont des idéaux de A , y/a D y/b = y/a D b . Il est clair que y/a D b C y/â et y^a n b C \/b » P31 conséquent y/a fi b C y/â n >/b . Montrons l'inclusion opposée. Si x G y/â D y/b , il existe un entier n > 0 et un entier m > 0 tels que xn G a et xm G b, alors xnm = (xn)m G a et xnm = (xm)n G b, donc x G y^a n b. Nous en déduisons que y/â n \/b C \/û n b , et finalement y/â fl \/b = y^a D b . Si a et b sont des idéaux de A, y/â C y/a + b et >/b c \/a + & » donc y/â + y/b C \/a H- b , et par conséquent \Jy/a + y/b C ^/y^a + é* = y/a + b . Comme a C y/â et b C \/b , on voit que a -h b C ^â + y/b , donc y/a -f b C y/a + \/b. Finalement, par double inclusion, nous obtenons l'égalité : Va~+~b = \Jy/â+ y/b. Exercice 3 : Dans un anneau commutatif non nul A, un idéal a est dit maximal ssi : a ^ A, et les seuls idéaux de A contenant a sont a et A. On donne un ensemble fini non vide E, un corps commutatif K et on considère l'anneau KE. d) Pour chaque a e E, l'ensemble Wa = {/ G | /(a) = 0} est un idéal maximal de KE . 6) Montrer que a i—> 33îa est une bijection de E sur l'ensemble des idéaux maximaux de KE . c) Montrer que cette propriété tombe en défaut si E n'est plus supposé fini. ■ a) Un élément a de E étant fixé, l'application / »-» f(a) de KE vers K est un homomorphisme d'anneaux (Définition II.5.3 exemple 5). Le noyau de cet homomorphisme d'anneaux, ïïla , est donc un idéal (Proposition III.7.1). Soit S un idéal de KE qui contient 3Wa . Si S ^ Wfla , il existe une application /, élément de 3, telle que f(a) ^ 0 ; soit g une application de K vers E , l'application h = g — (g(a)/f(a)) • / prend la valeur 0 en a et est donc un élément de 3Ka , donc de S ; nous pouvons en déduire que g est élément de S . Comme ceci est vrai pour toute application g : K —► E , nous voyons que 3 = A . L'idéal 3Ka est donc maximal.
III. 7 Notion d'idéal d'un anneau commutatif 47 b) Montrons d'abord que l'application a »-* 3Ka est injective. Soit pour x e E l'application Sx : E —» K définie par: Sx(y) = 0 si x ^ y et 6x(y) — 1 si x = 2/ • Si a et 6 sont des éléments de E distincts, on voit que 6a G sMb \ Wla et 6b G 2Jîa \ ; les idéaux %Jla et 3Kb sont donc distincts si a et b le sont. Montrons maintenant que l'application a i—► 3Wa est surjective. Soit 3 un idéal de l'anneau KE qui n'est inclus dans aucun des idéaux Wla . Pour tout élément o de l'inclusion Wla C 3Ka -f 3 est donc stricte, donc $Jla + 3 = . Il existe donc, pour tout a G E, une application ^a élément de 3Ka et une application <pa élément de 3 telles que ^a4-^o = l (1 désigne ici l'application constante égale à 1). Nous pouvons alors écrire : Yl(ll>a+<Pa) = l. a€E En développant ce produit, on trouve des termes qui sont tous dans l'idéal 3 , puisque (Va € E) cpa *G 3, sauf peut-être le terme Yi V>a > niais ce aeE terme est l'application nulle puisque (Va G E) Va(&) = 0- Nous pouvons déduire de ce qui précède que 1 G 3 et donc que 3 = A . Si Wl est un idéal maximal de l'anneau KE , il est nécessairement inclus dans l'un des idéaux maximaux Wla , donc égal à l'un d'entre eux, ce qu'il fallait démontrer. c) On suppose ici que E est un ensemble infini. Si / est un élément de KE , notons support (/) = {x G E \ f(x) ^ 0} . On voit facilement que le support de l'application nulle est 0 et que si f et g sont deux éléments quelconques de KE , support (/ x g) = support (/) n support (g), et support (/ 4- g) C support (/) U support (g). L'ensemble des applications de support fini est donc un idéal 3 de KE . Cet idéal 3 n'est inclus dans aucun des idéaux 3Ra puisque pour tout aeE, 6a G 3 \ 3Wa . L'idéal 3 n'est sans doute pas maximal, mais s'il est inclus dans un idéal maximal W, cet idéal maximal ne sera inclus dans aucun des %Ra , donc ne sera égal à aucun de ces idéaux. Il reste à démontrer la proposition suivante : Proposition : «Dans un anneau commutatif tout idéal strict est inclus dans un idéal maximal. ■ Le lecteur pourra d'abord se reporter à l'exercice 9 du chapitre 1.6. Considérons l'ensemble E des idéaux stricts de l'anneau A, ordonné par l'inclusion. Les idéaux maximaux de A sont les éléments maximaux de cet ensemble ordonné. Soit ^ une chaîne dans E , c'est-à-dire un ensemble non vide d'idéaux stricts de A, totalement ordonné par l'inclusion. Montrons que : J = |J / est un idéal de A . Cet ensemble n'est évidemment pas vide. Si x e J et a G A, alors il existe J G ^ tel que x G /, donc
48 Chapitre III Bases du calcul algébrique et combinatoire ax G /, donc ax G J. Si x G J et x' G J, il existe deux idéaux J G % et V e% tels que x £ I et x' G i7 ; comme est totalement ordonné par l'inclusion, Ici' ou i7 C J ; supposons par exemple / C i7, alors x et x' sont tous les deux éléments de l'idéal i7 donc x 4- 2/ aussi, donc x + y e J . L'ensemble J est donc bien un idéal de l'anneau A. Cet idéal J est strict, sinon 1 G J, donc 1 serait élément de l'un des idéaux stricts / où / G ^ , ce qui est impossible. Cet idéal est donc la borne supérieure de % , puisque c'est un majorant de % et que c'est le plus petit possible (pour l'inclusion). Toute chaîne dans l'ensemble E a une borne supérieure : l'ensemble E est par définition inductif. Le théorème de Zorn nous permet alors d'affirmer que cet ensemble ordonné possède au moins un élément maximal, ce qu'il fallait démontrer. Fin de la démonstration de la proposition. Reprenons les notations de l'exercice. Si E est infini, l'idéal de l'anneau KE dont les éléments sont les applications de support fini, qui est évidemment un idéal strict, est inclus dans un idéal maximal qui n'est aucun des idéaux Wia où a G E. L'application a »-> S)?a de E vers l'ensemble des idéaux maximaux de l'anneau KE n'est donc pas surjective. Exercice 7 : Pour qu'un sous-anneau A de Q soit partout dense (cf. exercice 6), il faut et il suffit que A D ]0,1[ ^ 0 . ■ Nous utiliserons les résultats de l'exercice 6. Si A est un sous-anneau de Q qui n'est pas partout dense, comme c'est un sous-groupe additif de Q , il existe a G Q>+ tel que A = aZ . Comme A est un sous-anneau, 1 G A donc a ^ 0 , d'où a > 0 ; de plus a2 G A, il existe donc un entier n > 0 tel que a2 = n - a , d'où a — n et A = nZ . Comme 1 G A , nécessairement n = 1, donc A = Z. Le seul sous-anneau de Q qui ne soit pas partout dense est donc Z. Tout sous-anneau de Q qui coupe l'intervalle ]0,1[ n'est pas Z et est donc partout dense. Inversement un sous-anneau de Q qui est dense coupe l'intervalle ]0,1[. L'équivalence est donc démontrée. Exercice 9 : On dit qu'un idéal 3 d'un anneau commutatif est primaire ssi, (V(x, y) G A2) (xy G 3 et x £ 3) ^ (3n G | yn G S). Montrer que la racine (cf. exercice 2) d'un idéal primaire est un idéal premier. Si 2)î est un idéal maximal de A , montrer que les puissances 3KP (p G f^J* ) de 3JZ sont des idéaux primaires ayant pour racine (voir l'exercice 4 pour la définition du produit
III. 7 Notion d'idéal d'un anneau commutatif 49 || d'idéaux). ■ Soit 3 un idéal primaire. Supposons que x et y soient des éléments de A tels que xy G V%. Il existe un entier m > 0 tel que xmym = (xy)m G S. Si x £ V% , nécessairement xm £ 3. Puisque l'idéal S est primaire, par définition il existe n > 0 tel que (ym)n = ymn G 3, donc y G \/3 . L'idéal \/3 est donc premier. Montrons d'abord qu'un idéal maximal est premier. Si 39? est un idéal maximal de l'anneau A, et x et y deux éléments de A tels que xy e M et x <^ 39?, l'idéal 39? 4- xA contient strictement 39? donc est égal à A . Il existe donc un élément a e A et un élément m G 39? tels que ax 4 m = 1. Nous en déduisons que y = axy 4- ray est élément de l'idéal 33?. L'idéal 39? est donc premier. Montrons ensuite que si 3 est un idéal premier, = 3 . En effet si x e a est tel que 3n G N*, xn G 3, alors x • x • ... • x G S. Par conséquent \/5 C 3 et finalement \/3 = S. Cette propriété est vraie aussi pour tout idéal maximal. Soit maintenant 39? un idéal maximal et p un entier > 0 . Comme 39?p C 39?, on voit que y/ffî? C \/3K = 39?. Démontrons l'inclusion opposée. Soit x G 39?, xp G 39?p, donc x G y/W?. Nous en déduisons 39? C et finalement 39Î = . Montrons que les idéaux 39?p sont primaires. Soient x et y des éléments de A tels que xy G 39?p et y £ 39? ; alors l'idéal Wfl+yA contient strictement 39? et est par conséquent égal à A ; il existe donc un élément a G A et un élément m G 39? tels que ay 4- m = 1 ; nous pouvons alors écrire x = axy 4- mx, ce qui prouve que x G 39? ; mais puisque x G 39?, alors x G 39?2 etc. ; on peut poursuivre ce raisonnement pour montrer que x G 39?p_1, puis, comme xy G 39?p et m G 39?, en déduire finalement x G 39?p. Par conséquent si xy G 39?p et x £ 39?p, alors y e 39? et yp G 39?p. L'idéal 39?p est donc primaire.
Chapitre IV NOTIONS D'ARITHMÉTIQUE §IV.l CONGRUENCES DANS Z, ANNEAUX Z /nz Exercice 2 : Il Calculer le reste mod(31) de (1986)10 000 , le reste mod(41) I de l'entier (51200)2l°°et le reste mod (17) de (1035 1 25)5642 . ■ On vérifie par division euclidienne que 1986 = 2 [31] donc (1986)10000 = 2ioooo [31]. or 25 = 1 [31], donc 210000 = (25)2000 = l2000 = 1 [31]. Nous avons démontré la relation (1986)10000 = 1 [31]. On vérifie par division euclidienne que 51200 = 32 = —9 [41] et que (-9)2 = 81 = -1 [41], donc 512004 = 1 [41]. Comme 4 divise 2100 , on voit comme ci-dessus que (51200)2l°° = 1 [41]. On vérifie par division euclidienne que 1035125 = 12 = —5 [17], puis que (-5)2 = 25 = 8 [17], (-5)4 = 64 = -4 [17] , (-5)8 = 16 = -1 [17], et enfin (—5)16 = 1 [17] (le petit théorème de Fermât donne ce résultat sans calcul ). On obtient facilement l'égalité 5642 = 16 x 352 -1-8 4-2, donc (1 035 1 25)5642 = (-5)5642 = (-5)8 x (-5)2 = (-1) x 8 = -8 = 9 [17]. Exercice 3 : Vérifier que 106 = 1 mod (7) et en déduire : £ 1010 =5 mod(7).« On vérifie que 1001 = 7 x 143, donc 103 = -1 [7] et 106 = 1 [7] . La classe de 10n modulo 7 ne dépend donc que de la classe de n modulo 6. Or 101 = 4 [6] , 102 = 16 = 4 [6] et on voit facilement que pour tout k 10 k entier > 0 , 10k =4 [6]. Tous les termes de la somme S = ^ 1010 sont donc congrus à 104 modulo 7, donc la somme est congrue à 105 = 102 x 103 modulo 7 . Donc S = 2 x (-1) = 5 [7].
IV. 1 Congruences dans Z, anneaux Z/n^ 51 Exercice 9 : Démontrer (Vn G M*) : a) 106n -h 103n - 2 ee 0 mod (111), b) 72n+1 - 48n - 7 ee 0 mod (288). ■ a) On voit que 103 = 9x111 + 1, donc 103 = 1 [111] . Par conséquent pour tout n G N , 106n + 103n - 2 ee l2n + ln - 2 ee 0 [111] . 6) On vérifie que pour tout n G N* : 72n+l _ 4gn _ 7 = 7^gn _ ^ _ 4gn = = 48 x (7(49n_1 + ... + 49 + 1) - n) . Comme 288 = 6 x 48, l'égalité de l'énoncé sera vraie si, et seulement si, 6 divise le nombre 7(49n_1 + ... + 49 + 1) — n, soit encore si, et seulement si, 7(49n_1 + ... + 49 + 1) ee n [6] . Comme 7 = 1 [6], cette relation est vraie. Exercice 11 : Démontrer : (Vn G N) a) 42" + 22n + 1 ee 0 mod (7) (Stifel) b) 22n + 15n - 1 ee 0 mod (9). ■ a) Posons pour n entier xn = 22n . On vérifie facilement que xo = 2 et que pour tout n entier, xn+i = x2 ; d'où x\ = 4, x2 = 16 ee 2 [7], X3 ee 4 [7] etc. Les classes modulo 7 des entiers xn sont donc alternativement 2 (si n est pair), et 4 (si n est impair) ; la classe modulo 7 de 42n + 22" = xn+i + xn est donc toujours celle de 2 + 4 ee — 1 [7] . Donc pour tout n G N , 42" + 22" +1 = 0 [7] . b) L'égalité est vraie pour n = 0. Pour tout n > 0, on voit que : 22n + 15n - 1 ee 22n - 1 - 3n [9] , et que 22n - 1 - 3n = 4n - 1 - 3n - 3 [(4n_1 + ... + 4 + 1) - n] . Par conséquent l'entier 22n + 15n - 1 sera divisible par 9 si, et seulement si 4n_1 + ... + 4 + 1 ee n [3] ; ce qui est évidemment vrai puisque 4 ee 1 [3] . Il Si 9 divise a3 + b3 + c3 , alors 3 divise a ou b ou c. ■ Exercice 14 :
52 Chapitre IV Notions d'arithmétique Ecrivons les entiers a , b et c sous la forme : a = 3qa 4- ra , 6 = 3qb 4 n>, c = 3qc 4- rc , où ra , n>, rc sont 0 , 1 ou —1. On voit que : a3 = (3ga -f raf = 27a3 4 27g2ra 4 9gar2 + r3 , donc : a3=r3a=ra [9]. Il en est de même pour b et pour c, donc : a3 + 63+c3 = ra4r64rc [9], Comme ra 4- n> 4- rc est compris entre —3 et 3 , l'entier a3 4 63 4 c3 est divisible par 9 si, et seulement si, ra 4- n> -h rc = 0. On voit que cela n'est possible que si {ra,7*6,rc} = {—1,0,1} . En particulier l'un des nombres est divisible par 3. Exercice 20 : Pour n G N , le nombre ^(^Jtj) n'est jamais divisible par k=0 5.B Soit dans l'anneau A = » la matrice x = ^ 0) ' ^n v^ne facilement que x2 = 3 • 1a • Le sous-espace vectoriel (sur le corps Z/rj j_ ) engendré par les matrices 1a et x est donc un sous-anneau commutatif B de l'anneau A . On vérifie que 3 n'est pas un carré modulo 5 , ce qui implique que l'anneau B est un corps. En effet, pour tous éléments a et b non tous les deux nuls de Z/52 on voit que (alA4-6x)(al^-6x) = (a2-362)lA ; comme 3 n'est pas un carré, l'élément a2 — 3b2 ne peut être nul et est donc inversible dans le corps Z/t> j_ ; par conséquent la matrice al^ -4 bx est inversible dans l'anneau B , d'inverse (a2 — 362)_1(al^ — bx). Dans la suite de l'exercice nous utiliserons seulement l'existence d'un corps B contenant Z/5 j , donc de caractéristique 5 , et d'un élément x de B tel que x2 = 3 = 8 = 23 . En utilisant la formule du binôme nous obtenons pour tout n entier : et de manière analogue :
IV. 1 Congruences dans Z, anneaux Z/n^ 53 Nous en déduisons : d+x)^1 - (i - x)2«^=2 ± (m %2k+i ■ /i=0 ^ ' Comme pour tout h entier x2h+1 = xx2h = x8h = x23h , nous voyons que pour tout n entier : (1 + X)2n+1 _ (1 _ x)2«+1 = g + 1^ ^ d'où, en notant u„ la classe modulo 5 de l'entier 5Z^3 Voi."*" / : fc=o V2* + V Un = -L[(l+*)^-(l-*)*«+!]. Posons pour n entier an = (1 -h x)2n et 6n = (1 — x)2n . Comme x est racine d'une équation du second degré, on devine que ces suites vérifient des relations de récurrence simples. En effet : (1 -h x)2 = 3 + 1 4- 2x = 2(2 4- x) et: (1 4 x)3 = 2(2 4- x)(l 4 x) = 2(2 4- Sx 4- 3) = 6x = x, donc (1 + x)6 = x2 = 3 . On voit alors que pour tout n entier : an+3 = (l+x)2n+6 = 3an. Un calcul analogue, en remplaçant x par — x, montre que la suite (bn) vérifie la même relation de récurrence, et il en est donc de même pour la suite (un). Donc si n = 3g -h r , où r G [0,2], alors un = u3q+r = 3qur . Bien que ce ne soit pas indispensable ici, on peut remarquer aussi que : (1 4 x)4 = x(l 4 x) = 3 4 x = 6(2 4- x) + 1 = 3(1 4- x)2 -h 1, et que par conséquent, pour tout n entier : Qn+2 = 3an+i 4 an. La suite (bn) vérifie aussi cette relation et il en est de même pour la suite On voit que uo = 1, u\ = 1, et u<i — 3 4 1 = 4. Il est alors clair que un n'est jamais nul, et donc que pour tout n G N l'entier 23k [ ? fc=0 \2fc + 1 n'est pas divisible par 5 .
54 Chapitre IV Exercice 21 : Notions d'arithmétique Soit A la somme des chiffres de 4 4444444 et B la somme des chiffres de A. Trouver la somme des chiffres de B ; la numération est la numération décimale. (Olympiades, 1975.) m Notons S(n) la somme des chiffres de l'entier n dans son écriture décimale. On sait que S(n) = n [9] (cf. preuve par 9 ) ; par conséquent 4444 = 16 ee 7 [9] et 44444444 ee 74444 [9]. D'autre part 72 ee 49 ee 4 [9] et 73 ee 28 ee 1 [9] . Comme 4444 ee 7 [9], on voit que 4444 ee 7 ee 1 [3]

References: l'article 40
 l'article 41
 §1
 §1
 §1
 §1
 §1
 §11
 §11
 §11
 §11
 §11
 §1
 § 1
 § 1
 §1
 §1
 §1
 §11
 §11
 §111
 §111
 §111
 §111