# Théorie des groupes/Exercices/Sous-groupes de Z, divisibilité dans N et dans Z
## Problème 1

a) Soit E un ensemble ordonné. On suppose que pour tous éléments x, y de E, la partie {x, y} de E admet une borne inférieure, qu'on désignera par ${\text{x}}\wedge {\text{y}}$, et une borne supérieure, qu'on désignera par ${\text{x}}\vee {\text{y}}$. (Un ensemble ordonné qui possède ces deux propriétés est dit ensemble réticulé) Prouver que les lois de composition dans E $(a,b)\mapsto a\wedge b$ et $(a,b)\mapsto a\vee b$ sont commutatives et associatives.
La commutativité de ces deux lois résulte immédiatement du fait que les ensembles {a, b} et {b, a} sont égaux. Prouvons que la loi $(a,b)\mapsto a\wedge b$ est associative. Il s'agit de prouver que pour tous éléments a, b, c de E,
    $(1)\qquad a\wedge (b\wedge c)=(a\wedge b)\wedge c.$
Le premier membre est le plus grand des minorants de $\{a,b\wedge c\}$. Un élément x de E est un minorant de $\{a,b\wedge c\}$ si et seulement si on a à la fois $\ x\leq a$ et $x\leq b\wedge c$. La condition $x\leq b\wedge c$ équivaut à ce qu'on ait à la fois $x\leq b$ et $x\leq c$. Donc un élément x de E est un minorant de $\{a,b\wedge c\}$ si et seulement si c’est un minorant de {a, b, c}. Ainsi,
    (2) le premier membre de (1), à savoir $a\wedge (b\wedge c)$, est la borne inférieure de {a, b, c}.
Par changement de notations, on en tire que $c\wedge (a\wedge b)$ est la borne inférieure de {c, a, b} = {a, b, c}. Puisque la loi $(x,y)\mapsto x\wedge y$ est commutative, cela revient à dire que
    (3) $(a\wedge b)\wedge c$ est la borne inférieure de {a, b, c}.
La comparaison de nos résultats (2) et (3) prouve notre thèse (1), donc la loi $(a,b)\mapsto a\wedge b$ est associative. Pour prouver que la loi $(a,b)\mapsto a\vee b$ est associative, on peut par exemple appliquer le résultat précédent à l’ordre opposé de l’ordre considéré sur E.
b) Aux hypothèses du point a), on ajoute que E admet un plus petit élément, soit m, et un plus grand élément, soit M. Montrer qu'alors E, muni de la loi $(a,b)\mapsto a\wedge b$, est un monoïde commutatif admettant M pour élément neutre et que E, muni de la loi $(a,b)\mapsto a\vee b$, est un monoïde commutatif admettant m pour élément neutre. Comme dans tout monoïde, on définit alors le composé d'un n-uplet (a$_1$, ... , a$_n$) d'éléments de E par récurrence sur n :
    $a_{1}\wedge \ldots \wedge a_{n}=M$ si n = 0 ;
    $a_{1}\wedge \ldots \wedge a_{n}=(a_{1}\wedge \ldots \wedge a_{n-1})\wedge a_{n}$ si n ≥ 1.
De même, pour la loi $\vee$ :
    $a_{1}\vee \ldots \vee a_{n}=m$ si n = 0 ;
    $a_{1}\vee \ldots \vee a_{n}=(a_{1}\vee \ldots \vee a_{n-1})\vee a_{n}$ si n ≥ 1.
Prouver que $a_{1}\wedge \ldots \wedge a_{n}$ est la borne inférieure et $a_{1}\vee \ldots \vee a_{n}$ la borne supérieure de $\{a_{1}\ldots a_{n}\}.$
Pour tout élément x de E, $x\wedge M$ est la borne inférieure de l’ensemble {x, M}. Cet ensemble admet x comme plus petit élément et donc comme borne inférieure, donc $x\wedge M=x$, ce qui montre que M est neutre pour la loi $\wedge$. On montre de même que m est neutre pour la loi $\vee .$ Compte tenu du point a), E est donc bien un monoïde commutatif pour les deux lois considérées.
Prouvons que pour tout nombre naturel n ≥ 0, $a_{1}\wedge \ldots \wedge a_{n}$ est la borne inférieure de {a$_1$, ... , a$_n$}. Pour n = 0, cela signifie que M est la borne inférieure de E, ce qui est vrai. (Si un ensemble ordonné admet un plus grand élément, cet élément est la borne inférieure de la partie vide dans E.) Supposons que n ≥ 1 et que notre thèse est vraie pour n - 1, et prouvons-la pour n. Par hypothèse de récurrence, $a_{1}\wedge \ldots \wedge a_{n-1}$ est la borne inférieure inf(a$_1$, ..., a$_{n-1}$) de {a$_1$, ... , a$_{n-1}$}, donc, vu notre définition de ${a_{1}\wedge \ldots \wedge a_{n}}$ par récurrence, $a_{1}\wedge \ldots \wedge a_{n}=inf(a_{1},\ldots a_{n-1})\wedge a_{n}$, autrement dit,
    (2) $a_{1}\wedge \ldots \wedge a_{n}$ est la borne inférieure de $\{inf(a_{1},\ldots a_{n-1}),a_{n}\},$
