Direkt zum Inhalt

Lexikon der Mathematik: euklidischer Algorithmus

eine geometrisch motivierte Methode zur Konstruktion des ggT zweier ganzer Zahlen a > b > 0.

Man setzt r0 = a und r1 = b und definiert r2 als Rest bei Division von r0 durch r1 (Division mit Rest): \begin{eqnarray}{r}_{0}=c{r}_{1}+{r}_{2}\end{eqnarray} mit ganzen Zahlen c, r2 und 0 ≤ r2r1.

Solange rk ≠ 0 berechnet man induktiv rk+1 als Rest bei Division von rk−1 durch rk. Wegen 0 ≤ rk+1 < rk ist irgendwann rk+1 = 0; dann stoppt man das Verfahren, und es gilt rk = ggT(a, b).

Die notwendigen algebraischen Voraussetzungen an den Rechenbereich, damit der euklidische Algorithmus durchführbar ist und nach endlich vielen Schritten zu einem Ergebnis kommt, sind im Begriff des euklidischen Rings kondensiert.

Der euklidische Algorithmus ist seinem Ursprung nach eine geometrische Methode zur Konstruktion eines gemeinsamen Teilers zweier (evtl. durch geometrische Konstruktionen gegebenen) Streckenlängen a, b. Man nennt diesen Algorithmus auch einen Divisionsalgorithmus.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos