Calcul du PGCD de deux nombres par la méthode des soustractions successives
Calcul du PGCD de deux nombres par la méthode des soustractions successives
On cherche le plus grand diviseur commun de deux nombres.
Or, si un nombre divise deux nombres, alors il divise leur différence.
On calcule donc la différence des deux nombres.
Le PGCD divise le plus petit des deux nombres et leur différence.
On recommence, jusqu'à ce que la différence soit 0.
Le PGCD est alors la dernière différence non nulle obtenue.
 
A la main : Avec un tableur :


Le PGCD de 2648 et 3456 est 8.

MAX(B2;C2) donne le plus grand des deux nombres de la deuxième et de la troisième colonne.
MIN(B2;C2) donne le plus petit de ces deux nombres
=A3-B3 calcule leur différence.
On fait faire les calculs automatiquement par le tableur en recopiant les formules dans les trois colonnes. ( avec Excel, en tirant le petit carré noir en bas à droite de la case ).

Calcul du PGCD : algorithme d'Euclide