Euklidsch Algorithmus

Vun Wikipedia
Wesseln na: Navigatschoon, Söök

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) a1 un a2 geven, denn rekent een so:

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

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

a1 = a2\cdotq2 + a3.

Wenn nu a3 nich 0 is, denn maakt wi wieder und deelt a2 dörch a3 un hebbt denn:

a2 = a3\cdotq3 + a4.
...

So gaht dat jümmer wieder, bit wi

an-1 = an\cdotqn + an+1

hebbt, wobi nu de Rest an+1=0 is. (Dat mutt mal so kamen, wiel de Tallen a1, a2, a3, ... (odder de Grad vun a1, a2, a3, ...) 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) an en gröttster gemeener Deler vun a1 un a2.