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 $a$ et $b$ sont deux entiers naturels non nuls avec $a > b$ alors $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 $600$ et $315$ par la méthode des soustractions successives.

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

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

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

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

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

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

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

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

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

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

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

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

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

$PGCD\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 $a$ et $b$ sont deux entiers naturels non nuls avec $a > b$ et $r$ le reste de la division euclidienne de $a$ par $b$ .

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

Remarques

Si $r=0$ , cela signifie que $b$ divise $a$ donc dans ce cas $PGCD\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 $600$ et $315$ mais avec l'algorithme d'Euclide cette fois :

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

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

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

$30$ touche division euclidienne $15$ : $Q=2$ et $R=0$

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

Le PGCD est le dernier reste non nul donc :

$PGCD\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

1 - Méthode des soustractions successives

Théorème

Remarque

Exemple

Remarque

2 - Algorithme d'Euclide

Théorème

Remarques

Exemple

Remarque

Dans ce chapitre...

Cours

Exercices

Méthodes

Outils

Quiz

VOIR AUSSI...