Euklidsch Algorithmus

Mit den Euklidschen Algorithmus kann een den gröttsten gemeenen Deler vun twee helen Tallen (odder ok Polynomen) utreken.

Sünd twee Tallen (odder Polynomen) a₁ un a₂ geven, denn rekent een so:

Wi köönt annehmen, dat dat (vun den Bedrag her) Gröttere vun a₁ un a₂ de Tall a₁ is (bi Polynomen, dat de Grad vun a₁ grötter odder dersülvige is as de Grad vun a₂) .

Nu deelt wi a₁ dörch a₂, wat us in de mehrsten Fäll en Rest a₃ gifft. (Dat is akkerat denn de Fall, wenn a₂ nich de gröttste gemeene Deler vun a₁ un a₂ is.) Wi hebbt:

a₁ = a₂ · q₂ + a₃.

Wenn nu a₃ nich 0 is, denn maakt wi wieder und deelt a₂ dörch a₃ un hebbt denn:

a₂ = a₃ · q₃ + a₄.

…

So gaht dat jümmer wieder, bit wi

a_n-1 = a_n · q_n + a_n+1

hebbt, wobi nu de Rest a_n+1=0 is. (Dat mutt mal so kamen, wiel de Tallen a₁, a₂, a₃, … (odder de Grad vun a₁, a₂, a₃, …) jümmer lütter warrt, un wenn een dörch 1 (odder en Polynom mit Grad 0) deelt, denn is de Rest jümmer 0.)

Denn is de Tall (oder dat Polynom) a_n en gröttster gemeener Deler vun a₁ un a₂.