Euklidischer Algorithmus (Mathe-Song)
HTML-код
- Опубликовано: 23 ноя 2023
- 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: www.DorFuchs.de/t-shirts/
Facebook: / dorfuchs
Instagram: / dor.fuchs
Twitter: / dorfuchs
RUclips: / dorfuchs
Website: www.DorFuchs.de/
Playlist mit allen Mathe-Songs: bit.ly/MatheSongs
Spotify: bit.ly/DorFuchsSpotify
iTunes: 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 RUclips-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 www.eduflat.de/. Dieses Video ist für schulische Unterrichtszwecke geeignet und bestimmt und daher ein geschütztes Werk gemäß §60a und §60b UrhG.
Ein neuer Mathesong 🎉
🥳
Hier noch ein paar Func Facts, die es nicht in den Liedtext geschafft haben:
• Die meisten Schritte benötigt man mit zwei aufeinanderfolgenden Fibonacci-Zahlen (z. B. 21 und 13). Dann wird nämlich in jedem Schritt nur "-1•" gerechnet und man kommt nicht ganz so schnell zu kleineren Zahlen
• Da die Fibonacci-Zahlen exponentiell wachsen (und zwar mit Basis goldener Schnitt), hat der Euklidische Algorithmus eine logarithmische Laufzeit.
• Der euklidische Algorithmus ist der älteste bekannte nicht-triviale Algorithmus. 300 v. Chr. hat in Euklid in "Die Elemente" beschrieben. Euklids Elemente war über viele Jahrhunderte DAS Mathe-Lehrbuch schlechthin. Wahrscheinlich hat Euklid da eher bekanntes Wissen gesammelt als den Algorithmus selbst entdeckt.
• Da man nur Division mit Rest braucht, um den Algorithmus zu machen, funktioniert das mit allen mathematischen Strukturen, wo man eine vernünftige Division mit Rest definieren kann. Diese nennt man euklidische Ringe. Man könnte das zum Beispiel mit Polynomen machen und macht dann Polynomdivision und nimmt dort den Rest.
Finde ich echt gut, dass du subtile Kritik an der Primfaktorzerlegung übst, viele Lehrpersonen hinterfragen diese unsägliche Methode gar nie.
Kannst du mal ein Song über proportionale Zuordnungen bzw. Antipropotionale Zuordnungen machen?
Kleine Ergänzung vielleicht noch: die Koeffizienten, die man beim Erweiterten Euklidischen Algorithmus mitberechnet, heißen Bezout-Koeffizienten :)
Noch ein halber zusätzlicher Fakt:
Den erweiterten euklidische Algorithmus kann man bei der Schlüsselerzeugung in der Kryptographie benutzen. Dafür nimmt man zwei Zahlen, von denen man schon weiß, dass der ggT=1 ist, weil man nur an der Linearkombination interessiert ist.
Wir brauchen diese Mathe-Songs bei YT-Shorts. Einfach den Refrain reinhauen und das wird so unfassbar erfolgreich.
Leider kann ich keine Bilder hier rein schicken, aber dieses Jahr warst du mein Top Artist auf Spotify. Danke für alle Mathe songs.
wow, verrückt!
Den Algorithmus hatte ich schon verstanden, die Begründung leuchtet mir jetzt erst ein. Danke, dass du es besser erklärst als mein Prof in 1,5 Stunden Vorlesung. xD
Love your songs! I don't yet know German, but I like how it sounds, and knowing these math topics allows me to understand some of the words.
Watched the whole playlist recently. Please keep going with them!
Mathe + Musik = DorFuchs
edit: musik, not music lol
Very nice to read from you here in the comments!
Of course you have found the English Song as well, what's your opinion?
Same here lol
Wie wärs mit nem Mathesong über Exponentialfunktionen/gleichungen
unpopular opinion: einer seiner besten songs
Ich freue mich jedes Mal, wenn mir RUclips eine Benachrichtigung schickt, dass du einen neuen Song veröffentlicht hast (eigentlich freue ich mich über alle deine Videos!)
Sitze gerade in meiner Physikvorlesung, aber ich weiß jetzt schon, dass ich mich auf ein Meisterwerk freuen kann!
Danke dir. :)
Same. Sitze auch gerade in einer Vorlesung und freue mich darauf, danach diesen Song zu hören
@@Meister__Wu Welche Vorlesung ist es bei dir?
Fis-Dur! Wie schön!
In der Beschreibung hab ich es mal als Gb bezeichnet. 😋
Sehr nice!
Tatsächlich auch mal ein Song, dessen Inhalt auch im Grundschullehramt bei uns vermittelt wird
"Akward Silence" auch ich, der gerade Physik studiert und für Ringe und Gruppen gcd braucht und keine Ahnung mehr darüber hatte. :)
@@connoravanzini5324Echt? Darf ich wissen, wofür Sie Ringe und Gruppen brauchen, wenn Sie Physik studieren? Für Physik kenne ich nur Quaternionen, und ich habe das Gefühl, dass man maximal nur ein bisschen abstrakte Algebra für Physik braucht. Ich studiere Mathe und einige Dozenten sagen dass abstrakte Algebra überall benutzt ist, aber das glaube ich nicht
(Entschuldigung für mein schlechtes Deutsch, das ist nicht meine Muttersprache)
Schön, dass du auch den erweiterten euklidischen Algorithmus erklärst. Passt zu den Themen in der Uni gerade :)
Kleine Korrektur: Bei 0:25, steht in der Klammer hinter ggT auf einmal 70 statt 140.
Sonst echt wieder sehr nice geworden
Höre gerade Zahlentheorie an der Uni und sehe mich sowas von sicher mit deinem Song in der Klausur 😂
Ich habe gerade Kryptologie und der Song ist eine gute Wiederholung xD
Ich grüße alle aus Tübingen die den Song in Mathe 3 angehört haben
JUHU ENDLICH EIN NEUER MATHE SONG
Hammer das du noch die Mathe-songs machts. Hast mein jüngeres ich echt mit den Brüchen und linearen Funktionen geholfen :)
Wow, die Mathe-Songs sind extrem Genial. Ich liebe deinen Kanal!!!
Wieder ein absoluter Ohrwurm - So lernt es sich doch gleich viel besser! ♡~♡
Einfach cool, dass ein neues Lied da ist. ❤❤
Algebra1 ist bei mir schon eine Zeit lang her, aber ich weiß, dass meine Algorithmen, die ich verwenden musste vom Aufschreiben her viel ätzender waren.
So wie du es aufgeschrieben hast, war es echt geschmeidig.
Alles, was ich zum euklidischen Algorithmus bei der Suche gesehen hatte, war auch mit deutlich mehr Schreibaufwand verbunden, aber da versuche ich immer, eine Variante mit möglichst wenig Schreibaufwand zu gestalten - so wird es halt auch viel übersichtlicher.
Freut mich total du kannst so vielen was beibringen.
@@DorFuchsAußerdem muss die Schreibmethode ja auch in einen Refrain passen, das alleine spricht ja schon dafür, eine Methode mit wenig Schreibaufwand wie möglich zu finden...
Wie in Alten Zeiten, verdammt geil!
Hallo DorFuchs, wie cool, dass du über den Euklidischen Algorithmus einen Song schriebst! Auf RUclips ist der EA viel zu wenig vertreten, darum habe ich gerade diese Woche ein Video dazu hochgeladen. Zum Beweis habe ich auch ein Video gemacht, werde ich am Wochenende dann hochladen, allerdings bin ich den Beweis etwas anders angegangen, deine Variante zu sehen war allerdings auch spannend. Und cool, dass du auch den EEA einbaust, den habe ich nicht. Aber wie immer, Top-Song! :)
Wieder ein sehr guter Song hat ein platz in meiner Spotify Playlist definitiv verdient.
Ich höre nur seit 10 Minuten dieses Lied und ich habe schon eine Aufgabe der Zahlentheorie gemacht, mit der ich viele Tage verbracht habe. Deine Songs sind echt Magie :D
(sorry if I made mistakes but I'm still learning)
Was für Fehler denn? Dein Deutsch ist super!
@@maxfrobin8930 Danke :)
lch höre nun am anfang, sonst merkt man aber echt nicht das du kein muttersprachler bist!
Wunderbar, mal sehen, was meine Schüler dazu sagen😊
Wie immer ein absoluter Banger!
Gestern habe ich noch darüber nachgedacht, und heute darf ich mich über einen dazugehörigen Song mit Herleitung freuen, was gibts schöneres! :)
Das war so wundervoll! Großartig
Wie geil! Endlich mal wieder ein Song. Und was für ein Brecher der halt ist!! 🎉
Morgen gibt's zum Frühstück ggT.
Du kannst mir immer mit jedem Song etwas neues beibringen!
Vielen Dank! ^w^
Mir auch
Ich habe gestern noch daran gedacht, dass langsam mal wieder ein neuer Mathe-Song kommen könnte😅
Echt gut! Unironisch in meiner Musik-Playlist
Wohooo, ein Mathesong!
Ich finde die echt inspirierend, weil ich auch versuche Songs zu schreiben und mich auch für Mathe interessiere. (1. Semester Physik)
Du hast viel mehr Reichweite verdient😌😁
Neuer Mathe-Song, genau das, was ich jetzt brauche!
Geiler Song, ich merke wie die Qualität immer weiter zunimmt
Mich fasziniert einfach, wie hier nebenbei quasi die gesamte Popmusik einmal durch den Kakao gezogen wird ... während Refrains normalerweise so oft wiederholt werden, bis die drei Minuten voll sind, hat hier alles Hand und Fuß. Genial!
Sehr schön, mal wieder ein Song 👍
Nice den zeig ich meinen Üblingen 😂
Edit: Es ist ein richtiger Banger geworden🥰
Gut, wie gewohnt
Absoluter Banger
What en Banger!
Du hast es genau während meiner Physikklausur hochgeladen! :D
einfach genial !! :D
einfach nur geil ❤
Finde es faszinierend wie viel man sich durch Musik merken kann. (ZB deine Songs oder der Periodensystem Song von asap science)
Wieder mal ein Banger
Sehr gutes Lied!
Einfach stark!!!!
Wie es in der Bridge auf einmal richtig deep wird❤😂
Der Song kommt wie gerufen, perfekter Zeitpunkt
Mit dem Song schaffen wirs durch die Klausur 🗣🗣🔥💥
hätte den EEA gestern für meine Klausur in Informatik für den RSA Algorithmus gebraucht, mal wieder ein super Upload um ein paar Stunden zu spät xD
ECC > RSA
Den erweiterten habe ich nie ganz verstanden wieso weshalb muss ich was machen aber mit dieser Tabelle wie du es machst ist das verständlich und fast schon trivial warum das funktioniert.
Jetzt schon Ohrwurm
Endlich wieder ein Mathe-Song!
Der Refrain geht hart 🤟
waas ein neuer Mathesong. Geiler Typ
Wow, richtig krass 😧 muss extrem viel Arbeit sein
jetzt stellt euch das mal mit richtigen dopplungsspuren, backups, adlips, hall und delay vor. Banger und locker für Spotify. Schreib mir mal ich mach dir das umsonst :D
Sehr gut 🎶 🎉
Ein neuer Mathesong😍😍😍
Super Song, was wir noch nicht
hatten ist die Matrixrechnung
Cooler song
Schön
Dorfuchs for ESC 🎉
Wir haben den Euklidischen Algorithmus auch in Z+aZ behandelt, aber ich hab bis heute nicht gerafft wie das gehen soll. Hab die Klausur zum Glück auch so geschafft :D.
Mein Problem ist nur dass du dich ja gar nicht bei 0 raus kommst irgendwann. Also für Z+iZ und den Zahlen 12+i10 und 4-i5, wenn ich dort rum subtrahiere bleibt das ja immer ungleich 0. Außerdem ist mir nicht so ganz klar wie das „kleiner“ werden soll, ich muss da ja erstmal irgendeine Norm sinnvoll definieren.
Hm, gibt da so eine tolle Neuigkeit,
heißt B U C H. Nimmst Du 1 zur elementaren Zahlentheorie und guckst bei Euklidischen Ringen nach. Dort steht dann auch, dass also Norm von a+bi eben a^2+b^2
gewählt wird. Das die Division mit
Rest, wird hoffentlich im Buch bewiesen, gilt auch nicht für alle
Z+ alpha Z, sonst wäre Fermats Großer Satz schon vor 200 Jahren
bewiesen gewesen.
Aber wenn Du ein Lied dazu brauchst, hast Du wohl Pech.
Legende
Das geb ich mir jetzt beim schlafen
Nächste mittwoch VO Prüfung in Zahlentheorie. Vieleicht hilft mir das
Stiil a legend
Super Song freut mich total , bin gerade bei der Matrix könnte mir bestimmt helfen für die Arbeit nächstes Mal
I am a new explorer of your channel！
Very interesting🎉
cooler Mathe-Song! Als nächstes bitte beweisen, dass der goldene Schnitt irrational ist!
Kannst du mal einen Song darüber machen wie man einen Kreisausschnitt berechnet ps:Deine Videos sind die besten
Wir brauchen eigentlich mal ein Mathe-Musical!
Gerade wenn es in der Uni Thema ist. 10/10 timing
Diskrete Strukturen ballert
köstlich
Super song! Kannst du bitte ein Lied zu den Taylorpolynomen machen? Es ist super dringend und wichtig! Dor Fuchs bitte hilf uns
🔥🔥🔥
Geil😂❤
Haben wir damals in der fünften Klasse gemacht. War nach 'nem halben Jahr der einzige, der sich nich daran Erinnern konnte😅.
immer diese Mathe-Brains hier in den Kommentaren... haha
yey!
Wir haben witzigerweise diesen Montag erst eine Informatikklausur geschrieben, wo wir das anwenden mussten.
Wie man auf die Koeffizienten in der tabelle beim erweiterten ggt algorithmisch kommt ist mir nicht klar 😂
Der algorithmus wurde heute in einer vorlseung eingeführt was ein timing
Als ob wir haben das gerade in der schule😂
Nice! Ich kann mich nicht daran erinnern, ob ich das selbst in der Schule hatte... 😅
Wir hatten damals nur die Primfaktorzerlegung zur Bestimmung des ggT.
Nächstes Lied bitte auf deutsch!
LG
Ich hatte ja auf einen erweiterten Refrain für den rechten Teil gehofft 😅
4:39 Wenn man die kleine Zahl von der großen abziehen soll, müsste es rechts doch eigentlich 3-(-2) heißen? Oder ist die Regel eigentlich, dass man die unterste Zahl von der oberen abziehen soll? Klingt natürlich nicht so schön
Kannst du Mal einen Song, über die Lamerbt Funktion w(X) machen, sprich der Umkehrfunktion zu x * e^x ?
Wir haben sie im Unterricht geguckt!!! 😅
Hallo DorFuchs. Aber hast du da bei 0:31 nicht einen Fehler? Sollte das nicht ggT(616, 140)=2×2×7=28 heißen?
Oh nein. Stimmt. Da steht fälschlicherweise 70.
Erst hatte ich 70 als Beispiel, aber dann dachte ich, ein mehrfacher Primfaktor im ggT macht hier deutlicher, was passiert, aber hab es offensichtlich nicht überall geändert...
Ist schon echt mies, wenn man wochenlang an so etwas arbeitet, es dutzende Male durchschaut und sowas einfach nicht bemerkt...
@@DorFuchs Passiert :). Sonst Klasse - wie immer.!
What ich saß gerade an Zahlentheorie
Moin bist du hörn amon
wann konzert?
Beim "Erweiterten e. A." musste es dann schnell gehen? 😉
Ein paar Pfeile und die Multiplikation (nicht nur das Ergebnis) hätten doch noch hingepasst.
Ich muss bei euglied sofort an hobbylos denken. L-l
Meiner Meinung NPC!