ℂ Option Mathématiques expertes Terminale Générale · Chapitre 5

PGCD, théorèmes de Bézout et de Gauss

Plus grand commun diviseur et algorithme d'Euclide, nombres premiers entre eux, théorème et identité de Bézout, théorème de Gauss et ses corollaires, équations diophantiennes ax + by = c.

1. PGCD et algorithme d'Euclide

Définition · PGCD

Le PGCD de deux entiers non tous deux nuls est le plus grand entier naturel qui les divise tous les deux. Deux entiers sont premiers entre eux si leur PGCD vaut $1$.

Propriété · Algorithme d'Euclide

Si $a = bq + r$, alors $\mathrm{PGCD}(a\,;\,b) = \mathrm{PGCD}(b\,;\,r)$. On répète les divisions euclidiennes : le PGCD est le dernier reste non nul.

Exemple · PGCD(252 ; 198)

$252 = 198 \times 1 + 54$ ; $198 = 54 \times 3 + 36$ ; $54 = 36 \times 1 + 18$ ; $36 = 18 \times 2 + 0$. Donc $\mathrm{PGCD}(252\,;\,198) = 18$.

2. Théorème de Bézout

Propriété · Identité et théorème de Bézout

Il existe des entiers $u$ et $v$ tels que $au + bv = \mathrm{PGCD}(a\,;\,b)$.

Théorème de Bézout : $a$ et $b$ sont premiers entre eux $\iff$ il existe des entiers $u$, $v$ tels que $au + bv = 1$.

Méthode · Trouver u et v

On « remonte » l'algorithme d'Euclide. Pour $35$ et $24$ : $35 = 24 + 11$, $24 = 2 \times 11 + 2$, $11 = 5 \times 2 + 1$. Donc $1 = 11 - 5 \times 2 = 11 - 5(24 - 2 \times 11) = 11 \times 11 - 5 \times 24 = 11(35 - 24) - 5 \times 24 = 35 \times 11 - 24 \times 16$.

3. Théorème de Gauss

Propriété · Théorème de Gauss

Si $a$ divise $bc$ et si $a$ est premier avec $b$, alors $a$ divise $c$.

Corollaire : si $a$ et $b$ divisent $n$ et sont premiers entre eux, alors $ab$ divise $n$.

36 dents24 dentsPPCM(24 ; 36) = 7272 = 2 × 36 = 3 × 24grande roue : 2 tourspetite roue : 3 tours
Les deux repères rouges se retrouvent face à face après 72 dents, soit 2 tours de la grande roue et 3 de la petite.

4. Équations ax + by = c

Méthode · Résolution

L'équation $ax + by = c$ a des solutions entières si et seulement si $\mathrm{PGCD}(a\,;\,b)$ divise $c$. On trouve une solution particulière $(x_0\,;\,y_0)$ (Bézout), on soustrait, puis on applique le théorème de Gauss.

Exemple · 3x + 5y = 1

$(2\,;\,-1)$ est solution. Alors $3(x - 2) = -5(y + 1)$ ; $5$ divise $3(x - 2)$ et est premier avec $3$, donc $5 \mid x - 2$ : $x = 2 + 5k$ et $y = -1 - 3k$, $k \in \mathbb{Z}$.

Attention · PGCD et PPCM

Pour des entiers naturels non nuls : $\mathrm{PGCD}(a\,;\,b) \times \mathrm{PPCM}(a\,;\,b) = ab$.

⚠️ Une erreur dans ce cours ? Signalez-la

S'entraîner

Exercices corrigés

🎓 20 exercices corrigés et un quiz vous attendent dans ce chapitre.

Créez votre compte gratuit pour voir les corrections, faire les quiz et suivre votre progression.

20

Engrenages

★★☆

Deux roues dentées de $24$ et $36$ dents engrènent. Au bout de combien de tours de chaque roue reviennent-elles pour la première fois à la position de départ ?

🔒 Correction réservée aux membres Créer un compte gratuit →

Vérifier

Avez-vous bien compris ?

Répondez au quiz : la correction s'affiche immédiatement.