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

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

Calcul de $\mathrm{pgcd}(48, 18)$

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.

Pour comprendre, passons aux exercices.

Exercice d'exemple

Calcul de $\mathrm{pgcd}(48, 18)$

1

$48 = 18 \times 2 + 12$ , donc $r_1 = 12 \neq 0$ .

2

$18 = 12 \times 1 + 6$ , donc $r_2 = 6 \neq 0$ . On continue avec $(12, 6)$ .

3

$12 = 6 \times 2 + 0$ , donc $r_3 = 0$ . Conclusion : $\mathrm{pgcd}(48, 18) = 6$ .

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.

Comment calculer le PGCD de deux entiers ?

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

Pour comprendre, passons aux exercices.

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