Comment calculer le PGCD de deux entiers ?

En appliquant l'algorithme d'Euclide : remplacer itérativement $(a, b)$ par $(b, a \bmod b)$ jusqu'à obtenir un reste nul ; le dernier reste non nul est le PGCD

L'objectif

Calculer $\mathrm{pgcd}(a, b)$ pour deux entiers $a, b$ avec $a \geq b > 0$ .

Le principe

La relation $\mathrm{pgcd}(a, b) = \mathrm{pgcd}(b, a \bmod b)$ permet de réduire le problème à des paires de plus en plus petites jusqu'au reste nul.

La méthode

1
S'assurer que $a \geq b > 0$ (échanger si nécessaire). Effectuer la division euclidienne : $a = bq_1 + r_1$ avec $0 \leq r_1 < b$ .
2
Si $r_1 = 0$ , alors $\mathrm{pgcd}(a,b) = b$ . Sinon, recommencer avec la paire $(b, r_1)$ : $b = r_1 q_2 + r_2$ .
3
Continuer jusqu'à obtenir un reste nul $r_k = 0$ : le PGCD est $r_{k-1}$ , le dernier reste non nul.

Exemple corrigé

Difficulté croissante de 1 à 4

Exercices aujourd'hui0 / 3

Prêt à t'entraîner ?

Génère un exercice personnalisé sur cette méthode et entraîne-toi avec la correction IA.

En appliquant l'algorithme d'Euclide : remplacer itérativement (a,b)(a, b)(a,b) par (b,a mod b)(b, a \bmod b)(b,amodb) jusqu'à obtenir un reste nul ; le dernier reste non nul est le PGCD

Exemple corrigé

En appliquant l'algorithme d'Euclide : remplacer itérativement $(a, b)$ par $(b, a \bmod b)$ jusqu'à obtenir un reste nul ; le dernier reste non nul est le PGCD