Maths-cours

COURS & EXERCICES DE MATHÉMATIQUES

Close

Deux méthodes de calcul du PGCD

1 - Méthode des soustractions successives

Cette méthode se base sur le résultat suivant :

Théorème

Soient aa et bb sont deux entiers naturels non nuls avec a>ba > b alors PGCD(a ;b)=PGCD(b ;a−b)PGCD\left(a~; b\right) = PGCD\left(b~; a - b\right).

Remarque

L'intérêt de ce théorème est qu'il remplace le calcul du PGCD de deux nombres par le calcul du PGCD de deux nombres plus petits. On peut ainsi calculer un PGCD utilisant plusieurs fois de suite ce théorème (méthode des soustractions successives).

Exemple

Calculons le PGCD de 600600 et 315315 par la méthode des soustractions successives.

600−315=285600 - 315 =285 donc PGCD(600 ;315)=PGCD(315 ;285)PGCD\left(600~; 315\right)=PGCD\left(315~; 285\right)

315−285=30315 - 285 =30 donc PGCD(315 ;285)=PGCD(285 ;30)PGCD\left(315~; 285\right)=PGCD\left(285~; 30\right)

285−30=255285 - 30 =255 donc PGCD(285 ;30)=PGCD(255 ;30)PGCD\left(285~; 30\right)=PGCD\left(255~; 30\right)

255−30=225255 - 30 =225 donc PGCD(255 ;30)=PGCD(225 ;30)PGCD\left(255~; 30\right)=PGCD\left(225~; 30\right)

225−30=195225 - 30 =195 donc PGCD(225 ;30)=PGCD(195 ;30)PGCD\left(225~; 30\right)=PGCD\left(195~; 30\right)

195−30=165195 - 30 =165 donc PGCD(195 ;30)=PGCD(165 ;30)PGCD\left(195~; 30\right)=PGCD\left(165~; 30\right)

165−30=135165 - 30 =135 donc PGCD(165 ;30)=PGCD(135 ;30)PGCD\left(165~; 30\right)=PGCD\left(135~; 30\right)

135−30=105135 - 30 =105 donc PGCD(135 ;30)=PGCD(105 ;30)PGCD\left(135~; 30\right)=PGCD\left(105~; 30\right)

105−30=75105 - 30 =75 donc PGCD(105 ;30)=PGCD(75 ;30)PGCD\left(105~; 30\right)=PGCD\left(75~; 30\right)

75−30=4575 - 30 =45 donc PGCD(75 ;30)=PGCD(45 ;30)PGCD\left(75~; 30\right)=PGCD\left(45~; 30\right)

45−30=1545 - 30 =15 donc PGCD(45 ;30)=PGCD(15 ;30)PGCD\left(45~; 30\right)=PGCD\left(15~; 30\right)

30−15=1530 - 15 =15 donc PGCD(30 ;15)=PGCD(15 ;15)PGCD\left(30~; 15\right)=PGCD\left(15~; 15\right)

Or évidemment PGCD(15 ;15)=15PGCD\left(15~; 15\right) = 15 donc finalement :

PGCD(600 ;315)=15PGCD\left(600~; 315\right)=15.

Remarque

On voit que cette méthode est assez simple au niveau calcul (elle ne requiert que des soustractions) mais elle peut dans certains cas s'avérer assez longue. Une méthode plus rapide est l'algorithme d'Euclide.

2 - Algorithme d'Euclide

L'algorithme d'Euclide utilise le théorème suivant :

Théorème

Soient aa et bb sont deux entiers naturels non nuls avec a>ba > b et rr le reste de la division euclidienne de aa par bb.

Si r≠0r\neq 0 alors PGCD(a ;b)=PGCD(b ;r)PGCD\left(a~; b\right) = PGCD\left(b~; r\right).

Remarques

  • Si r=0r=0, cela signifie que bb divise aa donc dans ce cas PGCD(a;b)=bPGCD\left(a;b\right)=b

  • Comme le précédent, ce théorème remplace le calcul d'un PGCD par le calcul du PGCD de deux nombres plus petits.

    On peut, là encore, calculer un PGCD utilisant plusieurs fois de suite ce théorème. cette méthode s'appelle l'algorithme d'Euclide (ou la méthode des divisions successives).

Exemple

Calculons, à nouveau, le PGCD de 600600 et 315315 mais avec l'algorithme d'Euclide cette fois :

600600 touche division euclidienne 315 315 : Q=1 Q=1 et R=285R=285 donc PGCD(600 ;315)=PGCD(315 ;285)PGCD\left(600~; 315\right)=PGCD\left(315~; 285\right)

315315 touche division euclidienne 285285 : Q=1 Q=1 et R=30R=30 donc PGCD(315 ;285)=PGCD(285 ;30)PGCD\left(315~; 285\right)=PGCD\left(285~; 30\right)

285285 touche division euclidienne 3030 : Q=9 Q=9 et R=15R=15 donc PGCD(285 ;30)=PGCD(30 ;15)PGCD\left(285~; 30\right)=PGCD\left(30~; 15\right)

3030 touche division euclidienne 1515 : Q=2 Q=2 et R=0R=0

On s'arrête car le reste est nul.

Le PGCD est le dernier reste non nul donc :

PGCD(600 ;315)=15PGCD\left(600~; 315\right)=15.

Remarque

Si vous souhaitez vous entraîner à cette méthode, vous pouvez vérifier votre calcul et votre résultat grâce à cet outil : PGCD Algorithme d'Euclide

Dans ce chapitre :

Cours

Exercices

Compléments

Quiz

Outil