Du hast an der Uni das Thema den ggT zu finden? Und machst das dann mit dem Euklidschen Algorythmus? Das macht echt keinen Sinn lol - Ich glaube nicht, dass Du zur Uni gehst...
@@jeffreylebowski4927 Das stimmt natürlich auch , im Allgemeinen wird eh in der Uni grade in Mathe quasi nochmal von 0 angefangen und geht in einem rasanten Tempo schnell weiter :)
@@timdorner8580 Kann sein, ich denke so soll es eigentlich auch sein, leider war meine Erfahrung anders, bei mir ging es im 1. Semester gleich mit partieller Integration und Beweisen durch Vollständiger Induktion los... :s - vielleicht habe ich deshalb aufgehört zu studieren lol.
Ich hab das mal in der Schule in Informatik programmiert, also diesen Algorithmus in eine Funktion gegossen. Damals, als der Informatikunterricht noch wild und neu war. Ende der 1980er Jahre. Danke für diesen nostalgischen Ausflug! 😍
Wie immer mit positiver Energie erklärt…. War im Informatik Unterricht ein schönes Beispiel um zu lernen einen erstes kleines Programm zu schreiben… Danke für die Auffrischung
Ich fände es schön, wenn Du erklären würdest WARUM das funktioniert, damit man nicht nur stumpf irgendwelche alogorythmen auswendig lernt und anwendet, sondern VERSTEHT was da eigentlich passiert - das ist nämlich eigentlich das was interessant ist.
Habe mal versucht es zu erklären: Der ggT von A und B (A>B) muss ja sowohl A und B als auch den Rest von A/B sauber teilen können, denn A ist ja ein Vielfaches von B + Rest(A/B). A, B und Rest(A/B) haben also den selben ggT. Nennen wir "Rest(A/B)" ab jetzt einfach "C". Man kann jetzt also den ggT von B und C suchen - also von deutlich kleineren Zahlen. Und dieses Prinzip wiederholt sich .- wir gucken jetzt noch, ob C ohne Rest in B passt - denn dann wäre C der ggT von A und B. - er würde ohne Rest in B passen und müsste dann nur noch einmal zu n*B dazu addiert werden, um zu A zu kommen... (C ist ja der Rest(A/B) ). Wenn er nicht ohne Rest in B passt bekommen wir wieder einen Rest(B/C). Wir suchen also den ggT von B und C und bekommen einen Rest(B/C)... auch hier gilt wieder, dass der ggT von B und C den Rest(B/C) sauber teilen können muss, denn B = n*C + Rest(B/C). Wenn der Rest(B/C) sauber in C passt, dann ist das der ggT von B und C und damit auch der ggT von A und B. Falls er nicht ohne Rest in C passt dann geht das Spiel weiter und wir nennen Rest(B/C) "D" und suchen den ggT von D und Rest(C/D) also "E" und das so lange, bis einer der Reste sauber in die kleinere Zahl reinpasst..., denn dann ist das der ggT dieser und der nächst größeren Zahl und aller anderen Zahlen davor. Es ist in so einem UA-cam Kommentar nicht so leicht verständlich zu machen wie in einem UA-cam Video, deswegen ist es Schade, dass sie das nicht erklärt im Video, mit anschaulichen Zeichnungen etc.
@@porkonfork2023 Du meinst, weil es zu kompliziert ist es zu erklären? Ist es eigentlich gar nicht, man muss nur verstehen, dass der ggT von A und B auch den Rest(A/B) sauber teilen können muss, also dass A und B und Rest(A/B) den selben ggT haben. Dann kann man Rest(A/B) "C" nennen und den ggT von B und C suchen - das sind nämlich kleinere Zahlen... und so geht das immer weiter... bis einer der Reste selber der ggT ist und die nächst größere Zahl sauber teilt. Rest(A/B) muss sauber durch den ggT von A und B teilbar sein, weil A = n*B + Rest(A/B) n*B ist sauber durch den ggT teilbar, weil B sauber durch den ggT teilbar ist und n*B nur ein Vielfaches von B ist, also muss der Rest(A/B), der zu n*B dazu addiert wird um zu A zu kommen,auch sauber durch den ggT teilbar sein, weil A sauber durch den ggT teilbar ist. Ist das verständlich? Ich bin irgendwie nicht gut im erklären sorry.
Seien a und b in N, a >= b. Gesucht ist ggT(a; b). Ex. c in N und r in N_0, so dass a : b = c Rest r bzw. in Bruchdarstellung a/b = c + r/b | * b a = bc + r gilt. 1. Fall: r = 0 a = bc => b ist natürlicher Teiler von a => ggT(a; b) = b 2. Fall: r > 0 a = bc + r | : ggT(a; b) [Division erlaubt, da ein ggT immer >= 1 ist] a/ggT(a; b) = bc/ggT(a; b) + r/ggT(a; b) Da per Definition a/ggT(a; b) in N und bc/ggT(a; b) in N gilt, muss r/ggT(a; b) in N gelten, denn N + Q\N ⊆ Q\N. => ggT(a; b) ist natürlicher Teiler von r. Da r der Rest aus einer Division durch b ist, gilt r < b und aufgrund der Voraussetzung insgesamt r < b < a. => ggT(a; b) = ggT(a; b; r) = ggT(b; r) Das Spiel jetzt so lange wiederholen, bis der 1. Fall eintritt - Iteration: a_(n+1) := b_n und b_(n+1) := r_n Wegen r_n < b_n < a_n für alle n sind die a- und die b-Folge streng monoton fallend und daher zwingend endlich, weshalb der Algorithmus auf jeden Fall zum Ziel führt.
Du hast nicht umsonst so viele Abonenten!! Ich selbst spiele einfach nur gern mit Zahlen oä, und ich werde bald 59 Jahre (fühlt sich nicht so an ) 10the Klasse DDR Abschluß. Ich gebe noch manchmal Nachhilfe Für Kinder meiner Freunde oder Bekannten von Klasse 2 bis 10. immer von Erfolg gekrönt. Und was du mir da oft in ein paar Minuten neues innteressantes mitgibst..herrlich. Wäre ich nicht zufällig auf deinen Kanal gestoßen,wäre auch Deine ( Euere ) Musik an mir vorbeigegangen. Diese beiden,tja, ?? sichtbaren Präsentationen ?? ergänzen sich so schön.... (kann ich voll daneben liegen, erweckt aber den Eindruck) Weiter so...mit allem.
Cooler Video, wir hatten vor paar Monaten den ggT von 2 Zahlen und letzte Woche den ggT von 2 Polynomen, nur in der Uni haben wir das mit einer Tabelle gemacht, weil man da nochden ggT als Summanden von der Multiplikation darstellen kann
Danke. Den Algorithmus kannte ich noch gar nicht. Für die Verwendung in einem Computerprogramm ist der prima. (Jetzt müsste ich nur noch verstehen, WARUM der funktioniert.)
Da uns der Quotient nicht interessiert, sondern nur der Rest, kann man auch (wie einmal im Video kurz angedeutet), die kleinere Zahl so oft von der grösseren abziehen, bis ein Rest bleibt. Sobald man bei der Null landet, hat man mit dem aktuellen Subtrahenden den ggT gefunden.
Kommt natuerlich auf das Zahlenpaar an. Wenn sie sehr weit auseinander liegen, kann eine schriftliche Division schneller sein als mehrere Subtraktionen. Mit Taschenrechner ist eh die Division schneller.
Naja, im Video war's eher so, dass man zum Teil sehen konnte, dass der Quotient der beiden großen Zahlen 1 oder 2 sein musste. Was dann eher schon mal helfen kann, sind Teilbarkeitsregeln, wenn links noch eine sehr große und rechts eine sehr kleine Zahl steht. Bei den Divisoren 2 und 5 braucht man dann z. B. nur auf die Endziffer und bei 3 und 9 nur auf die Quersumme zu schauen. Wenn man die Teilbarkeit feststellt, braucht man nicht mehr weiter zu machen, weil man dann auch so weiß, dass der nächste Rest 0 sein wird und der aktuelle Rest somit bereits der gesuchte ggT ist.
Ich habe mal überlegt warum das funktioniert: Der ggT von A und B (A>B) muss ja sowohl A und B als auch den Rest von A/B sauber teilen können, denn A ist ja gleich n*B + Rest(A/B). Der ggT von A und B ist also der selbe wie der von B und Rest(A/B). Nennen wir "Rest(A/B)" ab jetzt einfach "C". Man kann jetzt also den ggT von B und C suchen - also von deutlich kleineren Zahlen. Und dieses Prinzip wiederholt sich .- wir gucken jetzt noch, ob C ohne Rest in B passt - denn dann wäre C der ggT von A und B. - er würde ohne Rest in B passen und müsste dann nur noch einmal zu n*B dazu addiert werden, um zu A zu kommen... (C ist ja der Rest(A/B) ). Wenn er nicht ohne Rest in B passt bekommen wir wieder einen Rest(B/C). Wir suchen also den ggT von B und C und bekommen einen Rest(B/C)... auch hier gilt wieder, dass der ggT von B und C den Rest(B/C) sauber teilen können muss, denn B = n*C + Rest(B/C). Wenn der Rest(B/C) sauber in C passt, dann ist das der ggT von B und C und damit auch der ggT von A und B. Falls er nicht ohne Rest in C passt dann geht das Spiel weiter und wir nennen Rest(B/C) "D" und suchen den ggT von C und D und das so lange, bis einer der Reste sauber in die kleinere Zahl reinpasst..., denn dann ist das der ggT dieser und der nächst größeren Zahl und aller anderen Zahlen davor. Es ist in so einem UA-cam Kommentar nicht so leicht verständlich zu machen wie in einem UA-cam Video, deswegen ist es Schade, dass sie das nicht erklärt im Video, mit anschaulichen Zeichnungen etc.
@@jeffreylebowski4927 Danke für die super Antwort, Jeffrey. Perfekt dargestellt, ich habe es jetzt auch kapiert. Ich glaube die Beweisführung hat Susanne extra nicht reingenommen, ist schon ziemlich schwierig der ganze Stoff und für die Nichtmathematiker Klientel vielleicht etwas zu hoch.
Wenn man keinen Taschenrechner zur Verfügung hat und einem Divisionen zu kompliziert sind, kann man auch Subtraktionen verwenden, braucht dann aber mehr Schritte. Man kann nämlich in jedem Schritt die kleinere von der größeren Zahl abziehen und dann die größere Zahl durch diese Differenz ersetzen. Im ersten Beispiel: ggt(356, 238) = ggt(238, 356-238) = ggt(238, 118) = ggt(118, 238-118) = ggt(118, 120) = ggt(118, 120-118) = ggt(118, 2) = ggt(2, 118-2) = ggt(2, 116) = ... PK, jetzt kommen die vielen Schritte, da wäre es natürlich gut, einfach zu dividieren: = ggt(2, 118:2) = ggt(2, 2) = 2.
... oder noch besser, auf den Trichter zu kommen, dass 2 (eine Primzahl ist und als solche) nur die Teiler 1 und 2 hat. Dementsprechend kann auch der ggT(2; n) für jede beliebige Zahl n nur 1 oder 2 sein. Und logischerweise ist er 1, wenn n ungerade ist, und 2, wenn n gerade ist.
@@teejay7578 Das stimmt, aber mir ist entfallen, wie man diese Rekursion bei der Subtraktionsmethode _allgemein_ schneller abbrechen kann. Also, wenn die kleinere Zahl nicht so klein wie 2 ist. Irgendwie gab es da glaub ich eine Regel, aber sie fällt mir grad nicht ein.
Hab die beiden Varianten grad auf Wikipedia nachgeschlagen: die klassische mit der Subtraktion läßt sich wirklich nicht schneller abbrechen, denn sie bricht erst ab, wenn eine der beiden Zahlen 0 wird. Also müßte man im vorliegenden Beispiel wirklich 2 so oft von der geraden Zahl 118 subtrahieren, bis man bei 0 ankommt. Die moderne Variante (Division mit Rest) kürzt das dann natürlich zu einem Schritt ab: 118 mod 2 = 0.
Oh, das haben wir im Studium in Algebra (1. Semester) mal gemacht. Ich meine, wir hatten das sogar begründet, aber das ist so lange her, ich hatte es tatsächlich vergessen. 😂 Hab es halt nie wieder gebraucht … 🤪
@Gehteuch Nichtsan Ja, die Funktion ggT() ruft in der letzten Zeile (return ggT(b, a % b)) sich selbst wieder auf, und zwar so lange, bis der Rest, der mittels Modulo-Operator bestimmt wurde (a % b), Null ist.
Ich schreibe das jedes mal so: def ggT(a, b): while b != 0: a, b = b, a % b return a Persönlich finde ich die Variante besser, weil Rekursion mehr Speicher braucht und langsamer ist. Der Algorithmus an sich geht aber so schnell, dass es wahrscheinlich keinen Unterschied macht, und ich höre oft, dass man meine Version schlecht lesen kann.
meine güte du hast eine so wunderschöne schrift. und eine so wunderschöne stimme. und du bist auch noch so wunderschön🫣ich glaube du bist das beste was einem inf-ro-ma(nn)-tiker passieren könnte😇heschtekheiratemirdoch PAUAWOMAN _-bilbe wei ud tsib-_ fil libe su dir
So verstehe ich das auch aber ich würde eine Erklärung zu der Definition vermissen. Da hab ich aktuell Probleme mit dem formalen beschreiben und wie man anhand so ein Text es versteht. Was wäre eventuell hilfreich noch. Satz: Euklidischer Algorithmus Seien a, b ∈ ℤ mit a ≠ 0. Dann lässt sich der größte gemeinsame Teiler von a und b wie folgt eindeutig bestimmen: Wir dividieren b durch a mit Rest und erhalten b = q1a + r1 mit 0 ≤ r1 ≤ |a|. Falls r1 = 0 ist, so ist |a| = ggT(a,0) und mit dem vorangegangenen Lemma gilt ggT(a,b) = ggT(a,r1) = ggT(a,0) = |a|. Falls r1 ≠ 0 ist, dividieren wir a durch r1 mit Rest und erhalten a = q2r1+r2 mit 0≤r2 r1 > r2 >... > rn > rn+1 = 0. Da es nur endlich viele ganze Zahlen zwischen |a| und 0 gibt, ist sichergestellt, dass das Verfahren irgendwann terminiert. Auf diese Weise erhalten wir eine Reihe von Gleichungen der Form: Bei so was tu ich mich aktuell noch schwer
Hallo MathemaTrick, weißt du eigentlich, weshalb andere Mathe YoutTuber, speziell spiele ich auf Daniel Jung und Lehrerschmidt an, den Euklidischen Algorithmus nicht präsentieren? Er ist ja viel effizienter als die Primfaktorzerlegung ...
Mit Lambda Ausdrücken kann man den Algorithmus rekursiv in eine einzige Programmzeile schreiben: (C#) ggT(int a, int b) => (b == 0) ? a : ggT(b, a % b);
@Gehteuch Nichtsan Auch wenn Du mir scheinbar ignorant erscheinst, sowas wird in der Universität (Informatik und Mathematik) gelehrt... Wenn Du etwas nicht verstehst, dann frag normal nach. Warum so feindseliger Antwort?
Seien a_{0} und a_{1} zwei natürliche Zahlen mit a_{0}>a_{1}. Betrachte a_{0}=q_{1}*a_{1}+a_{2} a_{1}=q_{2}*a_{2}+a_{3} . . . a_{n-1}=q_{n}*a_{n}+a_{n+1} a_{n}=q_{n+1}*a_{n+1}+0 Dann ist a_{n+1} ggT(a_{0},a_{1}) Denn Rest 0 erhält man auf jeden Fall, da es offensichtlich ist, dass a_{1}>a_{2}>a_{3}>...>=0 gilt. Beweis: Teil 1: Sei d ein ganz beliebiger Teiler von a_{0} und a_{1} => d ist ein Teiler von a_{2}=a_{0}-q_{1}*a_{1}, a_{3},...,a_{n+1}. Teil 2: Aus a_{n}=q_{n+1}*a_{n+1} folgt, dass a_{n+1} ein Teiler von a_{n} ist => a_{n+1} ist ein Teiler von a_{n-1},...,a_{1} und a_{0}. Insgesamt folgt, dass a_{n+1} ggT(a_{0},a_{1}) sein muss, denn gebe es einen größeren gemeinsamen Teiler, so wäre es ein Widerspruch zu Teil 1, da a_{n+1} durch diesen Teiler nicht teilbar wäre.
Bitte niemals sagen, dass man bei irgendetwas nicht mehr zu denken brauche - das Hirn eingeschaltet zu lassen ist nie verkehrt und kann trotzdem oft noch Arbeit sparen: 1. Sobald als Rest 1 raus kommt, muss der ggT 1 sein. Grund: Die nächste Division geht dann durch 1 und ist immer restfrei. 2. Sobald als Rest eine Primzahl raus kommt, muss der ggT entweder diese Primzahl (falls die andere Zahl ein Vielfaches davon ist) oder 1 (sonst) sein. Grund: Der Algorithmus funktioniert, weil der Rest denselben ggT wie die beiden Ausgangszahlen hat. Und der ggT einer Primzahl kann nur 1 oder sie selbst sein. Die Hälfte von 118 hätte man somit nicht mehr explizit ausrechnen müssen, sondern direkt entscheiden können, dass der ggT 2 ist, weil die 118 gerade ist - bei einem ungeraden Dividenden wäre er 1 gewesen.
Seien a_{0} und a_{1} zwei natürliche Zahlen mit a_{0}>a_{1}, dann gilt a_{0}=q_{1}*a_{1}+a_{2} a_{1}=q_{2}*a_{2}+a_{3} . . . a_{n-1}=q_{n}*a_{n}+a_{n+1} a_{n}=q_{n+1}*a_{n+1}+0 und a_{n+1} ist ggT(a_{0},a_{1}) Denn Rest 0 erhält man auf jeden Fall, da es offensichtlich ist, dass a_{1}>a_{2}>a_{3}>...>=0 gilt. Beweis: Teil 1: Sei d ein ganz beliebiger Teiler von a_{0} und a_{1} => d ist ein Teiler von a_{2}=a_{0}-q_{1}*a_{1}, a_{3},...,a_{n+1}. Teil 2: Aus a_{n}=q_{n+1}*a_{n+1} folgt, dass a_{n+1} ein Teiler von a_{n} ist => a_{n+1} ist ein Teiler von a_{n-1},...,a_{1} und a_{0}. Insgesamt folgt, dass a_{n+1} ggT(a_{0},a_{1}) sein muss, denn gebe es einen größeren gemeinsamen Teiler, so wäre es ein Widerspruch zu Teil 1, da a_{n+1} durch diesen Teiler nicht teilbar wäre.
*Mein komplettes Equipment*
➤ mathematrick.de/mein-equipment
_____________________________________
Meine Wunschliste: mathematrick.de/wunschzettel
Danke! Hallo Susanne, der euklidische Algorithmus ist wirklich einfacher als die Primfaktozerlegung. Viele liebe Grüße!
Danke, war mir neu! Nett, auf die alten Tage etwas Neues zu lernen👏
Grösster Zufall, dass ich gerade jetzt das Thema im Studium habe und am Freitag meine Klausur ist. :D Danke!
Du hast an der Uni das Thema den ggT zu finden? Und machst das dann mit dem Euklidschen Algorythmus? Das macht echt keinen Sinn lol - Ich glaube nicht, dass Du zur Uni gehst...
@@jeffreylebowski4927 Bei mir an der Uni wird das unter anderem in Einführung in die Zahlentheorie benutzt, bzw ist es eins der Einführungsthemen.
@@timdorner8580 Hmm also wir haben das in der Grundschule gemacht...
@@jeffreylebowski4927 Das stimmt natürlich auch , im Allgemeinen wird eh in der Uni grade in Mathe quasi nochmal von 0 angefangen und geht in einem rasanten Tempo schnell weiter :)
@@timdorner8580 Kann sein, ich denke so soll es eigentlich auch sein, leider war meine Erfahrung anders, bei mir ging es im 1. Semester gleich mit partieller Integration und Beweisen durch Vollständiger Induktion los... :s - vielleicht habe ich deshalb aufgehört zu studieren lol.
Ich hab das mal in der Schule in Informatik programmiert, also diesen Algorithmus in eine Funktion gegossen. Damals, als der Informatikunterricht noch wild und neu war. Ende der 1980er Jahre.
Danke für diesen nostalgischen Ausflug! 😍
Es hat sich nichts verändert, Machen wir auch
Wie immer mit positiver Energie erklärt…. War im Informatik Unterricht ein schönes Beispiel um zu lernen einen erstes kleines Programm zu schreiben… Danke für die Auffrischung
Danke, hat mich gefreut dass es zu dem Thema ein Video von Dir gibt :)
Meiner Oma hat es sehr doll geholfen. Vielen Dank für das erklären.
Ich fände es schön, wenn Du erklären würdest WARUM das funktioniert, damit man nicht nur stumpf irgendwelche alogorythmen auswendig lernt und anwendet, sondern VERSTEHT was da eigentlich passiert - das ist nämlich eigentlich das was interessant ist.
Habe mal versucht es zu erklären:
Der ggT von A und B (A>B) muss ja sowohl A und B als auch den Rest von A/B sauber teilen können, denn A ist ja ein Vielfaches von B + Rest(A/B).
A, B und Rest(A/B) haben also den selben ggT. Nennen wir "Rest(A/B)" ab jetzt einfach "C". Man kann jetzt also den ggT von B und C suchen - also von deutlich kleineren Zahlen.
Und dieses Prinzip wiederholt sich .- wir gucken jetzt noch, ob C ohne Rest in B passt - denn dann wäre C der ggT von A und B. - er würde ohne Rest in B passen und müsste dann nur noch einmal zu n*B dazu addiert werden, um zu A zu kommen... (C ist ja der Rest(A/B) ).
Wenn er nicht ohne Rest in B passt bekommen wir wieder einen Rest(B/C).
Wir suchen also den ggT von B und C und bekommen einen Rest(B/C)... auch hier gilt wieder, dass der ggT von B und C den Rest(B/C) sauber teilen können muss, denn B = n*C + Rest(B/C).
Wenn der Rest(B/C) sauber in C passt, dann ist das der ggT von B und C und damit auch der ggT von A und B.
Falls er nicht ohne Rest in C passt dann geht das Spiel weiter und wir nennen Rest(B/C) "D" und suchen den ggT von D und Rest(C/D) also "E" und das so lange, bis einer der Reste sauber in die kleinere Zahl reinpasst..., denn dann ist das der ggT dieser und der nächst größeren Zahl und aller anderen Zahlen davor.
Es ist in so einem UA-cam Kommentar nicht so leicht verständlich zu machen wie in einem UA-cam Video, deswegen ist es Schade, dass sie das nicht erklärt im Video, mit anschaulichen Zeichnungen etc.
hab bei WIKI nachgesehen. seitdem weiß ich zwar nicht wieso es klappt, aber warum sich susanne erklärungen erspart hat.
@@porkonfork2023 Du meinst, weil es zu kompliziert ist es zu erklären?
Ist es eigentlich gar nicht, man muss nur verstehen, dass der ggT von A und B auch den Rest(A/B) sauber teilen können muss, also dass A und B und Rest(A/B) den selben ggT haben.
Dann kann man Rest(A/B) "C" nennen und den ggT von B und C suchen - das sind nämlich kleinere Zahlen... und so geht das immer weiter... bis einer der Reste selber der ggT ist und die nächst größere Zahl sauber teilt.
Rest(A/B) muss sauber durch den ggT von A und B teilbar sein, weil A = n*B + Rest(A/B)
n*B ist sauber durch den ggT teilbar, weil B sauber durch den ggT teilbar ist und n*B nur ein Vielfaches von B ist, also muss der Rest(A/B), der zu n*B dazu addiert wird um zu A zu kommen,auch sauber durch den ggT teilbar sein, weil A sauber durch den ggT teilbar ist.
Ist das verständlich? Ich bin irgendwie nicht gut im erklären sorry.
Seien a und b in N, a >= b. Gesucht ist ggT(a; b). Ex. c in N und r in N_0, so dass a : b = c Rest r bzw. in Bruchdarstellung a/b = c + r/b | * b a = bc + r gilt.
1. Fall: r = 0
a = bc => b ist natürlicher Teiler von a => ggT(a; b) = b
2. Fall: r > 0
a = bc + r | : ggT(a; b) [Division erlaubt, da ein ggT immer >= 1 ist]
a/ggT(a; b) = bc/ggT(a; b) + r/ggT(a; b)
Da per Definition a/ggT(a; b) in N und bc/ggT(a; b) in N gilt, muss r/ggT(a; b) in N gelten, denn N + Q\N ⊆ Q\N.
=> ggT(a; b) ist natürlicher Teiler von r.
Da r der Rest aus einer Division durch b ist, gilt r < b und aufgrund der Voraussetzung insgesamt r < b < a.
=> ggT(a; b) = ggT(a; b; r) = ggT(b; r)
Das Spiel jetzt so lange wiederholen, bis der 1. Fall eintritt - Iteration: a_(n+1) := b_n und b_(n+1) := r_n
Wegen r_n < b_n < a_n für alle n sind die a- und die b-Folge streng monoton fallend und daher zwingend endlich, weshalb der Algorithmus auf jeden Fall zum Ziel führt.
@@teejay7578 Lol Du schon wieder haha - wenn ich die Energie habe lese ich mir deine Ultrakomplizierte Erklärung durch... ;)
Beeindruckend einfach. Ohne zu denken, also etwas für mich...🤣
Danke!
ein schöner Algorithmus, der sich wunderbar programmieren lässt. Grundkurs Mathematik/Informatik :-)
Du hast nicht umsonst so viele Abonenten!! Ich selbst spiele einfach nur gern mit Zahlen oä, und ich werde bald 59 Jahre (fühlt sich nicht so an ) 10the Klasse DDR Abschluß. Ich gebe noch manchmal Nachhilfe Für Kinder meiner Freunde oder Bekannten von Klasse 2 bis 10. immer von Erfolg gekrönt.
Und was du mir da oft in ein paar Minuten neues innteressantes mitgibst..herrlich. Wäre ich nicht zufällig auf deinen Kanal gestoßen,wäre auch Deine ( Euere ) Musik an mir vorbeigegangen.
Diese beiden,tja, ?? sichtbaren Präsentationen ?? ergänzen sich so schön.... (kann ich voll daneben liegen, erweckt aber den Eindruck)
Weiter so...mit allem.
Klasse Alternative zur Primfaktorzerlegung
finde ich persönlich leichter zu merken, aber wenn häufig die riesigen Zahlen vorkommen sollten, könnte es lohnen
Cooler Video, wir hatten vor paar Monaten den ggT von 2 Zahlen und letzte Woche den ggT von 2 Polynomen, nur in der Uni haben wir das mit einer Tabelle gemacht, weil man da nochden ggT als Summanden von der Multiplikation darstellen kann
Der ist Hammer !!! Ich kannte nur die Primvariante . Toll❤
Nix denken müssen. PERFEKT.😊
Sofort ein Like, wenn ich der Bedarf mich wieder hierher geführt hat, noch ein Video von Susanna zu schauen. ❤
danke für die gute Erklärung
Du bist einfach großartig...
Super Video. Kannst du vielleicht auch ein Video machen, wie man den euklidischen Algorithmus bei komplexen Zahlen benutzt🙃
Danke das hat mir geholfen 😀
Super, das freut mich sehr! 🥰
Danke. Den Algorithmus kannte ich noch gar nicht. Für die Verwendung in einem Computerprogramm ist der prima. (Jetzt müsste ich nur noch verstehen, WARUM der funktioniert.)
that's it
Die Erklärung findest du in diversen anderen Kommentaren.
Liebe Susanne! Der Eiklidische Algorithmus ist wirklich interresant Peter Hablelsberger
ich finde du erklärst sehr gut es wäre sehr nett wenn du mal ein Video über Kreisberechnungen weil ich nix von meinem lehrer verstehe
Da uns der Quotient nicht interessiert, sondern nur der Rest, kann man auch (wie einmal im Video kurz angedeutet), die kleinere Zahl so oft von der grösseren abziehen, bis ein Rest bleibt. Sobald man bei der Null landet, hat man mit dem aktuellen Subtrahenden den ggT gefunden.
Kommt natuerlich auf das Zahlenpaar an. Wenn sie sehr weit auseinander liegen, kann eine schriftliche Division schneller sein als mehrere Subtraktionen. Mit Taschenrechner ist eh die Division schneller.
Naja, im Video war's eher so, dass man zum Teil sehen konnte, dass der Quotient der beiden großen Zahlen 1 oder 2 sein musste.
Was dann eher schon mal helfen kann, sind Teilbarkeitsregeln, wenn links noch eine sehr große und rechts eine sehr kleine Zahl steht.
Bei den Divisoren 2 und 5 braucht man dann z. B. nur auf die Endziffer und bei 3 und 9 nur auf die Quersumme zu schauen. Wenn man die Teilbarkeit feststellt, braucht man nicht mehr weiter zu machen, weil man dann auch so weiß, dass der nächste Rest 0 sein wird und der aktuelle Rest somit bereits der gesuchte ggT ist.
Danke fürs Zeigen.
Gerne! :)
Mathe macht eben Freude! :)
Absolut!
Mathematisch interessant wäre der Beweis, warum das so ist ;-)
Ich habe mal überlegt warum das funktioniert:
Der ggT von A und B (A>B) muss ja sowohl A und B als auch den Rest von A/B sauber teilen können, denn A ist ja gleich n*B + Rest(A/B).
Der ggT von A und B ist also der selbe wie der von B und Rest(A/B). Nennen wir "Rest(A/B)" ab jetzt einfach "C". Man kann jetzt also den ggT von B und C suchen - also von deutlich kleineren Zahlen.
Und dieses Prinzip wiederholt sich .- wir gucken jetzt noch, ob C ohne Rest in B passt - denn dann wäre C der ggT von A und B. - er würde ohne Rest in B passen und müsste dann nur noch einmal zu n*B dazu addiert werden, um zu A zu kommen... (C ist ja der Rest(A/B) ).
Wenn er nicht ohne Rest in B passt bekommen wir wieder einen Rest(B/C).
Wir suchen also den ggT von B und C und bekommen einen Rest(B/C)... auch hier gilt wieder, dass der ggT von B und C den Rest(B/C) sauber teilen können muss, denn B = n*C + Rest(B/C).
Wenn der Rest(B/C) sauber in C passt, dann ist das der ggT von B und C und damit auch der ggT von A und B.
Falls er nicht ohne Rest in C passt dann geht das Spiel weiter und wir nennen Rest(B/C) "D" und suchen den ggT von C und D und das so lange, bis einer der Reste sauber in die kleinere Zahl reinpasst..., denn dann ist das der ggT dieser und der nächst größeren Zahl und aller anderen Zahlen davor.
Es ist in so einem UA-cam Kommentar nicht so leicht verständlich zu machen wie in einem UA-cam Video, deswegen ist es Schade, dass sie das nicht erklärt im Video, mit anschaulichen Zeichnungen etc.
@@jeffreylebowski4927 Danke für die super Antwort, Jeffrey. Perfekt dargestellt, ich habe es jetzt auch kapiert. Ich glaube die Beweisführung hat Susanne extra nicht reingenommen, ist schon ziemlich schwierig der ganze Stoff und für die Nichtmathematiker Klientel vielleicht etwas zu hoch.
Dankeschön ehrlich danke
Wollte dir nur sagen das du jeden tag an dem ich Mathe schreibe mich vor dem durchfallen rettest :,D
Hehe, das freut mich sehr! :)
Ich wünschte, das hätte uns in der Schule auch jemand beigebracht...
Wenn man keinen Taschenrechner zur Verfügung hat und einem Divisionen zu kompliziert sind, kann man auch Subtraktionen verwenden, braucht dann aber mehr Schritte. Man kann nämlich in jedem Schritt die kleinere von der größeren Zahl abziehen und dann die größere Zahl durch diese Differenz ersetzen. Im ersten Beispiel:
ggt(356, 238) = ggt(238, 356-238) = ggt(238, 118) = ggt(118, 238-118) = ggt(118, 120) = ggt(118, 120-118) = ggt(118, 2) = ggt(2, 118-2) = ggt(2, 116) = ... PK, jetzt kommen die vielen Schritte, da wäre es natürlich gut, einfach zu dividieren: = ggt(2, 118:2) = ggt(2, 2) = 2.
... oder noch besser, auf den Trichter zu kommen, dass 2 (eine Primzahl ist und als solche) nur die Teiler 1 und 2 hat. Dementsprechend kann auch der ggT(2; n) für jede beliebige Zahl n nur 1 oder 2 sein. Und logischerweise ist er 1, wenn n ungerade ist, und 2, wenn n gerade ist.
@@teejay7578 Das stimmt, aber mir ist entfallen, wie man diese Rekursion bei der Subtraktionsmethode _allgemein_ schneller abbrechen kann. Also, wenn die kleinere Zahl nicht so klein wie 2 ist. Irgendwie gab es da glaub ich eine Regel, aber sie fällt mir grad nicht ein.
Hab die beiden Varianten grad auf Wikipedia nachgeschlagen: die klassische mit der Subtraktion läßt sich wirklich nicht schneller abbrechen, denn sie bricht erst ab, wenn eine der beiden Zahlen 0 wird. Also müßte man im vorliegenden Beispiel wirklich 2 so oft von der geraden Zahl 118 subtrahieren, bis man bei 0 ankommt. Die moderne Variante (Division mit Rest) kürzt das dann natürlich zu einem Schritt ab: 118 mod 2 = 0.
Oh, das haben wir im Studium in Algebra (1. Semester) mal gemacht. Ich meine, wir hatten das sogar begründet, aber das ist so lange her, ich hatte es tatsächlich vergessen. 😂 Hab es halt nie wieder gebraucht … 🤪
Hab's grad in Python eingetippt:
def ggT(a, b):
if b == 0:
return a
return ggT(b, a % b)
ggT(356, 238)
2
ggT(12540, 24255)
165
@Gehteuch Nichtsan Ja, die Funktion ggT() ruft in der letzten Zeile (return ggT(b, a % b)) sich selbst wieder auf, und zwar so lange, bis der Rest, der mittels Modulo-Operator bestimmt wurde (a % b), Null ist.
Ich schreibe das jedes mal so:
def ggT(a, b):
while b != 0:
a, b = b, a % b
return a
Persönlich finde ich die Variante besser, weil Rekursion mehr Speicher braucht und langsamer ist. Der Algorithmus an sich geht aber so schnell, dass es wahrscheinlich keinen Unterschied macht, und ich höre oft, dass man meine Version schlecht lesen kann.
@@kappasphere Du hast die iterative Variante gwählt, die ist sicher programmiertechnisch effektiver und definitiv nicht schlecht lesbar.
Dankeschön
Gerne :)
meine güte du hast eine so wunderschöne schrift. und eine so wunderschöne stimme. und du bist auch noch so wunderschön🫣ich glaube du bist das beste was einem inf-ro-ma(nn)-tiker passieren könnte😇heschtekheiratemirdoch
PAUAWOMAN _-bilbe wei ud tsib-_ fil libe su dir
So verstehe ich das auch aber ich würde eine Erklärung zu der Definition vermissen. Da hab ich aktuell Probleme mit dem formalen beschreiben und wie man anhand so ein Text es versteht. Was wäre eventuell hilfreich noch.
Satz: Euklidischer Algorithmus
Seien a, b ∈ ℤ mit a ≠ 0. Dann lässt sich der größte gemeinsame Teiler von a und b wie folgt eindeutig bestimmen:
Wir dividieren b durch a mit Rest und erhalten b = q1a + r1 mit 0 ≤ r1 ≤ |a|.
Falls r1 = 0 ist, so ist |a| = ggT(a,0) und mit dem vorangegangenen Lemma gilt ggT(a,b) = ggT(a,r1) = ggT(a,0) = |a|.
Falls r1 ≠ 0 ist, dividieren wir a durch r1 mit Rest und erhalten a = q2r1+r2 mit 0≤r2 r1 > r2 >... > rn > rn+1 = 0. Da es nur endlich viele ganze Zahlen zwischen |a| und 0 gibt, ist sichergestellt, dass das Verfahren irgendwann
terminiert. Auf diese Weise erhalten wir eine Reihe von Gleichungen der Form:
Bei so was tu ich mich aktuell noch schwer
Prima - aber wie gehe ich denn bei mehr als zwei zahlen vor?
Hallo MathemaTrick, weißt du eigentlich, weshalb andere Mathe YoutTuber, speziell spiele ich auf Daniel Jung und Lehrerschmidt an, den Euklidischen Algorithmus nicht präsentieren? Er ist ja viel effizienter als die Primfaktorzerlegung ...
Was Die vor der Taschenrechnerzeit schon für den Comouter herausgefunden haben 🤗
Schöne Technik aber wie mache ich das bei 3 oder mehr Zahlen
Den ggT der ersten beiden Zahlen zur dritten Zahl gesellen und das Verfahren erneut anwenden.
@@Waldlaeufer70 Danke für deine Erklärung 😄😄
Mit Lambda Ausdrücken kann man den Algorithmus rekursiv in eine einzige Programmzeile schreiben: (C#)
ggT(int a, int b) => (b == 0) ? a : ggT(b, a % b);
danke schon
Hast du im Studium programmieren müssen? Dieser Algorithmus schreit doch gerade zu als Programmierübung für rekursive Programmierung 🙂
Ich hab's immer Iterativ geschrieben. Aber für beide Fälle ist das echt ne nützliche Übung
MfG
❤️❤️
Anscheinend hatte ich nur unfähige Mathelehrer... sowas nützliches nie in der Schule gelernt.
Yippie euklidischer Algorithmus, ich habe sie so geliebt, jetzt fehlt nur noch chinesischer Restsatz de.wikipedia.org/wiki/Chinesischer_Restsatz
@Gehteuch Nichtsan Auch wenn Du mir scheinbar ignorant erscheinst, sowas wird in der Universität (Informatik und Mathematik) gelehrt... Wenn Du etwas nicht verstehst, dann frag normal nach. Warum so feindseliger Antwort?
@Gehteuch Nichtsan Sekte der "geistig nicht stehen gebliebenen" In Deutschland leider mit abnehmenden Mitgliederzahlen.
Und jetzt den Beweis (hihi). 🙂
Ich liebe dich
Mit dem Gamma GT Wert sollte man sich über seine Leber erhebliche Sorgen machen....
Seien a_{0} und a_{1} zwei natürliche Zahlen mit a_{0}>a_{1}. Betrachte
a_{0}=q_{1}*a_{1}+a_{2}
a_{1}=q_{2}*a_{2}+a_{3}
. . .
a_{n-1}=q_{n}*a_{n}+a_{n+1}
a_{n}=q_{n+1}*a_{n+1}+0
Dann ist a_{n+1} ggT(a_{0},a_{1})
Denn Rest 0 erhält man auf jeden Fall, da es offensichtlich ist, dass a_{1}>a_{2}>a_{3}>...>=0 gilt.
Beweis:
Teil 1: Sei d ein ganz beliebiger Teiler von a_{0} und a_{1} => d ist ein Teiler von a_{2}=a_{0}-q_{1}*a_{1}, a_{3},...,a_{n+1}.
Teil 2: Aus a_{n}=q_{n+1}*a_{n+1} folgt, dass a_{n+1} ein Teiler von a_{n} ist => a_{n+1} ist ein Teiler von a_{n-1},...,a_{1} und a_{0}.
Insgesamt folgt, dass a_{n+1} ggT(a_{0},a_{1}) sein muss, denn gebe es einen größeren gemeinsamen Teiler, so wäre es ein Widerspruch zu Teil 1, da a_{n+1} durch diesen Teiler nicht teilbar wäre.
der Dividend erinnert mich an Computer 😎 und CR7 ⚽⚽⚽⚽ ⚽ ⚽⚽⚽⚽
Ja, das kannte ich auch noch nicht.... Glaube ich :-)
Der Beweis fuer den Algorithmus waere sicher auch interessant.
Bitte niemals sagen, dass man bei irgendetwas nicht mehr zu denken brauche - das Hirn eingeschaltet zu lassen ist nie verkehrt und kann trotzdem oft noch Arbeit sparen:
1. Sobald als Rest 1 raus kommt, muss der ggT 1 sein.
Grund: Die nächste Division geht dann durch 1 und ist immer restfrei.
2. Sobald als Rest eine Primzahl raus kommt, muss der ggT entweder diese Primzahl (falls die andere Zahl ein Vielfaches davon ist) oder 1 (sonst) sein.
Grund: Der Algorithmus funktioniert, weil der Rest denselben ggT wie die beiden Ausgangszahlen hat. Und der ggT einer Primzahl kann nur 1 oder sie selbst sein.
Die Hälfte von 118 hätte man somit nicht mehr explizit ausrechnen müssen, sondern direkt entscheiden können, dass der ggT 2 ist, weil die 118 gerade ist - bei einem ungeraden Dividenden wäre er 1 gewesen.
Nicht gewusst
Wiso lernt man das nicht in der schule 😅
Diese doofe primfaktorzerlegung 🤬🤬
Nicht nur das WIE, sondern auch WARUM das WIE funktioniert, interessiert. 😎➗
Habe eine Erklärung gepostet, die ich mir überlegt habe...
Seien a_{0} und a_{1} zwei natürliche Zahlen mit a_{0}>a_{1}, dann gilt
a_{0}=q_{1}*a_{1}+a_{2}
a_{1}=q_{2}*a_{2}+a_{3}
. . .
a_{n-1}=q_{n}*a_{n}+a_{n+1}
a_{n}=q_{n+1}*a_{n+1}+0
und a_{n+1} ist ggT(a_{0},a_{1})
Denn Rest 0 erhält man auf jeden Fall, da es offensichtlich ist, dass a_{1}>a_{2}>a_{3}>...>=0 gilt.
Beweis: Teil 1: Sei d ein ganz beliebiger Teiler von a_{0} und a_{1} => d ist ein Teiler von a_{2}=a_{0}-q_{1}*a_{1}, a_{3},...,a_{n+1}.
Teil 2: Aus a_{n}=q_{n+1}*a_{n+1} folgt, dass a_{n+1} ein Teiler von a_{n} ist => a_{n+1} ist ein Teiler von a_{n-1},...,a_{1} und a_{0}.
Insgesamt folgt, dass a_{n+1} ggT(a_{0},a_{1}) sein muss, denn gebe es einen größeren gemeinsamen Teiler, so wäre es ein Widerspruch zu Teil 1, da a_{n+1} durch diesen Teiler nicht teilbar wäre.