Exemple du pgcd

Considérons le théorème suivant:

théorème (1) $pgcd(a,a)=pgcd(a,0)=a$
(2) $pgcd(a,b)=pgcd(b,a)$
(3) Si $a$ et $b$ sont deux entiers tels que $a > b$ alors $pgcd(a,b)=pgcd(a-b,b)$

Prouvons le (3): soit $m$ un diviseur commun à $a$ et à $b$ alors $a=ma'$ et $b=mb'$, si $a > b$ alors $a-b=m(a'-b')$ et $m$ est un diviseur commun à $a-b$ et à $b$. Réciproquement, si $m$ est un diviseur commun à $a-b$ et $b$ alors $m$ est aussi un diviseur commun à $a$ et $b$.

De ce théorème on peut déduire le programme suivant pour calculer le pgcd de deux nombres:

     m:=a;
     n:=b;

     while  m != n do
         if m > n then m := m - n fi
         if m < n then n := n - m fi
     od

En effet, à chaque itération, la valeur de $pgcd(m,n)$ reste la même (d'après le théorème) aussi si le programme termine, on a $m=n$ et d'après le théorème précédent dans ce cas le $pgcd$ de $m$ et $n$ est $m$.

Ce programme termine puisqu'à chaque itération, la différence $\vert m-n\vert$ décroît strictement, il y aura donc au plus $\vert a-b\vert$ itérations.

Comme on le voit la terminaison est traitée différemment.