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

Une page de Wikiversité.

Sommaire 1 Rappels de terminologie 2 Sous-groupes de Z 3 Théorèmes de divisibilité dans N et dans Z 3.1 Plus grand commun diviseur 3.2 Plus grand commun multiple 3.3 Nombres premiers

[modifier] Rappels de terminologie

Rappelons que si a et b sont des nombres naturels, on dit que a divise b, ou encore que a est (un) diviseur de b, ou encore que b est divisible par a, ou encore que b est (un) multiple de a, s'il existe un nombre naturel c tel que b = ac. On écrit souvent pour exprimer que a divise b. La relation «divise» est une relation d'ordre dans N. Si un nombre naturel a divise un nombre naturel b et que b n'est pas nul, alors pour la relation d'ordre usuelle dans N.
Si a et b sont maintenant des entiers rationnels, nous dirons de même que a divise b, ou encore que a est (un) diviseur de b, ou encore que b est divisible par a, ou encore que b est (un) multiple de a, s'il existe un entier rationnel c tel que b = ac. On vérifie facilement que si a et b sont naturels, a divise b selon la seconde définition si et seulement s'il le divise suivant la première. La relation «divise» est une relation de préordre dans Z. (Elle est réflexive et transitive, mais non antisymétrique, deux éléments de Z se divisant l'un l'autre si et seulement s'ils sont égaux ou opposés.)

[modifier] Sous-groupes de Z

Nous avons vu qu'un groupe est dit monogène s'il est engendré par un seul élément et que le sous-groupe (monogène) d'un groupe G engendré par un élément a de G est l'ensemble des éléments de G de la forme aⁿ, n parcourant .

Soit a un entier rationnel. Le sous-groupe de engendré par a est l'ensemble des éléments de de la forme na avec . Puisque la multiplication dans est commutative, c'est aussi l'ensemble des éléments de de la forme an avec . Nous noterons le sous-groupe <a> de engendré par a. Pour exprimer que deux éléments x, y de Z sont congrus modulo le sous-groupe aZ de Z, ce qui revient à dire que la différence de x et y est divisible par a, nous écrirons . Il est clair que si a = 1, alors aZ = 1Z = Z, donc Z est monogène, avec l'élément 1 pour générateur. Nous allons montrer que tous les sous-groupes de sont du type aZ, autrement dit sont monogènes.

Proposition

Soit n un nombre naturel > 0. Les n éléments r de tels que forment une transversale du sous-groupe de , autrement dit un système de représentants de pour la relation d'équivalence .

Démonstration. Il s'agit de prouver que tout élément x de est congru modulo n à un et un seul des nombres naturels . Prouvons d'abord que x est congru à un au moins de ces nombres. Si x est positif, cela résulte du principe de division euclidienne dans . Si x est négatif et divisible par n, il est congru à 0 modulo n et notre thèse est vraie. Si x est négatif et non divisible par n, le nombre naturel -x est congru modulo n à un nombre s parmi ; alors x est congru modulo n au nombre n-s, qui est dans la série , et notre thèse est encore vraie.
Prouvons maintenant que x n'est congru modulo n dans qu'à un des nombres . Il revient au même de prouver que si , r et s ne sont pas congrus entre eux modulo n dans . Dans le cas contraire, nous avons s-r = qn, avec . Puisque r et s sont distincts, q n'est pas nul, donc ou . Dans le premier cas, qn est au moins égal à n et ne peut donc pas être égal à s-r; dans le second cas, qn est négatif et ne peut donc pas non plus être égal à s-r.

Corollaire

Soit n un nombre naturel > 0. Le groupe quotient est d'ordre n.

Proposition

Soit H un sous-groupe de Z. Il existe un et un seul nombre naturel tel que H = aZ.

Démonstration. Prouvons d'abord l'existence de a. Si H est nul, notre thèse est vraie avec a = 0. Nous pouvons donc supposer H non nul. Alors H comprend un élément n tel que n < 0 ou n > 0. Si n < 0, alors -n, qui appartient lui aussi à H, est > 0. Donc H comprend au moins un élément > 0. Soit a le plus petit nombre naturel > 0 appartenant à H; prouvons que H = aZ. Puisque a appartient à H, aZ est contenu dans H (minimalité du sous-groupe engendré). Prouvons l'inclusion réciproque . Soit b un élément de H; il s'agit de prouver que b appartient à aZ. Nous avons vu que b (comme tout élément de Z) est congru modulo a à un nombre r parmi . Nous avons alors r = b - na, avec . Puisque b appartient à H par hypothèse et que, comme nous l'avons vu, est contenu dans H, r appartient à H. Si r n'était pas nul, la minimalité de a serait contredite (puisque ), donc r est nul, donc l'égalité r = b - na donne b = na, donc b appartient à aZ comme annoncé.
Nous avons donc prouvé l'existence d'un a tel que dans l'énoncé. Prouvons son unicité. Soit a₁ un nombre naturel tel que ; il s'agit de prouver que a₁ = a. On peut dire par exemple que a et a₁ sont deux nombres naturels multiples l'un de l'autre dans Z et que, comme on le montre facilement, deux nombres naturels ne sont multiples l'un de l'autre dans Z que s'ils sont égaux. On peut aussi régler à part le cas où H est nul et noter que si H n'est pas nul, alors, d'après un corollaire ci-dessus, a est l'indice de H dans Z, d'où l'unicité de a.

[modifier] Théorèmes de divisibilité dans N et dans Z

[modifier] Plus grand commun diviseur

Théorème

Soient a1, ... , an des entiers rationnels. Il existe un et un seul nombre naturel d qui est diviseur commun de a1, ... , an et multiple de tous leurs diviseurs communs.

Puisque le groupe (additif) Z est commutatif, a₁Z + ... + a_nZ est un sous-groupe de Z et est donc de la forme dZ pour un certain nombre naturel d. Puisque a₁, ... , a_n et appartiennent à dZ, d est un diviseur commun de a₁, ... , a_n. Puisque d appartient à a₁Z + ... + a_nZ, il existe des entiers rationnels c₁, ... , c_n tels que a₁ c₁ + ... + a_n c_n = d. Il en résulte clairement que si d' est un diviseur commun de a₁, ... , a_n, d' divise d. Nous avons donc prouvé l'existence d'un nombre naturel d tel que dans l'énoncé. Un tel nombre naturel d doit être unique, car c'est le plus grand des diviseurs naturels communs de a₁, ... , a_n relativement à la relation d'ordre «divise» dans N.

Remarque. Si d n'est pas nul, c'est-à-dire si a et b ne sont pas tous deux nuls, d est aussi le plus grand des diviseurs naturels communs de a et b pour la relation d'ordre usuelle dans N.

Définition

Si a1, ... , an sont des entiers rationnels, on appelle plus grand commun diviseur de a1, ... , an, en abrégé pgcd de a1, ... , an, et on note pgcd(a1, ... , an) l'unique nombre naturel qui divise tous les nombres a1, ... , an et est multiple de tous leurs diviseurs communs.

Théorème de Bézout (ou de Bachet-Bézout) dans les entiers rationnels

Soient a1, ... , an des entiers rationnels, d leur pgcd. Il existe des entiers rationnels c1, ... , cn tels que a1 c1 + ... + an cn = d.

Démonstration. Cela résulte de la démonstration du théorème précédent.

Corollaire. Théorème de Bachet-Bézout dans les nombres naturels.

Soient a et b deux nombres naturels non nuls, d leur pgcd. Il existe des nombres naturels x et y tels que ax - d = by.

D'après le théorème de Bachet-Bézout, il existe des entiers rationnels u et v tels que au - d = bv. On sait qu'un nombre naturel non nul admet des multiples aussi grands qu'on veut (par exemple, un nombre naturel non nul r admet le multiple r(s+1) > s), donc, puisque ab est un nombre naturel non nul, il existe un nombre naturel n tel que abn > d - au. La relation au - d = bv donne a(u + bn) - d = b(v + an), où, vu notre choix de n, le premier membre est positif. Puisque a, b et d sont tous trois > 0, on en tire que u + bn et v + an sont naturels, d'où l'énoncé.

Définition

On dit que deux entiers rationnels a et b sont premiers entre eux (ou encore que l'un est premier avec l'autre) s'ils n'ont pas d'autre diviseur naturel commun que l'unité.

Cela revient évidemment à dire que a et b n'ont pas d'autre diviseur commun dans Z que 1 et - 1. Il est clair que cela revient aussi à dire que le pgcd de a et b est égal à 1.

Définition

Soient a1, ... , an des entiers rationnels. On dit que ces nombres sont premiers entre eux dans leur ensemble si le seul nombre naturel qui les divise tous est 1. On dit que ces nombres sont premiers entre eux deux à deux si pour tous indices i et j distincts, ai et aj sont premiers entre eux.

Théorème

Soient a et b deux nombres naturels, d leur pgcd. Alors a = da' et b = db', où a' et b' sont des nombres naturels premiers entre eux.

Si d = 0 (c'est-à-dire si a et b sont tous deux nuls), on peut faire a' = b' = 1 et l'énoncé est vrai dans ce cas. Supposons maintenant d > 0. Soient a' et b' les entiers naturels (définis de manière unique) tels que a = da' et b = db'. Il s'agit de prouver que a' et b' sont premiers entre eux. Dans le cas contraire, ils admettraient un diviseur naturel d' distinct de 1. Alors dd' serait un diviseur commun de a = da' et de b = db' et serait strictement plus grand que d pour la relation «divise», ce qui contredit le fait que d est le pgcd de a et b.

Lemme de Gauss

Soient a et b deux entiers rationnels premiers entre eux. Si c est un entier rationnel tel que a divise bc, a divise c.

Démonstration. Puisque a et b sont premiers entre eux, leur pgcd est égal à 1. D'après le théorème de Bachet-Bézout, il existe donc des entiers rationnels r et s tels que ar + bs = 1. D'autre part, puisque a divise bc, il existe un entier rationnel x tel que ax = bc. En multipliant cette égalité par s, nous trouvons axs = bsc. En remplaçant dans cette égalité bs par 1 - ar, nous obtenons axs = c - arc, c = a(xs + rc), donc a divise bien c.

Corollaire

Soient a, b1, ... , bn des entiers rationnels. Si a est premier avec chacun des nombres b1, ... , bn, il est premier avec leur produit.

Démonstration. C'est banalement vrai pour n = 0. Soit n ≥ 1. Supposons que l'énoncé soit vrai pour n - 1 et prouvons qu'il est vrai pour n. Soit d un diviseur naturel commun à a et à b₁ ... b_n. Il s'agit de prouver que d = 1. Puisque d divise a, il est clair que d est premier avec chacun des nombres b₁, ... , b_n. Puisque d divise le produit de b₁ ... b_n-1 par b_n et est premier avec b_n, il résulte du lemme de Gauss que d divise b₁ ... b_n-1. Mais, par hypothèse de récurrence, d est premier avec b₁ ... b_n-1, donc d = 1, comme annoncé.

[modifier] Plus grand commun multiple

Théorème

Soient a1, ... , an, avec n ≥ 0, des entiers rationnels. Il existe un et un seul nombre naturel m qui est multiple commun de a1, ... , an et divise tous leurs multiples communs.

Démonstration. Si n = 0, tout entier rationnel est multiple commun de a₁, ... , a_n, donc m = 1 convient. Soit maintenant n ≥ 1. Nous pouvons alors parler de l'intersection des sous-groupes a₁Z, ... , a_nZ de Z. Cette intersection est un sous-groupe de Z et est donc de la forme mZ pour un certain nombre naturel m. Puisque m appartient à chacun des sous-groupes a₁Z, ... , a_nZ de Z, il est multiple commun de a₁, ... , a_n. D'autre part, si m' est un multiple commun de a₁, ... , a_n, il appartient à chacun des sous-groupes a₁Z, ... , a_nZ, donc il appartient à leur intersection mZ, donc il est divisible par m. Nous avons donc prouvé l'existence d'un nombre naturel m tel que dans l'énoncé. Un tel nombre naturel m doit être unique, car c'est le plus petit des multiples naturels communs de a₁, ... , a_n relativement à la relation d'ordre «divise» dans N.

Définition

Si a1, ... , an sont des entiers rationnels, on appelle plus petit commun multiple de a1, ... , an, en abrégé ppcm de a1, ... , an, et on note ppcm(a1, ... , an) l'unique nombre naturel qui est multiple de tous les nombres a1, ... , an et divise tous leurs multiples communs.

Remarque. Le produit de a₁, ... , a_n étant un multiple commun de a₁, ... , a_n, il est multiple de leur ppcm.

Théorème

Soient a1, ... , an, avec n ≥ 0, des entiers rationnels. Un entier rationnel est multiple commun de a1, ... , an si et seulement s'il est multiple de leur ppcm.

Démonstration. Soit m le ppcm de a₁, ... , a_n. Si un entier rationnel M est multiple de m, il est évidemment multiple de chacun des nombres a₁, ... , a_n (transitivité de la relation « divise »). Réciproquement, si un entier rationnel M est multiple de chacun des nombres a₁, ... , a_n, il est multiple de m par définition du ppcm.

Lemme

Soient a1, ... , an, avec n ≥ 1, des entiers rationnels, soit i un indice tel que 1 ≤ i ≤ n. Le ppcm de a1, ... , an est égal au ppcm de ppcm(a1, ... , ai) et de ppcm(ai+1, ... an). En particulier, le ppcm de a1, ... , an est égal au ppcm de ppcm(a1, ... , an-1) et de an.

Démonstration. D'après le théorème précédent,

(1) les multiples naturels du ppcm de ppcm(a₁, ... , a_i) et de ppcm(a_i+1, ... a_n) sont les multiples naturels communs de ppcm(a₁, ... , a_i) et de ppcm(a_i+1, ... a_n).

Toujours d'après le précédent théorème, les multiples naturels de ppcm(a₁, ... , a_i) sont les multiples naturels communs de a₁, ... , a_i et les multiples naturels de ppcm(a_i+1, ... a_n sont les multiples naturels communs de a_i+1, ... , a_n. Notre assertion (1) signifie donc que l'ensemble des multiples naturels du ppcm de ppcm(a₁, ... , a_i) et de ppcm(a_i+1, ... a_n) est égal à l'ensemble des multiples naturels communs de a₁, ... , a_n. En exprimant que ces deux ensembles ont le même plus petit élément pour la relation « divise», nous obtenons l'énoncé.

Remarque. Le lemme qui précède peut être considéré comme une propriété d'associativité du ppcm. Voir les exercices.

Théorème

Si a1, ... , an sont des nombres naturels premiers entre eux deux à deux, leur ppcm est leur produit.

Démonstration. Prouvons-le d'abord pour n = 2. Soit m le ppcm de a₁ et a₂. Soit m = a₁m', avec m' entier rationnel. Puisque a₂ divise m, c'est-à-dire divise a₁m', et est premier avec a₁, il résulte du lemme de Gauss que a₂ divise m'. Puisque m = a₁m', il en résulte que a₁a₂ divise m. D'autre part, a₁a₂ est évidemment un multiple commun de a₁ et a₂, donc m divise a₁a₂. Ainsi, m et a₁a₂ sont deux nombres naturels qui se divisent l'un l'autre, donc ils sont égaux. Ceci démontre l'énoncé dans le cas n = 2.
Passons au cas général. L'énoncé est banalement vrai si n = 0. Soit n ≥ 1. Supposons l'énoncé vrai pour n - 1 et prouvons-le pour n. Soient a₁, ... , a_n des nombres naturels premiers entre eux deux à deux. D'après un théorème précédent, ppcm(a₁, ... , a_n) est le ppcm de ppcm(a₁, ... , a_n-1) et de a_n. Par hypothse de récurrence, ppcm(a₁, ... , a_n-1) = a₁ ... a_n-1, donc

(1) ppcm(a₁, ... , a_n) est le ppcm de a₁ ... a_n-1 et de a_n.

Puisque a_n est premier avec chacun des nombres a₁, ... , a_n-1, il résulte d'un théorème précédent qu'il est premier avec leur produit. Donc, puisque l'énoncé est démontré dans le cas n = 2, le ppcm de a₁ ... a_n-1 et de a_n est a₁ ... a_n-1 a_n. La relation (1) ci-dessus entraîne donc l'énoncé.

Théorème

Si a, b, c sont des nombres naturels, ppcm(ab, ac) = a ppcm(b, c).

Démonstration. Le cas a = 0 étant banal, nous supposerons a non nul. Dans ce cea, si x et y sont des nombres naturels et que ax est multiple de ay, x doit être multiple de y. Pour prouver que ppcm(ab, ac) = a ppcm(b, c), il s'agit de prouver que
1° a ppcm(b, c) est un multiple commun de ab et de ac;
2° a ppcm(b, c) divise tous les multiples communs de ab et de ac.
Il est clair que 1° est vraie. Prouvons 2°. Soit m un multiple commun de ab et de ac. Il s'agit de prouver que m est multiple de a ppcm(b, c). Il est clair que m est multiple de a. Posons m = am', avec m' naturel. Alors am' est multiple commun de ab et de ac. Puisque 'nous supposons a non nul, m' est donc multiple commun de b et de c, donc m' est multiple de ppcm(b, c), donc am' (autrement dit m) est multiple de a ppcm(b, c), ce qui est notre thèse.

Théorème

Soient a, b des nombres naturels, d leur pgcd et m leur ppcm. Alors dm = ab.

Démonstration. L'énoncé est banal si d est nul (c'est-à-dire si a et b sont tous deux nuls), donc nous supposerons d non nul. Alors a = da' et b = db', où a' et b' sont des nombres naturels premiers entre eux. D'après le théorème précédent, m = d ppcm(a', b'). Puisque a' et b' sont premiers entre eux, leur ppcm est leur produit, donc d'où l'énoncé.

Corollaire

Soient a et b deux nombres naturels non nuls. Si a et b ne sont pas premiers entre eux, ppcm(a, b) < ab.

Démonstration. Si a et b ne sont pas premiers entre eux, leur pgcd d est >1. D'après le théorème précédent, ppcm(a, b) = a b / d, donc ppcm(a, b) < ab.

[modifier] Nombres premiers

Définition

On appelle nombre premier un nombre naturel > 1 qui n'a pas d'autre diviseur (dans N) que lui-même et l'unité.

Proposition

Soit p un nombre premier. Un entier rationnel a est premier avec p si et seulement s'il n'est pas divisible par p.

Démonstration. Si a est premier avec p, il n'est pas divisible par p car, dans le cas contraire, p serait un diviseur naturel commun de a et b distinct de 1. Réciproquement, supposons a non divisible par p et prouvons que a et p sont premiers entre eux. Soit d un diviseur naturel commun de a et p. Il s'agit de prouver que d = 1. Puisque d divise p et que p est premier, d est égal à 1 ou à p. Il n'est pas égal à p, puisqu'il divise a et que p est supposé ne pas diviser a'. Donc d = 1 comme annoncé.

Lemme d'Euclide

Soient p un nombre premier, a et b des entiers rationnels. Si p divise ab, il divise a ou b. Plus généralement, si p divise un produit d'entiers rationnels, il divise au moins un des facteurs.

Démonstration. Supposons que p divise ab. Si p ne divise pas a, il est premier avec a d'après le théorème précédent, donc il divise b d'après le lemme de Gauss, ce qui démontre la première assertion de l'énoncé. Démontrons la seconde partie de l'énoncé par récurrences sur n. Si maintenant p divise , alors et p divise . Si p ne divise pas a_n, alors, d'après la première partie de l'énoncé, il divise et, par hypothèse de récurrence, il divise un au moins des facteurs .

Théorème fondamental de l'arithmétique

Tout nombre naturel non nul est le produit d'une famille finie de nombres premiers. Cette famille est unique à l'ordre près.

Démonstration. Soit n un nombre naturel non nul. Prouvons par récurrence sur n que n est décomposable en produit de facteurs premiers. Si n est égal à 1, il est le produit de la famille vide et l'énoncé est vrai. Si n > 1, ou bien n est premier et l'énoncé est vrai, ou bien n admet un diviseur naturel n₁ distinct de 1 et de n. Alors n = n₁ n₂, où n₁ et n₂ sont des nombres naturels non nuls tous deux < n. Par hypothèse de récurrnence, n₁ et n₂ sont tous deux décomposables en produits de facteurs premiers, donc n l'est aussi.

Nous avons donc prouvé que tout nombre naturel non nul est le produit d'une famille finie de nombres premiers. Prouvons que cette famille est unique à l'ordre près. Ici encore, nous raisonnons par récurrence sur n. Soient

et

deux décompositions de n en produit de facteurs premiers. Si r = 0, alors n = 1, donc les familles et sont toutes deux vides et la thèse est vraie. Nous pouvons donc supposer . D'après le lemme d'Euclide, p_r divise un des nombres , soit q_j. Puisque q_j est premier, il est clair qu'il est égal à p_r. Donc n / p_r admet les décompositions

et

.

Par hypothèse de récurrence sur n, les familles et sont égales à l'ordre près, donc il en est de même des familles et , ce qui achève la démonstration.

Remarque. Les théorèmes de divisibilité relatifs à Z peuvent être considérés comme des cas particuliers de théorèmes relatifs aux anneaux euclidiens. On aurait pu introduire ici les notions d'anneau et d'anneau euclidien, démontrer en toute généralité les théorèmes de divisibilité dans les anneaux euclidiens et en déduire les théorèmes de divisibilité dans Z comme cas particuliers.