Euklidischer Algorithmus
Du hast vom euklidischen Algorithmus gehört und möchtest verstehen, wie er funktioniert? Hier bekommst du eine Schritt-für-Schritt-Anleitung! Schau dir auch gleich unser Video dazu an.
Inhaltsübersicht
Euklidischer Algorithmus einfach erklärt
Den euklidischen Algorithmus verwendest du, um den größten gemeinsamen Teiler (ggT) von zwei Zahlen zu bestimmen. Deshalb kannst du ihn auch ggT Algorithmus nennen.
Am folgenden Beispiel siehst du, wie man den euklidischen Algorithmus durchführt.
Was ist der ggT von 132 und 28?
| Rechenschritt Euklidischer Algorithmus | Erklärung euklidischer Algorithmus |
| 132 = 4 · 28 + 20 |
Schritt 1: |
| 28 = 1 · 20 + 8 |
Schritt 2: Nun teilst du 28 durch 20. Der Divisor aus Schritt 1 (28) wird also zum Dividenden und der vorige Rest (20) zum Divisor. 28 : 20 = 1 Rest 8 Damit kannst du nun 28 als 1 · 20 + 8 darstellen. |
| 20 = 2 · 8 + 4 | In den folgenden Schritten wiederholst du das Prinzip aus Schritt 2: Alter Divisor (20) wird neuer Dividend, alter Rest (8) wird neuer Divisor. |
| 8 = 2 · 4 + 0 |
Letzter Schritt: Das wiederholst du so lange, bis die Division den Rest 0 ergibt. Nun kannst du den gesuchten ggT ganz einfach ablesen: Es ist der Divisor in der letzten Rechnung, also der letzte Rest, der nicht 0 war. |
Das Ergebnis des Euklid Algorithmus ist also ggT(132,28) = 4.
Euklidischer Algorithmus — Mathematische Schreibweise
In allgemeiner mathematischer Form aufgeschrieben sieht der euklidische Algorithmus so aus:
Gegeben sind zwei Zahlen a und b und gesucht ist ihr größter gemeinsamer Teiler ggT(a,b).
| Rechenschritt Euklidischer Algorithmus | Erklärung euklidischer Algorithmus |
| a = q0 · b + r0 | Die Division mit Rest a : b liefert einen Quotienten q0 und einen Rest r0 |
| b = q1 · r0 + r1 | Ab dann folgst du immer demselben Prinzip:
|
| r0 = q2 · r1 + r2 | |
| … | |
| rn-3 = qn-1 · rn-2 + rn-1 | Der Rest, und damit auch der neue Divisor, wird in jedem Schritt kleiner. Spätestens wenn du durch 1 teilst, erhältst du Rest 0. Somit endet der Euklid Algorithmus immer nach endlich vielen Schritten. |
| rn-2 = qn · rn-1 + 0 | Wenn der Rest 0 ist, kannst du den ggT direkt ablesen: Es ist der Divisor im letzten Schritt des euklidischen Algorithmus, also der letzte Rest, der nicht 0 ist. |
Merke: Falls die Division tatsächlich erst mit dem Divisor 1 Rest 0 ergibt, bedeutet das, dass die Zahlen a und b die 1 als größten gemeinsamen Teiler haben.
In diesem Fall nennt man a und b dann teilerfremd.
Gegeben: Zwei Zahlen a und b
Gesucht: ggT(a,b)
-
- Division mit Rest a : b.
-
Divisor → Dividend,
Rest → Divisor.
Damit: wieder Division mit Rest. - Wiederhole Schritt 2, bis Rest 0 herauskommt.
- ggT(a,b) = letzter Rest, der nicht 0 war.
Übrigens: Durch Umstellen der Formel a · b = ggT(a,b) · kgV(a,b) kannst du das Ergebnis des euklidischen Algorithmus auch verwenden, um das kleinste gemeinsame Vielfache (kgV) von zwei Zahlen zu bestimmen.
Chinesischer Restsatz
Du verstehst jetzt, was du tun sollst, wenn in einer Aufgabe etwas mit „Euklidischer Algorithmus“ steht? Super! Dann schau unbedingt auch mal bei unserem Beitrag zum chinesischen Restsatz vorbei!
