[Songtext zu „Euklidischer Algorithmus“]
[Part 1]
Vielleicht willst oder sollst du mal den ggT berechnen
Also den größten gemeinsamen Teiler, aber mal echt, wenn
Du erstmal deine Zahl'n in ihre Primfaktor'n zerlegst
Dann siehst du schnell den ggT, aber wenn du mal überlegst
Wie viel Aufwand es bedeutet, Primfaktoren zu suchen
Solltest du vielleicht liebеr Euklids Algorithmus versuchen
Weil sich damit dеr ggT durch bisschen Division mit Rest
In nur wenigen Schritten berechnen lässt
[Hook]
Man zieht die kleine Zahl so oft von der großen ab
Wie sie reinpasst, und im Ergebnis hat
Man den Rest und den nimmt man als die nächste Zahl
Und mit den letzten beiden macht man das jetzt nochmal
Man zieht die kleine Zahl so oft von der großen ab
Wie sie reinpasst, und im Ergebnis hat
Man den Rest und den nimmt man als die nächste Zahl
Und mit den letzten beiden macht man das jetzt nochmal
Man zieht die kleine Zahl so oft von der großen ab
Wie sie reinpasst, und im Ergebnis hat
Man den Rest und den nimmt man als die nächste Zahl
Und mit den letzten beiden macht man das jetzt nochmal
Man zieht die kleine Zahl so oft von der großen ab
Bis man hier am Ende kein'n Rest mehr hat
Und die letzte Zahl, die ich vor der Null seh'
Ist der ggT
[Part 2]
Ok, durch Rechnen mit dem Rest bei Division
Auch Modulo genannt, kannst du das am Rechner schon
Mit nur wenig Aufwand super einfach implementieren
Aber warum wird der Algorithmus immer funktionieren?
Nun: Ist ein Teiler in zwei Zahlen enthalten
Dann kann ich ihn bei plus und minus hier mit Klammern abspalten
Bei Differenzen und Summen können wir also festhalten:
Gemeinsame Teiler bleiben dabei erhalten
Haben a und b einen gemeinsamen Teiler
Dann steckt der auch in jedem Vielfachen von b, und weiter
Ist der Teiler dann auch in der Differenz mit drin
Und bei b ja sowieso, und jetzt schau mal hin
Was passiert, wenn wir von der Aussage unten ausgehen
In jedem Vielfachen und in der Summe könn'n wir wieder sehen
Dass der Teiler dabeibleibt, doch die Summe ist a
Und da der Teiler auch im b steckt, wird also klar:
Die gemeinsamen Teiler sind also beide Male gleich
Wodurch ich garantiert den gleichen ggT erreich'
Wenn ich n so groß wähle, wie oft b in a reinpasst
Ist das ein Schritt im Algorithmus, der es jedes Mal schafft
Dass der Rest immer echt kleiner ist als b
Weshalb ich immer kleinere Zahlen und irgendwann die Null seh'
Doch dann ist b selbst gemeinsamer Teiler und ich versteh':
Einen größ'ren gibt es nicht, ich hab' den ggT
[Hook]
Man zieht die kleine Zahl so oft von der großen ab
Wie sie reinpasst, und im Ergebnis hat
Man den Rest und den nimmt man als die nächste Zahl
Und mit den letzten beiden macht man das jetzt nochmal
Man zieht die kleine Zahl so oft von der großen ab
Wie sie reinpasst, und im Ergebnis hat
Man den Rest und den nimmt man als die nächste Zahl
Und mit den letzten beiden macht man das jetzt nochmal
Man zieht die kleine Zahl so oft von der großen ab
Wie sie reinpasst, und im Ergebnis hat
Man den Rest und den nimmt man als die nächste Zahl
Und mit den letzten beiden macht man das jetzt nochmal
Man zieht die kleine Zahl so oft von der großen ab
Bis man hier am Ende kein'n Rest mehr hat
Und die letzte Zahl, die ich vor der Null seh'
Ist der ggT
[Bridge]
Und es gibt auch noch 'ne erweiterte Version
Mit a, 1, 0 und b, 0, 1 habe ich schon
Den Anfang und rechne ich jetzt zeilenweise, seh'
Ich am Ende hier aus a und b
Eine Linearkombination zum ggT
[Hook]
Man zieht die kleine Zahl so oft von der großen ab
Wie sie reinpasst, und im Ergebnis hat
Man den Rest und den nimmt man als die nächste Zahl
Und mit den letzten beiden macht man das jetzt nochmal
Man zieht die kleine Zahl so oft von der großen ab
Wie sie reinpasst, und im Ergebnis hat
Man den Rest und den nimmt man als die nächste Zahl
Und mit den letzten beiden macht man das jetzt nochmal
Man zieht die kleine Zahl so oft von der großen ab
Wie sie reinpasst, und im Ergebnis hat
Man den Rest und den nimmt man als die nächste Zahl
Und mit den letzten beiden macht man das jetzt nochmal
Man zieht die kleine Zahl so oft von der großen ab
Bis man hier am Ende kein'n Rest mehr hat
Und die letzte Zahl, die ich vor der Null seh'
Ist der ggT