Comment trouver le PGCD de deux… : En appliquant l'algorithme d'Euclide (divisions… — 3e | MetMat

Comment trouver le PGCD de deux entiers ?

En appliquant l'algorithme d'Euclide (divisions euclidiennes successives)

Calculer efficacement le PGCD de deux entiers, même grands, sans les décomposer en facteurs premiers.

Maîtriser

Reconnaître

Résoudre

Que ferais-tu face à un exercice de ce type ?

Calcule $\mathrm{PGCD}(180, 126)$ par l'algorithme d'Euclide.

L'objectif

Calculer efficacement le PGCD de deux entiers, même grands, sans les décomposer en facteurs premiers.

Le principe

Le PGCD de $a$ et $b$ est égal au PGCD de $b$ et du reste de la division de $a$ par $b$ . On répète l'opération jusqu'à ce que le reste soit nul : le dernier diviseur non nul est le PGCD.

La méthode

1
Effectuer la division euclidienne du plus grand nombre par le plus petit, en notant le quotient $q$ et le reste $r$ .
2
Si le reste $r$ est nul, le $\mathrm{PGCD}$ est le diviseur de cette dernière division.
3
Si le reste $r$ est non nul, recommencer : diviser le diviseur précédent par $r$ (le nouveau dividende devient l'ancien diviseur, le nouveau diviseur devient l'ancien reste).
4
Répéter jusqu'à obtenir un reste nul. Le $\mathrm{PGCD}$ est le dernier reste non nul (c'est-à-dire le dernier diviseur utilisé).

Pour comprendre, fais des exercices !

Exercice d'exemple

Calcule $\mathrm{PGCD}(180, 126)$ par l'algorithme d'Euclide.

Étape 1 —

Effectuer la division euclidienne du plus grand nombre par le plus petit, en notant le quotient

q

et le reste

r

$180 = 126 \times 1 + 54$ (reste $54 \neq 0$ )

Étape 2 —

Si le reste

r

est nul, le

\mathrm{PGCD}

est le diviseur de cette dernière division.

Le reste n'est pas nul, on continue.

Étape 3 —

Si le reste

r

est non nul, recommencer : diviser le diviseur précédent par

r

(le nouveau dividende devient l'ancien diviseur, le nouveau diviseur devient l'ancien reste).

$126 = 54 \times 2 + 18$ (reste $18 \neq 0$ ) ; puis $54 = 18 \times 3 + 0$ (reste $0$ ).

Étape 4 —

Répéter jusqu'à obtenir un reste nul. Le

\mathrm{PGCD}

est le dernier reste non nul (c'est-à-dire le dernier diviseur utilisé).

Le reste est nul : le $\mathrm{PGCD}$ est le dernier diviseur, soit $18$ .

$\mathrm{PGCD}(180, 126) = 18$

Les applications suivantes et la correction guidée sont réservées aux membres Premium

La méthode et sa première application corrigée restent en accès libre. Le Premium débloque les applications suivantes, l'aide IA et le suivi de ta maîtrise.