Théorème 5Les entiers relatifs

PGCD, théorème de Bézout, lemme de Gauss

La divisibilité $a \mid b$ , « $a$ divise $b$ », est celle du nœud Division euclidienne : il existe $c \in {\mathbb Z}$ tel que $b = ac$ . Pour $a, b \in \mathbb Z$ , l'idéal $a\mathbb Z + b\mathbb Z$ s'écrit $d\mathbb Z$ pour un unique $d \in {\mathbb N}$ (Idéaux de ℤ) : c'est le plus grand commun diviseur de $a$ et $b$ , noté $a \wedge b$ . Les entiers $a$ et $b$ sont premiers entre eux si $a \wedge b = 1$ .

Énoncé

(i) $a \wedge b$ divise $a$ et $b$ , et tout diviseur commun de $a$ et $b$ divise $a \wedge b$ .

(ii) Bézout. $a \wedge b = 1$ si et seulement s'il existe $u, v \in \mathbb Z$ tels que $au + bv = 1$ .

(iii) Gauss. Si $a \mid bc$ et $a \wedge b = 1$ , alors $a \mid c$ .

Démonstration

(i) $a = a \cdot 1 + b \cdot 0 \in d\mathbb Z$ , donc $d \mid a$ ; de même $d \mid b$ . Comme $d \in a\mathbb Z + b\mathbb Z$ , on écrit $d = au + bv$ ; un diviseur commun de $a$ et $b$ divise alors $d$ .

(ii) Si $a \wedge b = 1$ , alors $1 \in a\mathbb Z + b\mathbb Z$ . Réciproquement, si $au + bv = 1$ , alors $1 \in a\mathbb Z + b\mathbb Z = d\mathbb Z$ , donc $d \mid 1$ , et $d = 1$ puisque $d \in \mathbb N$ .

(iii) Écrivons $au + bv = 1$ . Alors $c = acu + bcv$ , et $a$ divise les deux termes, donc $c$ .

□

Remarque

La définition par l'idéal évite d'avoir à parler du « plus grand » diviseur. Le point (i) montre que $a \wedge b$ est bien le plus grand diviseur commun au sens de la divisibilité, et donc aussi au sens de l'ordre lorsque $a$ ou $b$ est non nul.

Remarque

L'algorithme d'Euclide calcule $a \wedge b$ par divisions euclidiennes successives, en remplaçant $(a, b)$ par $(b, r)$ , ce qui ne change pas l'idéal $a\mathbb Z + b\mathbb Z$ puisque $r = a - bq$ . Ainsi $252 \wedge 198 = 18$ , et $252 \cdot 4 - 198 \cdot 5 = 18$ donne une relation de Bézout.

Repose sur

Les idéaux de ℤ sont principaux

Sert à

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