Cours de maths : Méthodes de calcul du PGCD

Méthode des soustractions successives :

Exemple : Calcul du PGCD de 351 et de 208.

1) On soustrait le plus petit des deux nombres au plus grand :

351 - 208 = 143

2) On prend les deux plus petits nombres et on recommence :

208 - 143 = 65

3) On recommence l'étape précédente jusqu'à obtention d'un résultat nul :

143 - 65 = 78
78 - 65 = 13
65 - 13 = 52
52 - 13 = 39
39 - 13 = 26
26 - 13 = 13
13 - 13 = 0

4) Le PGCD est le dernier résultat non nul, donc PGCD (351 ; 208) = 13.



Algorithme d'Euclide :

Exemple : Calcul du PGCD de 351 et de 208.

1) On effectue la division euclidienne du plus grand nombre par le plus petit :

351 208
143 1

351 = 208 × 1 + 143

2) On recommence avec le diviseur et le reste de la division précédente :

208 143
65 1

208 = 143 × 1 + 65

3) On recommence l'étape précédente jusqu'à ce que l'on obtienne un reste nul :

143 65
13 2

143 = 65 × 2 + 13
65 13
0 5

65 = 13 × 5 + 0

4) Le PGCD est le dernier reste non nul, donc PGCD (351 ; 208) = 13.


Fiche précédente :
PGCD
Fiche suivante :
Tableaux simples et tableaux à double entrée