Le PGCD de deux entiers PGCD de deux entiers

1. L’algorithme d’Euclide

Soient a et b deux entiers naturels tels que a ≥ b. Pour calculer leur PGCD, Euclide utilisait un algorithme basé sur le calcul successif de plusieurs soustractions. Après avoir calculé a - b = d, on remplace a par le plus grand des deux nombres b et d et on fait la soustraction. On recommence de la même façon jusqu’à obtenir un résultat égal à 0. On obtient alors le PGCD des deux nombres.

Calculons par exemple le PGCD de 90 et de 36 avec cette méthode. On obtient successivement 90-36=54, 54-36=18 et enfin 18-18=0. Le PGCD de 90 et de 36 est donc 18.

# Calcul d'un PGCD par différences successives 
a=eval(input("Valeur de a ?")) 
b=eval(input("Valeur de b ?")) 
while a!=b: 
    d=abs(b-a) 
    b=a 
    a=d 
print("pgcd=",d) 
if d==1: 
    print("Les deux entiers sont premiers entre eux.") 

2. La méthode des divisions successives

On utilise aujourd’hui une forme modernisée...