PGCD et Théorème de Bézout

PGCD et Théorème de Bézout

• Le PGCD (plus grand commun diviseur) de deux entiers $a$ et $b$ est un entier naturel $d$ qui divise à la fois $a$ et $b$, et tel que tout autre diviseur commun de $a$ et $b$ divise $d$.
• Le théorème de Bézout stipule que pour deux entiers $a$ et $b$, il existe des entiers $u$ et $v$ tels que $au + bv = pgcd(a, b)$.

Démonstration du Théorème de Bézout

• L'ensemble $E$ est défini comme l'ensemble des combinaisons linéaires de $a$ et $b$ avec des coefficients entiers, qui sont aussi des nombres naturels.
• $E = {au + bv, (u, v) \in \mathbb{Z}^2} \cap \mathbb{N}$ est non vide car $|a|$ appartient à $E$.
• Soit $d$ le plus petit élément de $E$, il existe $u_0$ et $v_0$ dans $\mathbb{Z}$ tels que $d = au_0 + bv_0$.
• La division euclidienne de $a$ par $d$ donne $a = dq + r$ avec $0 \le r < d$.
• L'expression $r = a(1 - u_0q) + b(-v_0q)$ montre que $r$ appartient à $E$.
• Comme $d$ est le plus petit élément de $E$ et $r < d$, alors $r = 0$, ce qui implique que $d \mid a$.
• De même, il est démontré que $d \mid b$.
• Si $d'$ est un diviseur commun de $a$ et $b$, alors $d' \mid au_0 + bv_0$, donc $d' \mid d$.

Corollaire du Théorème de Bézout

• Si $a$ et $b$ sont premiers entre eux (c'est-à-dire que leur PGCD est 1), il existe des entiers $u$ et $v$ tels que $au + bv = 1$.

Lemme de Gauss

• Si $a$ divise le produit $bc$, et $a$ et $b$ sont premiers entre eux, alors $a$ divise $c$.

Démonstration du Lemme de Gauss

• $a \mid bc$ implique l'existence d'un entier $k$ tel que $bc = ak$.
• $a \land b = 1$ implique l'existence d'entiers $u$ et $v$ tels que $au + bv = 1$.
• En multipliant l'équation $au + bv = 1$ par $c$, on obtient $cau + cbv = c$.
• En substituant $cb = ak$, on obtient $cau + akv = c$, qui se simplifie en $a(cu + kv) = c$.
• Par conséquent, $a \mid c$.

Théorème Lié aux Nombres Premiers

• Si $p$ est un nombre premier et $p$ divise le produit $ab$, alors $p$ divise $a$ ou $p$ divise $b$.

Démonstration du Théorème

• Si $p \mid a$, la condition est satisfaite.
• Sinon, $p$ et $a$ sont premiers entre eux.
• Étant donné que $p \mid ab$ et $p \land a = 1$, selon le lemme de Gauss, $p \mid b$.

Corollaire du Théorème

• Si $p$ est un nombre premier qui divise un produit $a_1 \dots a_n$, alors il existe au moins un indice $i$ dans l'ensemble ${1, \dots, n}$ tel que $p$ divise $a_i$.