}
==

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.

h2. Impartire modulara

Acum pentru o aplicatie interesanta, impartirea modulara. Nu voi intra in detalii, pe scurt aritmetica modulara este aritmetica in care toate valorile se iau modulo un anumit numar {$n$}. Spre exemplu, in {@modulo 7@}, {$3 = 10$}. Similar, rezultatele tuturor operatiilor se iau in modul: {$4 + 5 = 2$}, {$3 * 5 = 1$} etc.

Acum pentru o aplicatie interesanta, impartirea modulara. Nu voi intra in detalii, pe scurt aritmetica modulara este aritmetica in care toate valorile se iau modulo un anumit numar {$n$}. Spre exemplu, in {@modulo 7@},avem {$3 = 10$}. Similar, rezultatele tuturor operatiilor se iau in modul: {$4 + 5 = 2$}, {$3 * 5 = 1$} etc.

Cum putem defini insa impartirea in modulo? Evident, {$6 / 2$} este tot {$3$}, dar $3 / 4$ cu cat este egal? De obicei impartirea este definita ca operatia inversa a inmultirii, similar cum scaderea este operatia inversa a adunarii. Astfel, daca {$a / b = c$} atunci {$b * c = a$}. Prin algoritmul lui Euclid putem afla $x$ si $y$ astfel incat {$n * x + b * y = cmmdc(n, b)$}, unde $n$ este modulul. Totul e modulo {$n$}, asa ca putem ignora {$x * n$}. Atunci {$c = y * a / cmmdc(n, b)$}. Daca $a$ nu este divizibil cu {$cmmdc(n, b)$}, atunci $c$ nu exista. Intradevar, nu exista $c$ pentru care $3 * c = 4$ modulo {$6$}.

3681