Erweiterter Euklidischer Algorithmus
Erweiterter euklidischer Algorithmus: Berechnen Sie mit der Methode von Euklid den ggT und zwei ganze Zahlen
Euklid von Alexandria entwickelte das Verfahren ungefähr 300 vor Christus. Seine Beschäftigung mit dem Thema Primzahlen führte ihn zum größten gemeinsamen Teiler. Zwei natürliche Zahlen besitzen mindestens eine Zahl, durch die beide teilbar sind. Dieser gemeinsame Divisor ist in vielen Fällen, beispielsweise bei zwei Primzahlen, eins. Oftmals gibt es größere Nummern, die als gemeinsamen Divisor agieren. Die Zahlen 18 und 24 haben diverse gemeinsame Teiler. Der Größte von ihnen ist sechs.
Stell uns deine Frage. Wir antworten dir schnellstens...
Mit der Methode von Euklid ermitteln Sie sorgfältig in verschiedenen Schritten den größten gemeinsamen Teiler (ggT) zweier natürlicher Zahlen a und b. Dazu teilen Sie die größere der beiden Zahlen durch die kleinere. Der Divisor ist der ggT, falls die Division aufgeht. Bleibt ein Rest, ist dieser der neue Divisor und der alte ist der aktuelle Dividend. Sie setzen das Verfahren so häufig fort, bis der ggT feststeht. Das System dient ebenfalls zur linearen Darstellung des ggTs.
Was ist der größte gemeinsame Teiler?
Der ggT ist die größte natürlich Zahl, durch die Sie zwei ganze Zahlen ohne Rest teilen. Der größte gemeinsame Teiler m von zwei ganzen Zahlen a und b ist Teiler beider Zahlen. Jede andere ganze Zahl, die a und b teilt, ist somit Teiler von m. Im Ring der ganzen Zahlen ist der ggT normiert auf die größte Zahl, auf die die genannten Eigenschaften zutreffen. Bei einfacheren Zahlen bestimmen Sie den ggT mittels Primfaktor-Zerlegung. Bei komplizierten Zahlen nehmen Sie den erweiterten euklidischen Algorithmus zu Hilfe.
Das Lemma von Bézout besagt, dass Sie den größten gemeinsame Teiler zweier Zahlen m und n als lineare Kombination ganzzahliger Koeffizienten darstellen.
ggT (m, n) = s * m + t * n mit s, t ? von Z.
Für die Berechnung der Koeffizienten s und t wenden Sie den erweiterten euklidischen Algorithmus an. In der Schule brauchen Sie den ggT zum Kürzen von Brüchen. Dies geschieht oftmals in Zusammenhang mit dem kgV, dem kleinsten gemeinsamen Vielfachen.
Erweiterter euklidischer Algorithmus berechnet neben dem ggT von a und b die ganzen Zahlen s und t
Der euklidische Algorithmus ist ein Teilgebiet der Zahlentheorie. Die erweiterte Form berechnet zusätzlich zwei ganze Zahlen s und t, die folgende Gleichung erfüllen: ggT (a, b) = s*a + t*b. Die Berechnung inverser Elemente in ganzzahligen Restklassenringen ist das Haupteinsatzgebiet des Algorithmus. Er ermittelt das Tripel d = ggT (a, b), s, t. Ist die Lösung d = 1, bedeutet dies 1 = t*b (mod a). In diesem Fall ist t das multiplikative Inverse von b modulo a.
Wenn d ? 1 hat b modulo a kein inverses Element. Der erweiterte euklidische Algorithmus ist die Grundlage für den chinesischen Restsatz und die diophantischen Gleichungen. Auf Ersterem basiert der bedeutende Trick der kleinen Primzahlen in der berechenbaren Algebra und liefert einen konstruktiven Beweis für das Lemma von Bézout.
Wie funktioniert der erweiterte euklidische Algorithmus?
Wird ein erweiterter euklidischer Algorithmus berechnet, so bezieht sich seine bekannteste Form auf die Menge der ganzen Zahlen. Er ist in jedem Ring anwendbar, wo eine Division mit kleinstem Rest möglich ist. Sehen Sie hier ein Beispiel:
Die Suche des ggTs der Zahlen 115 und 78.
Euklidischer Algorithmus aufgelöst nach Resten
115 = 1 * 78 + 37 37 = 115 – 1 * 78 (I)
78 = 3 * 37 + 4 4 = 78 – 2 * 37 (II)
37 = 9 * 4 + 1 1 = 37 – 9 * 4 (III)
4 = 4 * 1
Der Rest ist als Differenz der beiden anderen Terme dargestellt. Für die Berechnung des Ergebnisses nehmen wir die letzte Gleichung mit dem Ergebnis 1 als Basis.
Der größte gemeinsame Teiler der Zahlen 115 und 78 ist 1. Es existieren keine weiteren gemeinsamen Divisoren.
ggT (115, 78) = 1
1 = 37 – 9 * 4
1 = 37 – 9 * (78 – 2 * 37) = -9 * 78 + 19 * 37
1 = -9 * 78 + 171 *(115 – 1 * 78) = 171 * 115 – 180 * 78
1 = (19) * 115 + (-28) * 78
Die Gleichung ggT (a, b) = s * a + t * b ergibt:
ggT (115, 78) = (19) * 115 + (-28) * 78
Tabellarische Darstellung der Berechnung
Übersichtlich und in tabellarischer Form lässt sich ein erweiterter euklidischer Algorithmus berechnen. Mit etwas Übung ist dies die einfachste Form seiner Darstellung. Die verschiedenen Buchstaben haben alle ihre Bedeutung. i kennzeichnet eine Hilfszeile. Damit sind die Rechenschritte fortlaufend nummeriert. Die ersten beiden r’s sind die zwei Zahlen, deren ggT Sie ermitteln. Die weiteren r’s beziehen sich auf die Reste der vorherigen Rechnung. s und t stammen aus der oben genannten Gleichung. s und t der untersten Zeile entsprechen den Koeffizienten des Endergebnisses. q ist der Faktor, der angibt, wie viel Mal r im r der oberen Zeile enthalten ist. Das letztgenannte r ist der ggT.
| i | r | q | s | t |
| 0 | 115 | – | 1 | 0 |
| 1 | 78 | 1 | 0 | 1 |
| 2 | 37 | 2 | 1 | -1 |
| 3 | 4 | 9 | -2 | 3 |
| 4 | 1 | 4 | 19 | -28 |
Das erste r entspricht der größeren der beiden gegebenen Zahlen. Die Nächstkleinere folgt in der zweiten Zeile. 78 ist einmal in 115 enthalten. Um die Zahl zu vervollständigen, fehlen 37. Diese Nummer bildet das dritte r. Eine Zeile weiter unten ergibt vier mal neun 36. Der neue Rest ist 1 und bildet das letzte r in der Kette. In der letzten Zeile sind s = 19 und t = -28. Zusammen mit den beiden gegebenen Zahlen 115 und 78 vervollständigen Sie die Anfangsgleichung: ggT (115, 78) = 19 * 115 – 28 * 78.
Erweiterter euklidischer Algorithmus: seine Darstellung mit Matrizen
Mithilfe von Matrizen lässt sich als praktisches Verfahren ein erweiterter euklidischer Algorithmus berechnen und darstellen. Die Grundlage dazu bietet die Formel mk = nk * qk + rk. mk ist die Division mit Rest, die im Schritt k auszuführen ist. Die Bildung eines Spaltenvektors aus m und n führt zu einer Darstellung mit Übergangs-Matrix.
mk+1 0 1 * mk
nk+1 1 -qk nk
Mit den Zahlen im obigen Beispiel entsteht folgendes Resultat:
1 0 0 1 0 1 0 1
0 1 1 -1 1 -1 1 -2
115 78 78 37
1 -2 0 1 -2 19 0 1 19 -78
-1 3 1 -9 3 -28 1 -4 -28 115
37 4 4 1 1 0
Wurde von Ihnen ein erweiterter euklidischer Algorithmus berechnet, stellen Sie das Resultat auf eine der drei verschiedenen Arten dar. Mit dem Rechner geschieht das automatisch mit nur einem Klick. Er nützt für das Lösen schulischer Aufgaben oder anderer Herausforderungen. Sie erhalten als Ergebnis den ggT sowie die Variablen s und t für die von Ihnen gewünschten beiden Zahlen. Das System geht auf eine Erfindung aus der Zeit vor unserer Zeitrechnung zurück.
Wer war Euklid?
Euklid von Alexandria lebte vermutlich im 4. Jahrhundert vor Christus. Über sein Leben sind wenige Details bekannt. Annahmen zufolge arbeitete er zur Zeit Ptolemaios I. im ägyptischen Alexandria. Ein Verzeichnis von Mathematikern bei Proklos gibt Aufschluss über seine Lebenszeit. Andere Angaben besagen, er sei etwas jünger als Archimedes gewesen. Historiker schätzen sein Geburtsjahr auf 360 vor Christus. In Athen wuchs er auf und absolvierte seine Ausbildung vermutlich an Platons Akademie. Er ist nicht mit Euklid von Megara zu verwechseln.
Das Werk „Elemente“
Seine Werke zeigen ein imposantes Sammelsurium von mathematischen und musikalischen Erkenntnissen. Das Berühmteste unter ihnen ist „Elemente“. Es vereint das gesamte Wissen griechischer Mathematik zu jener Zeit. Inhalte sind beispielsweise die Konstruktion natürlicher Zahlen und geometrischer Objekte. Euklid untersuchte Eigenschaften bestimmter Größen mit Axiomen und Postulaten. Seine strenge Beweisführung in diesem Werk ist Vorbild für die spätere Mathematik. Die einheitliche Darstellung und die Sammlung des mathematischen Wissens verschiedener Mathematiker ist eine vorbildliche Leistung.
In „Elemente“ sind die Konzepte der Teilbarkeit und des größten gemeinsamen Teilers verewigt. Wie ein erweiterter euklidischer Algorithmus berechnet wird, ist darin ausführlich beschrieben. Euklid bewies in seinem nach ihm benannten Satz, dass es unendlich viele Primzahlen gibt. Weitere mathematische Strukturen sind nach ihm benannt.
Der euklidische Ring
Der euklidische Ring ist ein Konstrukt, in dem eine verallgemeinerte Division mit Rest ähnlich der der ganzen Zahlen vorkommt. Mithilfe des erweiterten euklidischen Algorithmus berechnen Sie den größten gemeinsamen Teiler zweier Ringelemente. In ihm sind assoziierte Elemente identisch bewertet. Jeder euklidische Ring besitzt eine minimale euklidische Norm. Dazu existiert ein Algorithmus. Er dient zur iterativen Bestimmung des minimalen euklidischen Betrags. Ein Beispiel für einen euklidischen Ring sind die ganzen Zahlen. Auch jeder Körper ist ein euklidischer Ring.
Euklid und die Musik
Euklid machte sich auch in der Musiktheorie einen Namen. Sein Werk „Die Teilung des Kanon“ beschreibt er die Theorie von Archytas und stellt sie auf die Basis von Frequenz und Schwingung. Er bewies die Irrationalität beliebiger Wurzeln und beschäftigte sich mit dem Parallelenaxiom. Die daraus entstandenen exakten mathematischen Begriffe und die verschiedenen Beweisführungen sind noch heute in der Wissenschaft von großer Bedeutung. Seine Musiktheorie baut auf der Arithmetik auf.