}
==

Pentru a fi inteles mai usor si eventual extins, este mai bine sa il punem sub forma recursiva

Pentru a fi inteles mai usor si eventual extins, este mai bine sa il punem sub forma recursiva:

== code(c) | void euclid(int a, int b, int *d)
{

Sa vedem cum functioneaza algoritmul lui Euclid. Se observa ca daca {$a<b$}, atunci $euclid(b, a % b)$ este de fapt {$euclid(b, a)$}.
Vom demonstra ca {$cmmdc(a, b) = cmmdc(b, a % b)$}. Notam $cmmdc(a, b)$ cu {$d$}. Scriem $a%b$ drept {$a - b * c$}, unde $c$ este parte intreaga din {$a / b$}. Cum $a$ si $b$ sunt divizibile cu {$d$}, atunci orice combinatie liniara a lor este divizibila cu {$d$}, inclusiv {$a - b * c = a%b$}.

Asta insa nu este de ajuns, putem aveam {$Z > d$}, $Z$ divizibil cu {$d$}, care sa fie {$cmmdc(b, a % b)$}. Insa atunci ar rezulta similar ca a e divizibil cu {$Z$}, deci {$Z = d = cmmdc(a, b)$}, Incalcand {$Z > d$}.

Asta insa nu este de ajuns, putem avea {$Z > d$}, $Z$ divizibil cu {$d$}, care sa fie {$cmmdc(b, a % b)$}. Insa atunci ar rezulta similar ca a e divizibil cu {$Z$}, deci {$Z = d = cmmdc(a, b)$}, Incalcand {$Z > d$}.

Astfel, algoritmul lucreaza reducand problema la numere din ce in ce mai mici, pana cand {$a % b = 0$}. Ca sa finalizam recurenta, daca $a$ este divizibil cu {$b$}, atunci este evident ca {$cmmdc(a, b)$} este {$b$}. In cod este un pic mai "ciudat", prindem acest caz doar dupa inca un apel recurent, cand {$b = 0$}. De fapt cred ca $cmmdc$ este definit pe numere strict pozitive, dar in informatica putem ocoli un pic matematica.