Euklidischer Algorithmus (Mathe-Song)
DorFuchs
https://www.youtube.com/watch?v=W8oIvMTr7PM

Transkript (automatisch erstellt)

0:01 [Musik] vielleicht willst oder sollst du mal den GGT berechnen also den größten
0:18 gemeinsamen Teiler aber mal echt wenn du erstmal deine Zahlen in ihre Primfaktoren zerlegst dann siehst Du schnell den GGT aber wenn du mal
0:26 überlegst wie viel Aufwand es bedeutet Primfaktoren zu suchen solltest Du vielleicht lieber euklidsalgorithmus versuchen weil sich
0:34 damit der GGT durch bisschen Division mit Rest in nur wenigen Schritten berechnen
0:42 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
0:54 den letzten beiden macht man das jetzt noch mal man zieht die kleine Zahl so oft von der großen ab wie sie reinpasst und im Ergebnis hat man den Rest und den
1:06 nimmt man als die nächste Zahl und mit den letzten beiden macht man das jetzt noch mal man zieht die kleine Zahl so oft von der großen ab wie sie rein passt
1:16 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 noch mal man zieht die kleine Zahl so
1:26 oft von der großen ab bis man hier am Ende kein Rest mehr hat und die letzte Zahl die ich vor der Null sehe ist der GGT okay durch rechnen mit dem Rest bei
1:41 Division auch modulo genannt kannst du das am Rechner schon mit nur wenig Aufwand super einfach implementieren aber warum wird der Algorithmus immer
1:52 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
2:01 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
2:12 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
2:22 ausgehen in jedem vielffachen und in der Summe können wir Wieders sehen dass der Teiler dabei bleibt doch die Summe a und da der Teiler auch im B steckt wird also
2:33 klar die gemeinsamen Teiler sind also beide Male gleich wodurch ich garantiert den gleichen GGT erreich und wenn ich n so groß wähle wie auf B in a reinpasst
2:44 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
2:54 sehe doch dann ist B selbst gemeinsamer Teiler und ich verstehe einen größeren gibt es nicht ich ich hab den
3:03 GGT 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
3:15 letzten beiden macht man das jetzt noch mal 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
3:27 man als die nächste Zahl und mit den letzt beiden macht man das jetzt noch mal man zieht die kleine Zahl so oft von der großen ab wie sie reinpasst und im
3:37 Ergebnis hat man den Rest und den nimmt man als die nächste Zahl und mit den letzten beiden macht man das jetzt noch mal man zieht die kleine Zahl so oft von
3:47 der großen ab bis man hier am Ende kein Rest mehr hat und die letzte Zahl die ich vor der Null sehe ist der GGT
4:00 und es gibt auch noch eine erweiterte Version mit A10 und B01 habe ich schon den Anfang
4:15 und rechne ich jetzt zeilenweise sehe ich am Ende hier aus A und B eine linear komombination zum
4:32 GGT 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
4:44 letzten beiden macht man das jetzt noch mal 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
4:56 man als die nächste Zahl und mit den letzten beiden macht man das jetzt noch mal man zieht die kleine Zahl so oft von der großen ab wie sie reinpasst und im
5:06 Ergebnis hat man den Rest und den nimmt man als die nächste Zahl und mit den letzten beiden macht man das jetzt noch mal man zieht die kleine Zahl so oft von
5:17 der großen ab bis man hier am Ende kein Rest mehr hat und die letzte Zahl die ich vor der Null se ist der GGT