Théorie des groupes/Sous-groupes de Z, divisibilité dans N et dans Z

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

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 $a\vert b$ 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 $a\leq b$ 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.)

Sous-groupes de Z

Rappelons qu'un groupe est dit monogène s'il est engendré par un seul élément. Nous avons vu 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}$, n parcourant $\mathbb {Z}$.

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

Proposition

Soit n un nombre naturel > 0. Les n éléments r de $\mathbb {Z}$ tels que $0\leq r<n$ forment une transversale du sous-groupe $n\mathbb {Z}$ de $\mathbb {Z}$, autrement dit un système de représentants de $\mathbb {Z}$ pour la relation d'équivalence $x\equiv y{\pmod {n}}$.

Pour une démonstration, voir par exemple « Division euclidienne », dans la leçon « Arithmétique ».

Corollaire

Soit n un nombre naturel > 0. Le groupe quotient $\mathbb {Z} /n\mathbb {Z}$ est d'ordre n.

Proposition

Soit H un sous-groupe de $\mathbb {Z}$. Il existe un et un seul nombre naturel $a\geq 0$ tel que H = $a\mathbb {Z}$.

'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 entier naturel > 0 appartenant à H; prouvons que H = a$\mathbb {Z}$. Puisque a appartient à H, a$\mathbb {Z}$ est contenu dans H (minimalité du sous-groupe engendré). Prouvons l'inclusion réciproque $H\subseteq a\mathbb {Z}$. Soit b un élément de H; il s'agit de prouver que b appartient à a$\mathbb {Z}$. Nous avons vu que b (comme tout élément de $\mathbb {Z}$) est congru modulo a à un nombre r parmi $0,1,\ldots a-1$. Nous avons alors r = b - na, avec $n\in \mathbb {Z} ,na\in a\mathbb {Z}$. Puisque b appartient à H par hypothèse et que, comme nous l'avons vu, $a\mathbb {Z}$ est contenu dans H, r appartient à H. Si r n'était pas nul, la minimalité de a serait contredite (puisque $0\leq r<a$), donc r est nul, donc l'égalité r = b - na donne b = na, donc b appartient à a$\mathbb {Z}$ comme annoncé.
Nous avons donc prouvé l’existence d'un a tel que dans l'énoncé. Prouvons son unicité. Soit $a_{1}$ un nombre naturel $\geq 0$ tel que $a\mathbb {Z} =a_{1}\mathbb {Z}$; il s'agit de prouver que $a_{1}=a$. On peut dire par exemple que $a$ et $a_{1}$ sont deux entiers naturels multiples l'un de l'autre dans $\mathbb {Z}$ et que, comme on le montre facilement, deux entiers naturels ne sont multiples l'un de l'autre dans $\mathbb {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 $\mathbb {Z}$, d'où l'unicité de a.

 

Théorèmes de divisibilité dans N et dans Z

Plus grand commun diviseur

Début d’un théorème

Théorème

Soit $\left(a_{i}\right)_{i\in I}$ une famille non vide (finie ou infinie) d'entiers rationnels. Il existe un et un seul nombre naturel d qui est diviseur commun des $a_{i}$ et multiple de tous leurs diviseurs communs, autrement dit : tel que les diviseurs communs des $a_{i}$ soient exactement les diviseurs de d.

Fin du théorème

Ce théorème repose uniquement sur la caractérisation ci-dessus des sous-groupes de (Z, +). C'est donc un cas particulier de la caractérisation du plus grand commun diviseur dans un anneau principal (voir « PGCD, PPCM », dans la leçon « Anneau »).

Remarque. Si d n’est pas nul, c'est-à-dire si les $a_{i}$ ne sont pas tous nuls, d est aussi le plus grand des diviseurs naturels communs des $a_{i}$ pour la relation d'ordre usuelle dans $\mathbb {N}$.

Définition

Soit $\left(a_{i}\right)_{i\in I}$ une famille non vide d'entiers rationnels, on appelle plus grand commun diviseur — en abrégé pgcd — des $a_{i}$, et l'on note $\operatorname {pgcd} \left(a_{i}\right)_{i\in I}$, l'unique nombre naturel qui divise tous les nombres $a_{i}$ et est multiple de tous leurs diviseurs communs.

Début d’un théorème

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

Soit $\left(a_{i}\right)_{i\in I}$ une famille non vide d'entiers rationnels, et d leur pgcd. Il existe des entiers rationnels $\left(c_{i}\right)_{i\in I}$, nuls sauf un nombre fini d'entre eux, tels que $\sum _{i\in I}a_{i}c_{i}=d$.

Fin du théorème

C'est à nouveau un cas particulier des propriétés du pgcd dans un anneau principal (voir « Identité de Bézout », dans la leçon « Anneau »).

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

