Calcul du et PGCD par la méthode des soustractions successives

1. Rappel d’une propriété du PGCD

C’est la deuxième méthode de recherche du PGCD de deux nombres entiers naturels non nuls. Elle est basée sur la propriété suivante du PGCD :

Propriété 3.
Soient $a$ et $b$ deux nombres entiers naturels non nuls. On suppose que $a>b$. Alors $$\boxed{\;\; PGCD(a;b)=PGCD(a;a−b)\;\;}$$

Cette propriété permet de réduire la recherche à des nombres plus petits. Si on
recommence le procédé de proche en proche, on devrait y arriver. A quel moment faudra-t-il s’arrêter ?

Exemple
Déterminer le PGCD de 18 et 24 en utilisant la méthode précédente.

$PGCD(18;24)=PGCD(18;24-18)$
$\phantom{PGCD(18;24)}=PGCD(18;6)$.
$\phantom{PGCD(18;24)}=6$, car 18 est un multiple de $6$.

2. Description de la méthode des soustractions successives

Propriété 2. Deuxième méthode : Algorithme des différences successives
Soient $a$ et $b$ deux nombres entiers naturels non nuls. On suppose que $a>b$. Alors :
$\quad\bullet$ Si $a$ est un multiple de $b$, alors $PGCD(a;b)=b$. Terminé.
$\quad\bullet$ Sinon, on calcule les différences successives de la manières suivante : $$a-b=c$$
On barre $a$, puis on remplace $a$ par le plus grand des deux nombres $b$ ou $c$ et $b$ par le plus petit des deux nombres $b$ ou $c$.
$\quad\bullet$ On recommence le procédé jusqu’à obtenir une différence nulle. Alors le PGCD est égal à la dernière différence non nulle dans la suite des soustractions successives entre $a$ et $b$.

Exemple.
Calculer le PGCD de $18$ et $24$ par la méthode des différences successives.

Corrigé
Recherchons le PGCD de $18$ et $24$. Tout d’abord, on a bien : $24>18$.
On calcule les différences successives de $24$ et $18$ comme suit :
$24\!\!\!\!{\color{brown}{\diagup}} -18 = 6$
$18\!\!\!\!{\color{brown}{\diagup}} -6 = 12$
$12\!\!\!\!{\color{brown}{\diagup}} -6 = {\color{brown}{\boxed{\;\;6\;\;}}}$. Dernière différence non nulle.
$6\!\!\!\!{\color{brown}{\diagup}} -6 =0$. La dernière différence nulle.
La dernière différence non nulle étant égale à $6$, donc : $${\color{brown}{\boxed{\;\;PGCD(18;24) = 6\;\;}}}$$

Remarques
1. Cette méthode est construite sous la forme d’un algorithme. On peut donc écrire un programme sur calculatrice ou un logiciel de programmation.

2. Un petit problème : le nombre d’opérations nécessaires pour exécuter cette méthode à la main ou dans un programme deviendra fastidieux pour certains couples de nombres.

Essayez de calculer le PGCD de 1792 et 48 avec cette méthode. Il faudra soustraire 48 au moins 36 fois avant de commencer à voire poindre la solution.

Il faudra utiliser une autre méthode, plus rapide. En l’occurrence, on utilisera la méthode des divisions euclidiennes successives, dite algorithme d’Euclide.

3. Exercices résolus

Vues : 16