Groupe (mathématiques)/Exercice/Sous-groupes de Z, divisibilité dans N et dans Z

Une page de Wikiversité.

**Sous-groupes de Z, divisibilité dans N et dans Z**
Leçon : Groupe (mathématiques)

Exercice 5
Chapitre du cours :	Sous-groupes de Z, divisibilité dans N et dans Z
Cet exercice est de niveau 13.

En raison de limitations techniques, la typographie souhaitable du titre, « Exercice : Sous-groupes de Z, divisibilité dans N et dans Z
Groupe (mathématiques)/Exercice/Sous-groupes de Z, divisibilité dans N et dans Z », n'a pu être restituée correctement ci-dessus.

[modifier] Problème 1 (Facile)

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 $a \wedge b$ , et une borne supérieure, qu'on désignera par $a \vee b$ . (Un ensemble ordonné qui possède ces deux propriétés est dit ensemble réticulé^[1]) 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.

Solution

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₁, ... , 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}\}.$

Solution

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₁, ... , 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₁, ..., a_n-1) de {a₁, ... , 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₁, ... , a_n-1), a_n}. Un élément x de E est un minorant de {inf(a₁, ... , a_n-1), a_n} si et seulement si on a à la fois x ≤ inf(a₁, ..., a_n-1) et x ≤ a_n. La condition x ≤ inf(a₁, ..., a_n-1) équivaut à ce que x soit inférieur ou égal à chacun des éléments a₁, ..., a_n-1, donc un élément x est un minorant de {inf(a₁, ... , a_n-1), a_n} si et seulement si c'est un minorant de {a₁, ... , a_n}. Dès lors, la borne inférieure de {inf(a₁, ... , a_n-1), a_n} est la borne inférieure de {a₁, ... , a_n}. Notre résultat (2) signifie donc que $a_{1} \wedge \ldots \wedge a_{n}$ est la borne inférieure de {a₁, ... , 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₁, ... , a_n}.

c) Soient a₁, ... , an des entiers rationnels. Retrouver à l'aide de ce qui précède la relation

ppcm (a₁, ... , an) = ppcm (ppcm(a₁, ... , an-1), an),

démontrée dans la théorie.

Solution

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₁, ... , 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₁, ... , an) = ppcm (ppcm(a₁, ... , 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. Prouver que tout ensemble totalement ordonné est un ensemble réticulé distributif.

Solution

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. Pour prouver que la borne supérieure est distributive par rapport à la borne inférieure, on peut par exemple appliquer le résultat précédent à l'ordre opposé à l'ordre considéré sur E.

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.)

Solution

On esquissera seulement la démonstration. 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 que 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.

[modifier] Problème 2 (Théorème chinois)

a) Soient a, b et c des entiers rationnels. Montrer que pour qu'il exite 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.

Solution

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₁, ... , m_n des entiers naturels et a₁, ... , 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.)

Solution

Prouvons-le d'abord dans le cas particulier n = 2. Il s'agit de prouver que si m₁ et m₂ sont des nombres naturels, si a₁ et a₂ 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₁ - a₂ est divisible par pgcd(m₁, m₂), 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₁ - x m₁ = a₂ + y m₂, donc la valeur commune de a₁ - x m₁ et a₂ + y m₂ 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 que 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.

Solution

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 que a - a' soit divisible par le ppcm des m_i, d'où l'énoncé.

d) Soient m₁, ..., m_n des nombres naturels premiers entre eux deux à deux, soient a₁, ..., 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}}.$

Solution

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_jM_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_iM_i modulo m_i, d'où la thèse en vertu de (1).

[modifier] Références

↑ N. Bourbaki, Théorie des ensembles. Chapitres 1 à 4, Paris, Masson, 1998, ch. III, § 1, n° 11, p. 13.

[0] N. Bourbaki, Théorie des ensembles. Chapitres 1 à 4, Paris, Masson, 1998, ch. III, § 1, n° 11, p. 13.

[1]

Groupe (mathématiques)/Exercice/Sous-groupes de Z, divisibilité dans N et dans Z

Une page de Wikiversité.

[modifier] Problème 1 (Facile)

[modifier] Problème 2 (Théorème chinois)

[modifier] Références

Affichages

Outils personnels

Rechercher

Navigation

Contribuer

Imprimer / exporter

Boîte à outils