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

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

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.

Pour comprendre, fais des exercices !

0/5 validés

Exercice d'exemple

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

Étape 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

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

Étape 2 —

r_1 = 0

, alors

\mathrm{pgcd}(a,b) = b

. Sinon, recommencer avec la paire

(b, r_1)

b = r_1 q_2 + r_2

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

Étape 3 —

Continuer jusqu'à obtenir un reste nul

r_k = 0

: le PGCD est

r_{k-1}

, le dernier reste non nul.

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

Application guidée

Calcul de $\mathrm{pgcd}(252, 105)$

Application autonome 1

Calcul de $\mathrm{pgcd}(1071, 462)$

Application autonome 2

Calcul de $\mathrm{pgcd}(13, 7)$ — entiers premiers entre eux

Application autonome 3

Calcul de $\mathrm{pgcd}(840, 308)$ .

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

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, fais des 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