Propriété qui justifie cet algorithme
La propriété qui permet de comprendre cet algorithme est la suivante :

Pour tous entiers naturels non nuls a et b pgcd(a , b) =

• pgcd( a , b - a) si b > a
• pgcd ( a - b, b) si a > b
• pgcd (a, b) = a = b si a = b.
  

Algorithme : choisir deux entiers non nuls a = et
b = et