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