}
==

Sa vedem cum functioneaza algoritmul lui Euclid. Se observa ca daca {$a< b$}, atunci $euclid(b, a % b)$ este de fapt {$euclid(b, a)$}.

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 {$b$}, 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$}.

h2. Euclid extins

Acest algoritm poate fi extins, in sensul gasirii $x$ si $y$ astfel incat {$a * x + b * y = d$}. In acest articol vom incerca sa deducem modul de calculare al lui x si y. Cei grabiti sau certati cu matematica pot sari direct la codul sursa, dar vor avea probleme in a tine minte algoritmul pe viitor.

Acest algoritm poate fi extins, in sensul gasirii $x$ si $y$ astfel incat {$a * x + b * y = d$}. In acest articol vom incerca sa deducem modul de calculare al lui $x$ si {$y$}. Cei grabiti sau certati cu matematica pot sari direct la codul sursa, dar vor avea probleme in a tine minte algoritmul pe viitor.

Vom extinde procedura recursiva de calculare a cmmdc pentru e include si x si y. Calculam x si y incepand de la "capatul recurentei". Daca b = 0, atunci a * 1 + b * 0 = a(cmmdc) evident, asa ca initial x = 1 si y = 0. Incercam sa calculam x, y in functie de x0, y0 obtinuti pentru b, a % b. Noi stim urmatoarele:
b * x0 + (a % b) * y0 = d
a * x + b * y = d
Trebuie sa aflam o solutie pentru x si y. Vom nota ca mai sus parte intreaga din a / b cu c.
b * x0 + (a - b * c) * y0 = a * x + b * y
b * (x0 - c * y0 - y) = a * (x - y0)
O solutie este acum evidenta (Una, sunt o infinitate de perechi x, y)
x0 - c * y0 - y = 0, De unde rezulta y = x0 - c * y0
x - y0 = 0, De unde rezulta x = y0

Vom extinde procedura recursiva de calculare a $cmmdc$ pentru e include si $x$ si {$y$}. Calculam $x$ si $y$ incepand de la "capatul recurentei". Daca {$b = 0$}, atunci $a * 1 + b * 0 = a(cmmdc)$ evident, asa ca initial $x = 1$ si {$y = 0$}. Incercam sa calculam {$x$}, $y$ in functie de {$x0$}, $y0$ obtinuti pentru {$b$}, {$a % b$}. Noi stim urmatoarele:
 
* $b * x0 + (a % b) * y0 = d$
* $a * x + b * y = d$
 
Trebuie sa aflam o solutie pentru $x$ si {$y$}. Vom nota ca mai sus parte intreaga din $a / b$ cu {$c$}.
 
* $b * x0 + (a - b * c) * y0 = a * x + b * y$
* $b * (x0 - c * y0 - y) = a * (x - y0)$
 
O solutie este acum evidenta (Una, sunt o infinitate de perechi {$x, y$})
{$x0 - c * y0 - y = 0$}, De unde rezulta $y = x0 - c * y0$
{$x - y0 = 0$}, De unde rezulta $x = y0$

Acum nu mai pare asa de "magic", nu?

Sursa modificata pentru a calcula si x si y nu este mult mai complexa. Acum intelegeti de ce am trimis d ca pointer mai sus, si de ce am folosit varianta recursiva a algoritmului lui euclid. Implementat iterativ, este nevoie de un vector care sa tina toate valorile c (a / b) obtinute pe parcurs.

Sursa modificata pentru a calcula si $x$ si $y$ nu este mult mai complexa. Acum intelegeti de ce am trimis $d$ ca pointer mai sus, si de ce am folosit varianta recursiva a algoritmului lui euclid. Implementat iterativ, este nevoie de un vector care sa tina toate valorile $c$ ({$a / b$}) obtinute pe parcurs.

Nota pentru pascalisti: in C nu exista div, impartirea intre int-uri este automat si impartire intreaga (div din pascal).

== code(c) |

void euclid(int a, int b, int *d, int *x, int *y)
{

if (b == 0) {
*d = a;
*x = 1;
*y = 0;
} else {
int x0, y0;
euclid(b, a % b, d, &x0, &y0);
*x = y0;
*y = x0 - (a / b) * y0;
}

    if (b == 0) {
        *d = a;
        *x = 1;
        *y = 0;
    } else {
        int x0, y0;
        euclid(b, a % b, d, &x0, &y0);
        *x = y0;
        *y = x0 - (a / b) * y0;
    }

}

==

Impartire modulara

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.