File:PGCD par soustractions successives.svg

${\displaystyle {\text{de }}\,\{30,\ 24\,\},\,}$

${\displaystyle 2\,|\,30\,{\text{ et }}\,2\,|\,24.\,}$

${\displaystyle {\text{de }}\,\{30,\ 24\,\}:\,}$

${\displaystyle \,{\text{PGCD}}(30,\ 24)=6.\,}$

${\displaystyle \,{\text{Et PGCD}}(0,\ 0)=0\ }$

${\displaystyle {\text{est }}\,\leqslant .\,}$

En désignant ${\displaystyle {\text{par }}\,C\,}$ l’ensemble des diviseurs communs ${\displaystyle {\text{de }}\,\{30,\ 24\,\},\,}$ ${\displaystyle \,30\,{\text{ et }}\,24\,}$ sont des multiples de n’importe quel élément ${\displaystyle d\,{\text{ de }}\,C.\,}$ ${\displaystyle {\text{Donc, }}\,30-24=6\,}$ est aussi un multiple ${\displaystyle {\text{de }}\,d.\,}$ Réciproquement, tout diviseur commun ${\displaystyle {\text{de }}\,\{24,\ 6\,\}\,}$ est aussi un diviseur ${\displaystyle {\text{de }}\,24\,{\text{ et }}\,6+24=30.\,}$ Autrement dit, ${\displaystyle C\,{\text{ est}}\,}$ aussi l’ensemble des diviseurs communs ${\displaystyle {\text{de }}\,\{24,\ 6\,\}.}$

Par l’algorithme de l’image, ${\displaystyle \{30,\ 24\,\}\,}$ est remplacé ${\displaystyle {\text{par }}\,\{24,\ 6\,\},\,}$ puis remplacé ${\displaystyle \,{\text{par }}\,\{18,\ 6\,\}\,}$ en répétant le processus, ${\displaystyle {\text{parce que }}\,24-6=18.\,}$ Et puis remplacé ${\displaystyle \,{\text{par }}\,\{12,\ 6\,\},\,}$ ${\displaystyle \,{\text{et par }}\,\{6,\ 6\,\}.\,}$ Finalement l’algorithme remplace la paire initiale ${\displaystyle {\text{par }}\,\{6,\ 0\,\},\,}$ sort de la boucle des soustractions, et affirme que  ${\displaystyle 6\,{\text{ est le PGCD de }}\,30\,{\text{ et }}\,24.}$

Au lieu de remplacer ${\displaystyle \{24,\ 6\,\}\,}$ par les quatre paires successives : ${\displaystyle \{18,\ 6\,\},\ \{12,\ 6\,\},\ \{6,\ 6\,\},\ \{0,\ 6\,\},\,}$ nous pourrions obtenir directement la dernière paire par la division euclidienne ${\displaystyle {\text{de }}\,24\,{\text{ par }}\,6.\,}$ Peu importe qu’il y ait 4 soustractions successives de 6, nous pouvons ignorer 4 : la valeur du quotient de cette division euclidienne. En fait, n’importe quelle séquence de soustractions d’un même nombre revient à une division euclidienne par ce nombre. Ainsi nous découvrons l’algorithme plus connu du PGCD par divisions euclidiennes successives, en améliorant le présent algorithme par soustractions.

Les néophytes en codage peuvent copier et coller dans une fenêtre dédiée au JavaScript l’une des comparaisons suivantes, et commander ensuite l’exécution : 30 < 24; ou 6 == 0; ou 6 < 24. Dans l’image, six symboles ressemblent à des affectations en OCaml. Voici un exemple d’affectation en JavaScript : r = 30; qui range dans la ${\displaystyle {\text{variable }}\,r\,}$ l’objet de type Number et de valeur 30. Chacun peut télécharger Firefox, et puis ouvrir une fenêtre Firefox dédiée au code JavaScript. Dans cette fenêtre spéciale, on peut copier et coller la traduction suivante de l’organigramme en JavaScript.

/* Pour ouvrir une fenêtre Firefox
 dédiée au code JavaScript :  Maj + F4  */

d = r = k = 182; p = 238;  // exemple de valeurs d’entrée,
// que nous pouvons remplacer par deux autres entiers naturels
if( s = p){  // si la valeur commune de s et p n’est pas nulle
while(r){  // tant que la valeur de r n’est pas nulle
if(r < s){  // dans ce cas, intervertir les valeurs de r et s
d = s; s = r; r = d }
r = r-s }  // fin de la boucle 'while(r)'
d = s }  // fin du bloc commençant par 'if( s = p)'
"   PGCD("+ k +", "+ p +") = "+ d;  // sortie : un objet de type String

// Raccourci clavier Firefox pour exécuter ce code :  Ctrl + L

En haut de l’image,  ${\displaystyle r\in \mathbb {N} \ }$ signifie que  ${\displaystyle r\,{\text{ appartient à}}}$ ${\displaystyle {\text{l’ensemble }}\mathbb {N} }$ des entiers naturels. Le code JavaScript qui précède ne fonctionne que si les valeurs d’entrée sont des entiers naturels. Voici une amélioration du code précédent, où les valeurs d’entrée affectées ${\displaystyle {\text{à }}\,k\,{\text{ et }}\,p\,}$ sont vérifiées.

try{  //  en cas d’erreur dans ce bloc de code,
//  l’exécution du bloc échoue, on va à 'catch'
d = r = k = 408; p = 255;  // exemple de valeurs d’entrée
var b;  // déclaration de portée globale
s = function(n){
// pour tester la valeur de l’argument n :  est-ce un entier naturel ?
b = n.constructor == Number; // valeur Booléenne : true ou false
if( !b // premier cas incorrect
  || n < 0 || n != Math.floor(n)  // autres cas incorrects
) throw n
// dans un des cas précédents, n est rejeté en tant qu’erreur
}  // fin de l’affectation de la fonction à la variable s

s(k); s(p);  // vérifications des valeurs d’entrée
if( s = p){  // si la valeur commune de s et p n’est pas nulle
while(r){
if(r < s){d = s; s = r; r = d} r = r-s } d = s }
"  PGCD("+ k +", "+ p +") = "+ d
}catch(e){  // en cas d’erreur (si e est rejeté)
"  "+( b ? e +"  n’est pas un nombre entier naturel.":
" Code incorrect.")
}

${\displaystyle {\text{Par exemple, PGCD}}(408,\ 255)=51,\,}$

${\displaystyle {\frac {\,408\,}{51}}=8\ {\text{ et }}\ {\frac {\,255\,}{51}}=5,\ }$

${\displaystyle {\text{donc }}\,{\frac {\,8\,}{5}}\,}$

${\displaystyle {\text{de }}\,{\frac {\,408\,}{255}}.\,}$