Euklidischer Algorithmus Rechner – ggT schrittweise mit Rest berechnen
Der Euklidische Algorithmus ist das klassische und effizienteste mathematische Verfahren zur Bestimmung des größten gemeinsamen Teilers (ggT) zweier natürlicher Zahlen. Anstatt aufwendige Primfaktorzerlegungen durchzuführen, nutzt der Algorithmus wiederholte Divisionen mit Rest (\(a = q \cdot b + r\)). Unser Rechner generiert die vollständige Rechenschritt-Tabelle, ideal für Schule, Klausuren und universitäre Prüfungen.
Funktionsweise: Division mit Rest (\(a = q \cdot b + r\))
Die mathematische Grundlage beruht auf der Erkenntnis: Wenn eine Zahl \(d\) sowohl \(a\) als auch \(b\) teilt, dann teilt \(d\) auch den Divisionsrest \(r = a \pmod b\). Daher gilt:
Schritt-für-Schritt-Ablauf:
- Start: Wählen Sie zwei positive ganze Zahlen \(a\) und \(b\) mit \(a \ge b\).
- Division: Führen Sie die ganzzahlige Division durch: \(a = q \cdot b + r\).
- Ersetzung: Wenn der Rest \(r > 0\) ist, setzen Sie \(a = b\) und \(b = r\) und wiederholen die Division.
- Abbruch: Sobald der Rest \(r = 0\) ist, ist der letzte Divisor \(b\) (der letzte von Null verschiedene Rest) der größte gemeinsame Teiler.
Ausführliches Rechenbeispiel: ggT(2260, 816)
Schritt 2: 816 = 1 × 628 + 188 (Rest: 188)
Schritt 3: 628 = 3 × 188 + 64 (Rest: 64)
Schritt 4: 188 = 2 × 64 + 60 (Rest: 60)
Schritt 5: 64 = 1 × 60 + 4 (Rest: 4)
Schritt 6: 60 = 15 × 4 + 0 (Rest: 0)
⇒ Der letzte Divisor ist 4. Somit gilt: ggT(2260, 816) = 4.
Warum ist der Euklidische Algorithmus so effizient?
Während die Bestimmung der Primfaktoren bei Zahlen mit hunderten Ziffern praktisch unmöglich ist, arbeitet der Euklidische Algorithmus in logarithmischer Laufzeit (\(\mathcal{O}(\log(\min(a, b)))\)). Nach dem Satz von Lamé (1844) benötigt der Euklidische Algorithmus für zwei Zahlen niemals mehr Schritte als das Fünffache der Anzahl der Ziffern der kleineren Zahl im Dezimalsystem. Der ungünstigste Fall (Worst Case) tritt auf, wenn zwei aufeinanderfolgende Fibonacci-Zahlen eingegeben werden (z. B. \(89\) und \(55\)).
Verwandte Rechner & Werkzeuge
- Wenn Sie den ggT von drei oder mehr Zahlen parallel berechnen möchten, nutzen Sie unseren allgemeinen ggT-Rechner.
- Wenn Sie alle Teiler als vollständige Menge auflisten möchten, besuchen Sie den Rechner für gemeinsame Faktoren.
- Für das kleinste gemeinsame Vielfache steht Ihnen unser kgV-Rechner zur Verfügung.
Häufig gestellte Fragen (FAQ)
Was ist der Euklidische Algorithmus?
Der Euklidische Algorithmus ist ein klassisches mathematisches Verfahren zur schrittweisen Bestimmung des größten gemeinsamen Teilers (ggT) zweier natürlicher Zahlen mittels wiederholter Division mit Rest.
Wie lautet die mathematische Formel für die Division mit Rest?
In jedem Schritt wird a = q · b + r berechnet, wobei q der ganzzahlige Quotient und r der verbleibende Rest mit 0 ≤ r < b ist. Anschließend ersetzt man a durch b und b durch r, bis der Rest r = 0 erreicht wird.
Warum ist der Euklidische Algorithmus schneller als die Primfaktorzerlegung?
Während die Primfaktorzerlegung großer Zahlen extrem rechenintensiv ist, benötigt der Euklidische Algorithmus nur logarithmisch viele Divisionen (höchstens proportional zur fünffachen Stellenanzahl der kleineren Zahl nach dem Satz von Lamé).
Was passiert, wenn eine der beiden Zahlen 0 ist?
Für jede positive ganze Zahl a gilt ggT(a, 0) = a, da jede Zahl die 0 teilt (0 / a = 0) und a der größte Teiler von sich selbst ist. Der Ausdruck ggT(0, 0) ist mathematisch undefiniert.
Zuletzt aktualisiert: 1. Oktober 2026