c'est-à-dire le plus grand minorant de {inf(a$_1$, ... , a$_{n-1}$), a$_n$}. Un élément x de E est un minorant de {inf(a$_1$, ... , a$_{n-1}$), a$_n$} si et seulement si on a à la fois x ≤ inf(a$_1$, ..., a$_{n-1}$) et x ≤ a$_n$. La condition x ≤ inf(a$_1$, ..., a$_{n-1}$) équivaut à ce que x soit inférieur ou égal à chacun des éléments a$_1$, ..., a$_{n-1}$, donc un élément x est un minorant de {inf(a$_1$, ... , a$_{n-1}$), a$_n$} si et seulement si c’est un minorant de {a$_1$, ... , a$_n$}. Dès lors, la borne inférieure de {inf(a$_1$, ... , a$_{n-1}$), a$_n$} est la borne inférieure de {a$_1$, ... , a$_n$}. Notre résultat (2) signifie donc que $a_{1}\wedge \ldots \wedge a_{n}$ est la borne inférieure de {a$_1$, ... , a$_n$} comme annoncé.
Par exemple en appliquant ce résultat à l’ordre opposé de l’ordre considéré sur E, on prouvera que $a_{1}\vee \ldots \vee a_{n}$ est la borne supérieure de {a$_1$, ... , a$_n$}.
c) Soient a$_1$, ... , a$_n$ des entiers rationnels. Retrouver à l'aide de ce qui précède la relation
    ppcm (a$_1$, ... , a$_n$) = ppcm (ppcm(a$_1$, ... , a$_{n-1}$), a$_n$),
démontrée dans la théorie.
Nous avons évidemment toujours $ppcm(c_{1},...,c_{1})=ppcm(\vert c_{1}\vert ,...,\vert c_{1}\vert )$, ce qui permet de se ramener au cas où les a$_i$ sont naturels. L'ensemble des nombres naturels, muni de la relation « divise », est un ensemble ordonné admettant 1 pour plus petit élément et 0 pour plus grand élément. Les points a) et b) s'appliquent à cet ensemble ordonné. En particulier, la loi de composition $(a,b)\mapsto a\vee b=ppcm(a,b)$ est associative et $a_{1}\vee \ldots \vee a_{n}$ est égal à la borne supérieure de {a$_1$, ... , a$_n$}. La relation $a_{1}\vee \ldots \vee a_{n}=(a_{1}\vee \ldots \vee a_{n-1})\vee a_{n}$ (qui a servi à définir le composé de plusieurs éléments) donne donc ppcm (a$_1$, ... , an) = ppcm (ppcm(a$_1$, ... , an-1), an), comme annoncé.
d) Un ensemble ordonné réticulé est dit distributif si les deux lois de composition $(a,b)\mapsto sup(a,b)$ et $(a,b)\mapsto inf(a,b)$ (où sup(a, b) et inf(a, b) désignent respectivement la borne supérieure et la borne inférieure de {a, b}) sont distributives l'une par rapport à l'autre. En fait, si une de ces deux lois est distributive par rapport à l'autre, la seconde est également distributive par rapport à la première. En effet, si par exemple $\lor$ est distributive par rapport à $\land$ alors
    $(a\land c)\lor (b\land c)=[a\lor (b\land c)]\land [c\lor (b\land c)]=(a\lor b)\land (a\lor c)\land c=(a\lor b)\land c$
