PGCD : définition, méthode et exercices corrigés

Définitions et Algorithme d'Euclide

Propriétés du PGCD

• PGCD : le plus grand diviseur commun à deux entiers $a$ et $b$.
• Nombres premiers entre eux : leur unique diviseur commun positif est $1$, soit $PGCD(a; b) = 1$.
• Simplification : si $b$ divise $a$, alors $PGCD(a; b) = |b|$.

Algorithme d'Euclide

Méthode des divisions euclidiennes successives : le PGCD est le dernier reste non nul.

Exemple : $PGCD(1578; 534)$

• $1578 = 534 \times 2 + 510$
• $534 = 510 \times 1 + 24$
• $510 = 24 \times 21 + 6$
• $24 = 6 \times 4 + 0$ d'où $PGCD = 6$.

💡 Astuce : Pour simplifier tes calculs, retiens que $PGCD(a; b) = PGCD(b; a - kb)$.

Théorèmes de Bézout et de Gauss

Théorème de Bézout

• Identité de Bézout : il existe des entiers $u$ et $v$ tels que $au + bv = PGCD(a; b)$.
• Caractérisation : $a$ et $b$ sont premiers entre eux si et seulement si $au + bv = 1$.

Théorème de Gauss

• Énoncé : si $a$ divise le produit $bc$ et que $a$ est premier avec $b$, alors $a$ divise $c$.
• Corollaire : si $b$ et $c$ sont premiers entre eux et divisent $a$, alors leur produit $bc$ divise $a$.

💡 Attention : Pour appliquer le théorème de Gauss, n'oublie jamais de vérifier d'abord que $a$ et $b$ sont bien premiers entre eux.