Euklidischer Algorithmus

Erklärung von Serlo Education e. V., lizenziert unter CC BY-SA 4.0 – Original bei Serlo, CC BY-SA 4.0, übernommen am 2026-09-03.

Der Euklidische Algorithmus ist sehr hilfreich zur Bestimmung des größten gemeinsamen Teilers (ggT).

Allgemeine mathematische Schreibweise

Das ganze noch in einer allgemeinen mathematischen Schreibweise:

Man nehme an, dass \(a\) größer als \(b\) ist:

Geogebra File: https://assets.serlo.org/legacy/6716_szb0LAlyDI.xml

Führe dies so oft durch, bis bei einer Rechnung Rest \(0\) herauskommt.

Man kann hier ein Schema erkennen:

Erklärung am Beispiel

Man hat die zwei Zahlen \(a=1071\) und \(b=1029\).

Geogebra File: https://assets.serlo.org/legacy/6732_yAf2CCUneY.xml

Also ist  \(r_1=21\) der größte gemeinsame Teiler von \(1071\) und \(1029\):

\(\text{ggT}(1071,1029)=21\)

Weitere Begriffe

Vergleich von Dezimalzahlen 2x2-Matrizen mit einem Vektor multiplizieren Ableitung Absolute Häufigkeit Abstand eines Punktes zu einer Geraden Abstand zweier Punkte berechnen Addition Allgemeine Form und Scheitelform einer quadratischen Funktion Allgemeine Potenzfunktion Amplitude und Ruhelage der trigonometrischen Funktionen Anpassung der Ergebnismenge Assoziativgesetz