donc $\land$ est distributive par rapport à $\lor$.
Prouver que tout ensemble totalement ordonné est un ensemble réticulé distributif.
Soient E un ensemble totalement ordonné. Pour tous éléments x, y de E, désignons par max{x, y} le plus grand des deux éléments x, y, et par min{x, y} le plus petit de ces deux éléments. Le plus grand élément d'une partie étant toujours la borne supérieure de cette partie, max{x, y} est la borne supérieure de {x, y}. De même, min{x, y} est la borne inférieure de {x, y}. Ceci montre que E est réticulé. Prouvons qu’il est distributif. Prouvons d’abord que la borne inférieure est distributive par rapport à la borne supérieure. Il s'agit de prouver que, pour tous éléments a, b et c de E,
    min{ a, max{b, c} } = max{ min{a, b}, min{a, c} }.
Cette relation étant symétrique en b et c, nous pouvons supposer b ≤ c. Alors max{b, c} = c, donc le premier membre de la thèse est égal à min{a, c} et la thèse revient à dire que min{a,b} ≤ min{a, c}, autrement dit que min{a, b} est inférieur ou égal à chacun des deux éléments a et c, ce qui est clair puisque min{a, b} est inférieur ou égal à a et à b, lequel est ≤ c.
Nous avons donc prouvé que dans un ensemble totalement ordonné, la borne inférieure est distributive par rapport à la borne supérieure. Comme noté dans l'énoncé, cela suffit à prouver que E est distributif.
e) Prouver que l’ensemble des nombres naturels, muni de la relation d'ordre « divise », est un ensemble réticulé distributif, autrement dit que le pgcd et le ppcm sont distributifs l'un par rapport à l'autre. (Indication : utiliser le point d) et la décomposition en facteurs premiers.)
On esquissera seulement la démonstration. (Pour une autre méthode, voir cet exercice de la leçon sur les anneaux.) Posons $a\wedge b=\mathrm {pgcd} (a,b)$ et $a\vee b=\mathrm {ppcm} (a,b)$. Prouvons que le pgcd est distributif par rapport au ppcm. Le pgcd étant commutatif, il suffit de prouver que pour tous nombres naturels a et b,
    $a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c).$
Le cas où un des nombres a, b, c est nul se traite facilement à part. Nous pouvons donc supposer qu'a, b et c sont tous trois non nuls. Pour tout nombre naturel non nul x et pour tout nombre premier p, désignons par $\ v_{p}(x)$ le plus grand nombre naturel $\ v\geq$ 0 tel que $\ p^{v}$ divise x. De l’existence et de l'unicité de la décomposition en facteurs premiers, on tire
    $x=\prod _{p\in P}p^{v_{p}(x)},$
où P désigne l’ensemble des nombres premiers. (Le fait que le produit soit indexé par un ensemble infini ne pose pas de problème car les nombres premiers p pour lesquels v$_p$(x) n’est pas nul sont en nombre fini.) On montre facilement que si a et b sont deux nombres naturels non nuls,
    $a\wedge b=\prod _{p\in P}p^{min\{v_{p}(a),v_{p}(b)\}}$
et
    $a\vee b=\prod _{p\in P}p^{max\{v_{p}(a),v_{p}(b)\}}$
La distributivité de $\wedge$ et de $\vee$ l'une par rapport à l'autre se déduit alors facilement de la distributivité de max et de min dans un ensemble totalement ordonné (point d) ), l’ensemble totalement ordonné étant ici l’ensemble des nombres naturels muni de la relation d'ordre usuelle.

## Problème 2 (Théorème chinois)

a) Soient a, b et c des entiers rationnels. Montrer que pour qu’il existe un entier rationnel x tel que
    $ax\equiv b{\pmod {c}}$
il faut et il suffit que b soit divisible par le pgcd de a et c.
Sil existe un entier rationnel x tel que
    $ax\equiv b{\pmod {c}},$
alors b = ax + cr pour un certain entier rationnel r, donc b est clairement divisible par le pgcd de a et c. Réciproquement, supposons que b soit divisible par le pgcd de a et c. Soit d ce pgcd. Il existe donc un entier rationnel s tel que b = sd. D'autre part, d’après le théorème de Bézout, il existe des entiers rationnels t et u tels que ta + uc = d. En multiplianr par s, nous trouvons sta + suc = b, d'où
    $sta\equiv b{\pmod {c}}$
d'où
    $ax\equiv b{\pmod {c}}$
avec x =st.
b) (Théorème chinois) Soient m$_1$, ... , m$_n$ des entiers naturels et a$_1$, ... , a$_n$ des entiers rationnels. On suppose que pour tous indices i, j distincts,
    $\qquad a_{i}\equiv a_{j}{\pmod {\mathrm {pgcd} (m_{i},m_{j})}}.$
Prouver qu’il existe un entier rationnel a tel que, pour tout i (1 ≤ i ≤ n),
    $\qquad a\equiv a_{i}{\pmod {m_{i}}}.$
(Raisonner par récurrence sur n.)
Prouvons-le d’abord dans le cas particulier n = 2. Il s'agit de prouver que si m$_1$ et m$_2$ sont des nombres naturels, si a$_1$ et a$_2$ sont des entiers rationnels tels que
    $(1)\qquad a_{1}\equiv a_{2}{\pmod {\mathrm {pgcd} (m_{1},m_{2})}},$
il existe un entier rationnel a tel que
    $a\equiv a_{1}{\pmod {m_{1}}}$
et
    $a\equiv a_{2}{\pmod {m_{2}}}.$
D'après l'hypothèse (1), a$_1$ - a$_2$ est divisible par pgcd(m$_1$, m$_2$), donc, d’après le point a), il existe un entier rationnel x tel que
    $a_{1}-a_{2}\equiv xm_{1}{\pmod {m_{2}}},$
autrement dit, il existe des entiers rationnels x et y tels que
    $\ a_{1}-a_{2}=xm_{1}+ym_{2}.$
On a alors a$_1$ - x m$_1$ = a$_2$ + y m$_2$, donc la valeur commune de a$_1$ - x m$_1$ et a$_2$ + y m$_2$ convient pour a.
Nous avons donc démontré l'énoncé dans le cas particulier où n = 2. Passons au cas général. L'énoncé est banalement vrai si n = 0. Soit n un nombre naturel ≥ 1. Supposons l'énoncé vrai pour n - 1 (hypothèse de récurrence) et prouvons-le pour n. Par hypothèse de récurrence, nous pouvons choisir un entier rationnel b tel que
    $b\equiv a_{1}{\pmod {m_{1}}}$
    $b\equiv a_{n-1}{\pmod {m_{n-1}}}.$
Pour démontrer l'énoncé, il suffit clairement de prouver qu’il existe un entier rationnel a tel que
    $a\equiv b{\pmod {\mathrm {ppcm} (m_{1},\ldots m_{n-1})}}$
et
    $a\equiv a_{n}{\pmod {m_{n}}}.$
Puisque nous avons démontré l'énoncé dans le cas particulier où n = 2, il suffit de prouver que
    $a_{n}\equiv b{\pmod {\mathrm {pgcd} (m_{n},\mathrm {ppcm} (m_{1},\ldots m_{n-1}))}}.$
Puisque le pgcd est distributif par rapport au ppcm, nous avons
    $\mathrm {pgcd} (m_{n},\mathrm {ppcm} (m_{1},\ldots m_{n-1}))=\mathrm {ppcm} (\mathrm {pgcd} (m_{1},m_{n}),\ldots ,\mathrm {pgcd} (m_{n-1},m_{n})),$
donc il s'agit de prouver que
    $a_{n}\equiv b{\pmod {\mathrm {ppcm} (\mathrm {pgcd} (m_{1},m_{n}),\ldots ,\mathrm {pgcd} (m_{n-1},m_{n}))}}.$
Ceci revient à prouver que
    $a_{n}\equiv b{\pmod {\mathrm {pgcd} (m_{i},m_{n})}}$
pour chaque i (1 ≤ i ≤ n-1). Cette congruence résulte du fait qu'a$_n$ et b sont tous deux congrus à a$_i$ modulo pgcd(m$_i$, m$_n$). (Pour a$_n$, c’est vrai d’après les hypothèses de l'énoncé ; pour b, cela résulte clairement du choix de b.)
c) Prouver que si a est un entier rationnel satisfaisant aux conditions du point b), un entier rationnel a' satisfait à ces conditions si et seulement s'il est congru à a modulo le ppcm des m$_i$.
Soit a' un entier rationnel. Dire que, pour tout i, $a'\equiv a_{i}{\pmod {m_{i}}}$ équivaut à dire que pour tout i, $a'\equiv a{\pmod {m_{i}}}$, autrement dit que pour tout i, a - a' est divisible par m$_i$, ce qui équivaut à ce qu'a - a' soit divisible par le ppcm des m$_i$, d'où l'énoncé.
d) Soient m$_1$, ..., m$_n$ des nombres naturels premiers entre eux deux à deux, soient a$_1$, ..., a$_n$ des entiers rationnels. Prouver qu’il existe au moins un entier rationnel a tel que, pour tout i (1 ≤ i ≤ n),
    $a\equiv a_{i}{\pmod {m_{i}}}.$
C'est évidemment un cas particulier du théorème chinois. À titre de curiosité, on va donner une démonstration différente de celle qui a été donnée dans le cas général.
L'énoncé étant banal si n = 0, nous pouvons supposer n ≥ 1. Posons
    $M=\prod _{1\leq i\leq n}M_{i}$
et, pour chaque i (1 ≤ i ≤ n),
    $M_{i}=\prod _{j\not =i}m_{j},$
où j parcourt les éléments de {1, ..., n} distincts de i. Par hypothèse, les m$_j$ qui interviennent dans le produit M$_i$ sont premiers avec m$_i$, donc (théorie) leur produit M$_i$ est premier avec m$_i$.
Prouvons que les M$_i$ sont premiers entre eux dans leur ensemble. Supposons que, par absurde, p soit un diviseur premier commun à tous les M$_i$. Puisque nous supposons n ≥ 1, p divise au moins un M$_i$ et divise donc (lemme d'Euclide) un facteur m$_j$ de M$_i$. Puisque M$_j$ est premier avec m$_j$, il n'est donc pas divisible par p, ce qui contredit nos hypothèses sur p. Cette contradiction prouve que les M$_i$ sont premiers entre eux dans leur ensemble.
Soit i un indice dans {1, ... , n}. Puisque M$_i$ est premier avec m$_i$, il existe, d’après le point a), un entier rationnel b$_i$ tel que
    $(1)\qquad b_{i}M_{i}\equiv a_{i}{\bmod {m}}_{i}.$
Posons
    $a=b_{1}M_{1}+\ldots +b_{n}M_{n}.$
Pour chaque indice i, tous les termes b$_j$M$_j$ pour j ≠ i, sont divisibles par m$_i$ (car M$_j$ est divisible par m$_i$), donc, pour chaque i (1 ≤ i ≤ n), a est congru à b$_i$M$_i$ modulo m$_i$, d'où la thèse en vertu de (1).

## Problème 3

Soient $m,n\in \mathbb {N} ^{*}$ et $\pi :\mathbb {Z} \to \mathbb {Z} /m\mathbb {Z} \times \mathbb {Z} /n\mathbb {Z} ,\;x\mapsto (x{\bmod {m}},x{\bmod {n}})$.
* Montrer que $\ker \pi =\langle \operatorname {ppcm} (m,n)\rangle$.
* À quelle condition sur $m$ et $n$ le morphisme $\pi$ est-il surjectif ?
* $\pi (x)=(0{\bmod {m}},0{\bmod {n}})$ si et seulement si $x$ est divisible par $m$ et par $n$, c'est-à-dire par $\operatorname {ppcm} (m,n)$.
* $\pi$ est surjectif si et seulement si l'injection de $\mathbb {Z} /\ker \pi \to \mathbb {Z} /m\mathbb {Z} \times \mathbb {Z} /n\mathbb {Z}$ qu'il induit l'est, donc si et seulement si $\mathbb {Z} /\ker \pi$ et $\mathbb {Z} /m\mathbb {Z} \times \mathbb {Z} /n\mathbb {Z}$ ont même cardinal. D'après la question 1, cela équivaut à $\operatorname {ppcm} (m,n)=mn$ donc à $\operatorname {pgcd} (m,n)=1$.

## Problème 4 (Tout sous-groupe d'indice premier est maximal)

Soit G un groupe, soit H un sous-groupe d'indice (fini) premier de G. Prouver que H est un sous-groupe maximal de G.
Soit K un sous-groupe de G tel que $H\leq K\leq G$ ; il s'agit de prouver que K est égal à H ou à G. D'après la formule des indices, [G:H] = [G:K] [K:H]. Puisque le membre gauche est un nombre premier, un des deux facteurs du membre droit est égal à 1, ce qui revient à dire que K est égal à G ou à H.