* $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$

 
* {$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.

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@}, {$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, dar3 / 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.

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$}.

Tema pentru acasa

h2. Tema pentru acasa

Cateva probleme care se rezolva intr-un mod sau altul folosing algoritmul lui Euclid sau algoritmul lui Euclid extins:

[1]Sgu 106: The Equation
[2]Sgu 137: Funny Strings
[3]Sgu 141: Jumping Joe
[4]Sgu 248: Integer Linear Programming
 
References
 
Visible links
1. http://acm.sgu.ru/problem.php?contest=0&problem=106
2. http://acm.sgu.ru/problem.php?contest=0&problem=137
3. http://acm.sgu.ru/problem.php?contest=0&problem=141
4. http://acm.sgu.ru/problem.php?contest=0&problem=248

 
* Sgu 106: "The Equation":http://acm.sgu.ru/problem.php?contest=0&problem=106
* Sgu 137: "Funny Strings":http://acm.sgu.ru/problem.php?contest=0&problem=137
* Sgu 141: "Jumping Joe":http://acm.sgu.ru/problem.php?contest=0&problem=141
* Sgu 248: "Integer Linear Programming":http://acm.sgu.ru/problem.php?contest=0&problem=248