numerelor a din Z ~n~ prime cu n, folosind doua structuri repetitive imbricate.
</p>

h2. Rezolvarea sistemelor de ecuatii modulare liniare generale
 
<p>
O problema mai generala care ne-ar putea interesa este rezolvarea sistemelor de ecuatii modulare
x <tex>\equiv</tex> a ~1~ (mod n ~1~ )
x <tex>\equiv</tex> a ~2~ (mod n ~2~ )
...
x <tex>\equiv</tex> a ~k~ (mod n ~k~ )
unde n ~1~ , n ~2~ , ..., n ~k~ nu sunt neaparat prime intre ele. Este suficienta generalizarea pentru un sistem de doua ecuatii. Din
x <tex>\equiv</tex> a ~1~ (mod n ~1~ )
x <tex>\equiv</tex> a ~2~ (mod n ~2~ )
se va obtine o a treia ecuatie x <tex>\equiv</tex> a ~s~ (mod n ~s~ ) satisfacuta de orice valoare x cu proprietatea ca exista b ~1~ , b ~2~ <tex>\in</tex> Z, astfel incat x = n ~1~ {*} b ~1~ + a ~1~ = n ~2~ {*} b ~2~ + a ~2~ . Pentru oricare astfel de valoare x, vom avea:
x <tex>\equiv</tex> a ~1~ (mod n ~1~ )
si
x <tex>\equiv</tex> a ~2~ (mod n ~2~ ).
Cu alte cuvinte, sistemul si noua ecuatie sunt echivalente.
</p>
 
<p>
Dacã deteriminam valoarea x minima care satisface sistemul de ecuatii modulare, toate celelalte solutii vor fi obtinute adunand la acesta un multiplu al celui mai mic multiplu comun al numerelor n ~1~ , n ~2~ , ..., n ~k~ .
Din n ~1~ {*} b ~1~ + a ~1~ = n ~2~ {*} b ~2~ + a ~2~ se obtine n ~1~ {*} b ~1~ - n ~2~ {*} b ~2~
= a ~2~ - a ~1~ .
Fie d = cmmdc(n ~1~ , n ~2~ ). Aplicand algoritmul extins al lui Euclid se determina valorile c ~1~ si c ~2~ astfel incat n ~1~ {*} c ~1~ + n ~2~ {*} c ~2~ = d.
Amplificand cu (a ~2~ - a ~1~ ) / d se obtine:
 n ~1~ {*} c ~1~ {*} (a ~2~ - a ~1~ ) / d + n ~2~ {*} c ~2~ {*} (a ~2~ - a ~1~ ) / d = a ~2~ - a ~1~ .
Am putea fi tentati sa credem ca b ~1~ = c ~1~ {*} (a ~2~ - a ~1~ ) / d si b ~2~ = c ~2~ {*} (a ~2~ - a ~1~ ), dar aceasta nu este intotdeauna cea mai buna solutie. Fie h = cmmmc(n ~1~, n ~2~ ), valoarea minima pentru care, dac x este solutie, atunci si x + h este solutie (cu alte
cuvinte, h este perioada).
Notând l = (a ~2~ - a ~1~ ) / d, observam ca n ~1~ {*} c ~1~ {*} l - n ~2~ {*} c ~
l + k · h - k · h = n1 · (c1 · l + k · h / n1) - n2 · (c2 · l + k · h
/ n2) satisface sistemul.
Dorim sã gãsim cea mai micã soluþie, deci valoarea c1
· l + k · h / n1 trebuie sã fie cât mai micã posibil. Fie m1 =
c1 · l + k · h / n1, iar n1 · m1 + b1 cea mai micã valoare care
satisface sistemul.
ªtim cã n1 · m1 + b1 < h ºi existã o singurã soluþie mai
micã decât h. Avem h / n1 > m1 ≥ 0, deci m1 = (c1 · l)
mod (h / n1).
Sistemul format din cele douã ecuaþii este satisfãcut
pentru valorile x = cmmmc(n1, n2) · i + n1 · m1 + b1, pentru
i ≥ 0.
Sistemul este astfel echivalent cu
x ≡ n1 · m1 + b1 (mod cmmmc(n1, n2)).
Pentru a rezolva un sistem de ecuaþii cu mai mult de
douã necunoscute este suficient sã aplicãm succesiv operaþiile
descrise mai sus, reducând perechile de ecuaþii la
una singurã echivalentã, pânã când rãmâne o singurã ecuaþie
modularã.
</p>

* acest articol trebuie imbunatatit