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.

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 !

0/5 validés

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$

Application guidée

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

Application autonome 1

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

Application autonome 2

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

Application autonome 3

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

Crée ton compte gratuit pour accéder à la fiche et aux exercices