Calcul du et PGCD par la méthode des divisions euclidiennes successives. Algorithme d’Euclide

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

Propriété 4.
Soient $a$ et $b$ deux nombres entiers naturels non nuls. On suppose que $a>b$.
Alors, si on effectue la division euclidienne de $a$ par $b$, il existe un couple unique d’entiers
$(q;r)$ tel que : $a = bq+r$, avec $0\leqslant r < b$. Alors : $$\boxed{\;\;PGCD(a;b)=PGCD(b;r)\;\;}$$

Cette propriété donne une méthode plus rapide, et permet de réduire la recherche du PGCD à des nombres plus petits. Si on recommence le procédé de proche en proche, on devrait y arriver plus vite que les autres méthodes. A quel moment faudra-t-il s’arrêter ?
Cette propriété sera utilisée pour développer la méthode des divisions euclidiennes successives, dite algorithme d’Euclide, pour le calcul du PGCD.

Exemple.
Déterminer le PGCD de $24$ et $18$ par la méthode des divisions euclidiennes successives.

Corrigé.
Si on pose $a=24$ et $b=18$, alors $24 = 18\times1+6$, donc $r=6$.
Par conséquent : $PGCD(18;24)=PGCD(18;6)=6$.
On recommence avec $a=18$ et $b=6$, alors $18 =6\times3+0$, donc $r=0$.
Or, le $PGCD(6;0)=6$. Donc ${\color{brown}{\boxed{\;\;PGCD(24;18)=6\;\;}}}$.

2. Description de la méthode des des divisions euclidiennes successives. Algorithme d’Euclide

Propriété 2. Deuxième méthode : divisions euclidiennes successives. Algorithme d’Euclide
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 la division euclidienne de $a$ par $b$. Donc, il existe un couple unique d’entiers $(q;r)$ tel que : $$a=b\times q+r$$
$\quad\bullet$ On remplace $a$ par $b$ et $b$ par $r$. On recommence le procédé jusqu’à obtenir un reste nul. Alors le PGCD est égal au dernier reste non nul dans la suite des divisions euclidiennes successives de $a$ par $b$.

Exemple.
Calculer le PGCD de $1792$ et $48$ par la méthode des divisions euclidiennes successives.

Remarque

Avec la méthode des soustractions successives, on aurait calculé :
$1792-48=1744$ ;
$1744-48=1696$ ;
$\ldots$ etc. ;
$64-48=16$ ;
$48-16=32$ ;
$32-16=16$ ;
$16-16=0$.
Ce qui signifie qu’on aurait du effectuer 42 soustractions avant d’obtenir une différence nulle.
Ce qui serait fastidieux pour un calcul à la main. Essayons avec la nouvelle méthode.

Corrigé.
Pour calculer le PGCD de $1792$ et $48$ par la méthode des divisions euclidiennes successives. On a bien : 1792 > 48. On calcule les divisions euclidiennes successives de 1792 par 48 comme suit :
$$1792 = 48\times 37 + 16$$
Donc : $PGCD(1792;48)=PGCD(48;16)$. Or $48$ est un multiple de $16$. Donc $PGCD(48;16)=16$.
Par conséquent : $${\color{brown}{\boxed{\;\;PGCD(1792;48) = 16\;\;}}}$$

3. Exercices résolus

Vues : 17