pgcdcm1

algorithme des différences pour trouver le $\mathrm{pgcd}$ de deux nombres

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$, $\mathrm{pgcd}(a , b) = $

• $\mathrm{pgcd}( a , b - a)$ si $b > a$
• $\mathrm{pgcd}( a - b, b)$ si $a > b$
• $\mathrm{pgcd}(a, b) = a = b$ si $a = b$.
  

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