Der euklidische Algorithmus ist der älteste bekannte nicht-triviale Algorithmus. Mit ihm findet man den größten gemeinsamen Teiler zweier Zahlen. In diesem Song wird gezeigt, wie der Algorithmus funktioniert, hergeleitet, warum tatsächlich immer der ggT herauskommt und auch noch die erweiterte Version gezeigt.

Danke an LukasLLS, der mich auf   / dorfuchs   unterstützt.

Patreon:   / dorfuchs  
T-Shirts: http://www.DorFuchs.de/t-shirts/
Facebook:   / dorfuchs  
Instagram:   / dor.fuchs  
Twitter:   / dorfuchs  
YouTube:    / dorfuchs  
Website: http://www.DorFuchs.de/

Playlist mit allen Mathe-Songs: http://bit.ly/MatheSongs
Spotify: http://bit.ly/DorFuchsSpotify
iTunes: http://bit.ly/DorFuchsiTunes


Akkorde:
|: Gb Abm Bbm Abm :|
Ende des Raps: Gb Abm Bbm B Db
Ende des Refrains: Ebm Db B
Bridge: Abm Gb Db (3x) B Bm


Songtext:

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 lieber Euklids Algorithmus versuchen,
weil sich damit der ggT durch bisschen Division mit Rest
in nur wenigen Schritten berechnen lässt.


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.
(3x)
Man zieht die kleine Zahl so oft von der großen ab,
bis man hier am Ende keinen Rest mehr hat
und die letzte Zahl, die ich vor der Null seh’
ist der ggT.


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’ wir wieder sehen,
dass der Teiler dabei bleibt, 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ößeren gibt es nicht. Ich habe den g - gT!


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.
(3x)
Man zieht die kleine Zahl so oft von der großen ab,
bis man hier am Ende keinen Rest mehr hat
und die letzte Zahl, die ich vor der Null seh’
ist der ggT.

Und es gibt auch noch ne erweiterte Version.
Mit a, 1, 0 und b, 0, 1 hab ich schon
den Anfang und rechne ich jetzt zeilenweise, seh
ich am Ende hier aus a und b
eine Linearkombination zum ggT.


------
Dieses Video wurde für die private, nicht-kommerzielle Nutzung produziert und veröffentlicht und ist in diesem Rahmen ohne Rücksprache oder schriftlicher Genehmigung für private Zwecke kostenfrei zu verwenden. Bitte beachten Sie jedoch, dass das Video weder inhaltlich noch grafisch verändert werden darf. Geben Sie bei einer Verwendung bitte stets den YouTube-Kanal DorFuchs als Quelle an. Für die kommerzielle Nutzung sowie die Nutzung zu zustimmungspflichtigen Nutzungshandlungen zu Bildungszwecken, wie öffentliche Filmvorführungen, öffentliche Zugänglichmachungen über Bildungsserver, Lernplattformen oder Bildungsclouds, usw. ist eine Lizenzierung erforderlich. Lizenzen erhalten Sie bei unserem Vertriebspartner https://www.eduflat.de/. Dieses Video ist für schulische Unterrichtszwecke geeignet und bestimmt und daher ein geschütztes Werk gemäß §60a und §60b UrhG.