Fie d = cmmdc(n ~1~ , n ~2~ ). Aplicand "algoritmul extins al lui Euclid":http://infoarena.ro/Algoritmul-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, daca x este solutie, atunci si x + h este solutie (cu alte
cuvinte, h este perioada).

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, daca x este solutie, atunci si x + h este solutie (cu alte cuvinte, h este perioada).

Notand l = (a ~2~ - a ~1~ ) / d, observam ca n ~1~ {*} c ~1~ {*} l - n ~2~ {*} c ~2~ {*} l + k {*} h - k {*} h = n ~1~ {*} (c ~1~ {*} l + k {*} h / n ~1~ ) - n ~2~ {*} (c ~2~ {*} l + k {*} h/ n ~2~ ) satisface sistemul.
Dorim sa gasim cea mai mica solutie, deci valoarea c ~1~ {*} l + k {*} h / n ~1~ trebuie sa fie cat mai mica posibil. Fie m ~1~ = c ~1~ {*} l + k {*} h / n ~1~ , iar n ~1~ {*} m ~1~ + b ~1~ cea mai mica valoare care satisface sistemul.
Stim ca n ~1~ {*} m ~1~ + b ~1~ < h si exista o singura solutie mai mica decat h. Avem h / n ~1~ > m ~1~ <tex>\geq</tex> 0, deci m ~1~ = (c ~1~ {*} l) mod (h / n ~1~ ).