h2. Scurta istorie

Se considera un numar de obiecte. Impartindu-le in grupuri de cate trei, raman doua negrupate. Impartindu-le in grupuri de cate cinci, raman trei. Impartindu-le in grupuri de cate sapte, raman doua. Cate obiecte sunt? Aceasta este problema enuntata de matematicianul chinez Sun-Tsu in secolul al IV-lea al erei noastre. El a demonstrat ca toate numerele naturale de forma $23 + 105 {*} k$ reprezinta solutiile acestei probleme. Din pacate nu putem sti daca a dezvoltat o metoda generala pentru a rezolva astfel de sisteme de ecuatii modulare. Aceasta este tema tratata in articolul care urmeaza.

Se considera un numar de obiecte. Impartindu-le in grupuri de cate trei, raman doua negrupate. Impartindu-le in grupuri de cate cinci, raman trei. Impartindu-le in grupuri de cate sapte, raman doua. Cate obiecte sunt? Aceasta este problema enuntata de matematicianul chinez Sun-Tsu in secolul al IV-lea al erei noastre. El a demonstrat ca toate numerele naturale de forma <tex>23 + 105 * k</tex> reprezinta solutiile acestei probleme. Din pacate nu putem sti daca a dezvoltat o metoda generala pentru a rezolva astfel de sisteme de ecuatii modulare. Aceasta este tema tratata in articolul care urmeaza.

h2. Definitie

Mai ramane de verificat daca valoarea <tex>x</tex> este unica. Fie <tex>x'</tex> o alta solutie; avem <tex>x < n</tex> si <tex>x' < n</tex>. Daca <tex>x \equiv a_i (mod\ n_i)</tex> si <tex>x' \equiv a_i (mod\ n_i)</tex>, <tex>\forall i \in \{1, 2, ..., k\}</tex>, presupunand ca <tex>x' < x</tex>, avem <tex>x'-x \equiv 0 (mod\ n_i)</tex>, <tex>\forall i \in \{1, 2, ... k\}</tex>. Datorita faptului ca numerele <tex>n_i</tex> sunt relativ prime, rezulta ca <tex>x'-x = k * n</tex>, <tex>k \in \mathbb{Z}^*</tex>, deci <tex>x'-x \geq n</tex>, ceea ce contrazice ipoteza initiala. Asadar, solutia este unica, asa cum poate fi dedus si din t.c.r. Mai mult, verificand daca se pastreaza corespondenta in cazul aplicarii operatorilor, demonstrarea t.c.r. poate fi usor incheiata.

Pentru calcularea inversului modular al unui numar din $Z{~n~}$ , de obicei se foloseste "algoritmul extins al lui Euclid":http://infoarena.ro/Algoritmul-lui-Euclid. Evident, pentru ca acest invers sa existe, trebuie sa avem $cmmdc(a, n) = 1$. Aplicam algoritmul extins al lui Euclid si determinam $x$ si $y$ astfel incat $a {*} x + n {*} y = 1$ si obtinem $a^-1^ = x mod n$; pentru a verifica observam ca egalitatea $a^-1^ = x mod n$ este echivalenta cu $a {*} (x mod n)$ <tex>\equiv</tex> $1 (mod n)$ care, la randul sau, este echivalenta cu $a {*} x$ <tex>\equiv</tex> $1 (mod n)$. Aceasta ultima afirmatie este evident adevarata deoarece avem $a {*} x + n {*} y = 1$.
Pentru valori mici ale lui $n$, este recomandata preprocesarea "bruta" a inverselor tuturor numerelor a din $Z{~n~}$ prime cu $n$, folosind doua structuri repetitive imbricate.

Pentru calcularea inversului modular al unui numar din <tex>\mathbb{Z}_n</tex>, de obicei se foloseste "algoritmul extins al lui Euclid":http://infoarena.ro/Algoritmul-lui-Euclid. Evident, pentru ca acest invers sa existe, trebuie sa avem <tex>cmmdc(a, n) = 1</tex>. Aplicam algoritmul extins al lui Euclid si determinam <tex>x</tex> si <tex>y</tex> astfel incat <tex>a * x + n * y = 1</tex> si obtinem <tex>a^{-1} = x\ mod\ n</tex>; pentru a verifica observam ca egalitatea <tex>a^{-1} = x\ mod\ n</tex> este echivalenta cu <tex>a * (x\ mod\ n) \equiv 1 (mod\ n)</tex> care, la randul sau, este echivalenta cu <tex>a * x \equiv 1 (mod\ n)</tex>. Aceasta ultima afirmatie este evident adevarata deoarece avem <tex>a * x + n * y = 1</tex>.
Pentru valori mici ale lui <tex>n</tex>, este recomandata preprocesarea "bruta" a inverselor tuturor numerelor <tex>a</tex> din <tex>\mathbb{Z}_n</tex> prime cu <tex>n</tex>, folosind doua structuri repetitive imbricate.

h2. Rezolvarea sistemelor de ecuatii modulare liniare generale