Soient a ≠ 0 et b deux nombres naturels et d leur pgcd. Il existe des nombres naturels x et y tels que ax – d = by.

'Démonstration'

Si b = 0 alors d = a, donc x = 1 convient (avec y arbitraire). Si b ≠ 0 , appliquons le théorème de Bachet-Bézout : il existe des entiers rationnels u et v tels que au – d = bv. Pour tout entier n, en posant x = u + nb et y = v + na, on obtient ax – d = au – d + nab = bv + nab = by. De plus, puisque a et b sont supérieurs ou égaux à 1, x et y sont positifs si l'on choisit n ≥ max(|u|, |v|).

 

Définition : entiers premiers entre eux

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 $\mathbb {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

Soit $\left(a_{i}\right)_{i\in I}$ une famille non vide d'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 ;
• premiers entre eux deux à deux si pour tous indices $i$ et $j$ distincts, $a_{i}$ et $a_{j}$ sont premiers entre eux.

Début d’un théorème

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.

Fin du théorème

'Démonstration'

Si a et b sont tous deux nuls alors d = 0 ; on peut faire a' = b' = 1 et l'énoncé est vrai dans ce cas.

Sinon, voir Arithmétique/PGCD#Nombres premiers entre eux.

 

Début d'un lemme

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.

Fin du lemme

On le déduit facilement du théorème de Bachet-Bézout (voir « Théorème de Gauss » dans la leçon « Arithmétique »).

Corollaire

Soient a, b₁, ... , b_n des entiers rationnels. Si a est premier avec chacun des nombres b₁, ... , b_n, il est premier avec leur produit.

Cf. « Corollaire », dans la leçon « Anneau ».

Plus petit commun multiple

Début d’un théorème

Théorème

Soit $\left(a_{i}\right)_{i\in I}$ une famille (finie ou infinie) d'entiers rationnels. Il existe un et un seul nombre naturel m qui est multiple commun des $a_{i}$ et divise tous leurs multiples communs, autrement dit : tel que les multiples communs des $a_{i}$ soient exactement les multiples de m.

Fin du théorème

De même que précédemment pour le pgcd, c'est ici un cas particulier de la caractérisation du plus petit commun multiple dans un anneau principal (voir « PGCD, PPCM », dans la leçon « Anneau »).

Définition

Soit $\left(a_{i}\right)_{i\in I}$ une famille d'entiers rationnels, on appelle plus petit commun multiple des $a_{i}$, en abrégé ppcm des $a_{i}$, et l'on note $\operatorname {ppcm} \left(a_{i}\right)_{i\in I}$, l'unique nombre naturel qui est multiple de tous les $a_{i}$ et divise tous leurs multiples communs.

Remarque. Le produit d'une famille finie (a₁, ... , a_n) étant un multiple commun de a₁, ... , a_n, il est multiple de leur ppcm.

Début d'un lemme

Lemme

L'opérateur ppcm est « associatif », au sens suivant : si $I=\cup _{j\in J}I_{j}$ alors $\operatorname {ppcm} \left(a_{i}\right)_{i\in I}=\operatorname {ppcm} \left(b_{j}\right)_{j\in J}$, où $b_{j}:=\operatorname {ppcm} \left(a_{i}\right)_{i\in I_{j}}$.

Fin du lemme

'Démonstration'

Les $b_{j}$ et les $a_{i}$ ont mêmes multiples communs.

 

Début d’un théorème

Théorème

Si a₁, ... , a_n sont des nombres naturels premiers entre eux deux à deux, leur ppcm est leur produit.

Fin du théorème

Voir Arithmétique/Exercices/Divers#Exercice 11-8.

Début d’un théorème

Théorème

Pour tout nombre naturel $k$ et toute famille $\left(a_{i}\right)_{i\in I}$ d'entiers rationnels,

$\operatorname {ppcm} \left(ka_{i}\right)_{i\in I}=k\;\operatorname {ppcm} \left(a_{i}\right)_{i\in I}$.

Fin du théorème

Voir Anneau (mathématiques)/Exercices/Exercices#Exercice 4.

Début d’un théorème

Théorème

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

Fin du théorème

Voir Arithmétique/PPCM.

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ébut d'une démonstration

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.

Fin de la démonstration

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'

Soit d le pgcd de a et p. C'est un diviseur de p donc il est égal à soit à 1, soit à p.

Si p divise a alors d = p donc d ≠ 1 (autrement dit : a n'est pas premier avec p).

Réciproquement, si d ≠ 1 alors d = p, or d divise a, donc p divise a.

 

Début d'un lemme

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 $a_{1}\dots a_{n}$ d'entiers rationnels, il divise au moins un des facteurs.

Fin du lemme

On le déduit du lemme de Gauss ci-dessus, via le corollaire qui le suit : cf. « Lemme d'Euclide », dans la leçon « Anneau ».

Début d’un théorème

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.

Fin du théorème

Cf. « Décomposition en facteurs premiers », dans la leçon « Arithmétique ».

L'anneau Z/nZ

Dans cette section, on supposera connus les premiers éléments de la théorie des anneaux, y compris les notions d'idéal, d'anneau quotient et de corps.

On a vu au chapitre Groupes, premières notions que l'addition et la multiplication usuelles dans Z font de Z un anneau commutatif (non nul) admettant 1 pour unité et que, plus précisément, cet anneau est intègre. Puisque tout sous-groupe du groupe additif Z est de la forme nZ pour un certain élément n de Z, tout sous-groupe du groupe additif Z est un idéal de l'anneau Z. Donc les idéaux de l'anneau Z sont exactement les sous-groupes du groupe additif Z. Comme tout quotient d'un anneau commutatif par un idéal, le quotient Z/nZ se munit d'une structure d'anneau, l'addition étant la loi du groupe quotient (que nous avons déjà rencontrée) et la multiplication (notée par juxtaposition) pouvant se caractériser par la relation

$(a+n\mathbb {Z} )(b+n\mathbb {Z} )=ab+n\mathbb {Z} .$

Il nous arrivera de noter [x] la classe d'un entier rationnel modulo n (n étant sous-entendu dans la notation [x]). La relation ci-dessus peut alors s'écrire

$\ [a][b]=[ab].$

Si r et a sont des entiers rationnels, on a

$\ r[a]=[r][a].$

Soit n un nombre naturel; il est clair que l'anneau Z/nZ admet pour unité l'élément 1 + nZ et est nul si et seulement n = 1.

Début d’un théorème

Théorème

Soient n un nombre naturel et X une classe résiduelle modulo n, autrement dit un élément de Z/nZ. Les trois conditions suivantes sont équivalentes :

1° tout élément de X est premier avec n.
2° X comprend un entier rationnel premier avec n;
3° X est un élément inversible de l'anneau Z/nZ.

Si a est un entier rationnel, a + nZ est un élément inversible de l'anneau Z/nZ si et seulement si a est premier avec n.

Fin du théorème

Démonstration. Il est banal que 1° entraîne 2°. Supposons 2° vraie et prouvons 3° Puisque 2° est vraie, X est de la forme x + nZ, où x est premier avec n. D'après le théorème de Bézout, il existe des entiers rationnels a et b tels que ax + bn = 1. En passant aux classes modulo n, nous trouvons [x] [a] = [1]. Puisque [x] est égal à X, il en résulte que X est inversible, ce qui prouve 3°. Enfin, supposons 3° et prouvons 1°. Soit x un élément de X, il s'agit de prouver que x est premier avec n. Nous avons X = [x]. Puisque 3° est satisfaite, X admet un inverse, que nous pouvons noter [a] pour un certain entier rationnel a. Alors [x] [a] = [1], donc xa - 1 est divisible par n. Soit xa - 1 = yn, avec y entier. Tout diviseur commun à x et à n divise xa - yn, autrement dit divise 1, donc x est premier avec n, ce qui prouve 1°. Ainsi, les conditions 1° à 3° sont équivalentes. La dernière assertion de l'énoncé s'en déduit facilement.

Début d’un théorème

Théorème

Soit n un nombre naturel. L'anneau Z/nZ est un corps si et seulement n est un nombre premier.

Fin du théorème

Démonstration. Si n est premier, tout entier rationnel non divisible par n est premier avec n, ce qui, d’après le théorème précédent, revient à dire que tout élément non nul de l'anneau Z/nZ est inversible, donc cet anneau (non nul, puisque n > 1) est un corps. Réciproquement, supposons que l'anneau Z/nZ soit un corps et prouvons que n est un nombre premier. Puisqu'un corps a toujours au moins deux éléments, n est distinct de 1. D'autre part, Z/0Z est isomorphe à Z, qui n’est pas un corps, donc n est distinct de 0. Ainsi, n > 1. Puisque l'anneau Z/nZ est un corps, tout élément non nul de cet anneau est inversible, donc tout nombre naturel non divisible par n est premier avec n. Supposons que, par absurde, n ne soit pas un nombre premier. On a donc n = ab, où a et b sont des nombres naturels tous deux > 1. Alors a n’est pas divisible par n et n’est pas premier avec n, ce qui amène une contradiction.

Si p est un nombre premier, le corps $\mathbb {Z} /p\mathbb {Z}$ est souvent noté $\mathbb {F} _{p}$. On prouve facilement qu'entre deux corps à p éléments, il existe un et un seul isomorphisme. Pour cette raison, on dit volontiers « le corps à p éléments ».