Algorithme d'Euclide : PGCD par divisions successives

Le principe

Le PGCD de $a$ et $b$ ne change pas si on remplace $a$ par le reste de $a$ divisé par $b$.

$\text{PGCD}(a, b) = \text{PGCD}(b, r) \quad \text{où } a = bq + r$

On répète jusqu’à obtenir un reste égal à 0. Le dernier reste non nul est le PGCD.

Méthode pas à pas

Exemple : PGCD(252, 105).

Étape	Division	Quotient	Reste
1	252 = 105 × 2 + 42	2	42
2	105 = 42 × 2 + 21	2	21
3	42 = 21 × 2 + 0	2	0

PGCD(252, 105) = 21 (dernier reste non nul).

Autre exemple

PGCD(1071, 462) :

• 1071 = 462 × 2 + 147
• 462 = 147 × 3 + 21
• 147 = 21 × 7 + 0

PGCD = 21.

Pourquoi ça marche ?

Chaque étape réduit strictement la taille des nombres. L’algorithme termine forcément. Et à chaque étape le PGCD est préservé (théorème d’Euclide).

Applications

• Simplifier une fraction : diviser numérateur et dénominateur par leur PGCD.
• Résoudre une équation diophantienne $ax + by = c$ : possible ssi $\text{PGCD}(a, b)$ divise $c$.
• Cryptographie : Bézout (extension de l’algorithme d’Euclide) intervient dans RSA.

Erreurs classiques

1. S’arrêter trop tôt : on continue jusqu’à un reste NUL.
2. Prendre le mauvais reste : le PGCD est le DERNIER reste NON nul.
3. Confondre reste et quotient.

?À toi de jouer

PGCD(48, 18) par l'algorithme d'Euclide ?

A.6B.2C.12D.3

Valider