L'algorithme d'Euclide et son pire cas

(* pgcd a b renvoie le PGCD de a et b. Precondition : a >= 0, b >= 0. *)
let rec pgcd a b = if b = 0 then a else pgcd b (a mod b)

Terminaison. Variant : $b$. Il est entier positif, et lors de l'appel pgcd b (a mod b) le nouveau second argument est $a\mathrm{mod}b$, strictement inférieur à $b$ puisque $b>0$. Le variant décroît strictement et reste positif.

Correction, par récurrence forte sur $b$. Si $b=0$, le résultat est $a$, et $\mathrm{pgcd}(a,0)=a$. Sinon, tout diviseur commun de $a$ et $b$ divise $a-qb=a\mathrm{mod}b$, et réciproquement tout diviseur commun de $b$ et $a\mathrm{mod}b$ divise $a$ : les deux paires ont les mêmes diviseurs communs, donc le même plus grand. Par hypothèse de récurrence appliquée à $(b,a\mathrm{mod}b)$, dont le variant $a\mathrm{mod}b$ est $<b$, la valeur rendue est bien $\mathrm{pgcd}(a,b)$.

Le pire cas est celui des Fibonacci consécutifs, et c'est une raison de les citer que le cours accepte : on les analyse, on ne les recommande pas. Comme $F(k+1)\mathrm{mod}F(k)=F(k-1)$, la suite des appels parcourt toute la suite de Fibonacci en descendant, sans jamais sauter d'étape. Mesuré :

pgcd(F5, F4)  = pgcd(5, 3)     : 4 appels
pgcd(F8, F7)  = pgcd(21, 13)   : 7 appels
pgcd(F12, F11)= pgcd(144, 89)  : 11 appels
pgcd(1071, 462)                : 4 appels

On lit $k-1$ appels pour la paire $(F_k,F_{k-1})$.

La complexité s'en déduit. Si $\mathrm{pgcd}(a,b)$ demande $k$ appels avec $a>b$, alors $a\ge F_{k+1}$ ; comme $F_k\sim {\phi }^k/\sqrt{5}$, il vient $k=O(\log a)$. Le nombre d'appels est donc logarithmique en la taille des entrées — et le pire cas est atteint, ce qui rend la borne exacte. C'est le théorème de Lamé, dont on vient de faire le seul calcul exigible : un encadrement élémentaire, sans théorème général, comme le demande le programme.