Bestand wählen
Merken

Euklid

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
die Tagen an der TU Darmstadt das
Wort einmal herzlich Willkommen schön guten Morgen wenn sich jetzt alle gefunden haben noch zusammensetzen wollen und sollen wir dich gern loslegen ich hab zwar organisatorische Dinge zu sagen und das eine scheint ein Missverständnis zu sein dass in einem Übungsgruppen und ich weiß nicht wo es herkommt aufgetaucht ist oder und da gab es jetzt tatsächlich gab es doch Gruppen abgaben ich dachte ich hatte das klar genug gesagt du bist geladen klar genug kommuniziert aber ich Communities auch gern noch mal klar jeder bitte seine eigene Übung aber er also nicht im die PanAm auf ein Blatt stehen und dann zählt das für alle werden dass es bei den 1. Platte irgendwie ohne größeren Eck lösen aber auf die Dauer geht das nicht also ab den 2. Platz bitte keine Gruppen Abgaben mehr sondern jeder schreibt sein eigenes Blatt und geht es ab gut dass das eine und das andere ist Ankündigungen ja zur Vorlesung zur Klausur nahm zusammen mit dem Treffpunkt Mathematik ist wird sozusagen Rahmen des Treffpunkts mal den Artikel nach der Vorlesungen in Linz zu Beginn der Semesterferien noch den Klausur Vorbereitungskurs geben so in einer Woche ein paar Termine im Sinne des treffen sowie im Treffpunkt auch eben offenes Forum für ihre Fragen ist wo natürlich auch wir uns was überlegen was wir da noch mal erzählen können was so die klassischen gefallen sind das ist gerade in der Planung ich wissen was schon mal bis ihn schon mal sagen und dass also die Planung ist im Moment das stattfinden zu lassen der Woche 20. bis 24. April Februar sodass sie da noch so an ein 2 Wochen Zeit haben bis zur Klausur am 8. März die dortigen Erkenntnisse auch nochmal zu verdauen das für die na das es so noch machen und alles was sie sich jetzt schon mal überlegen wenn so zeigen jetzt im Lauf der Vorlesung wir merken es gibt die sich auch eine langfristige nochmal Wiederholung vertragen dann sammeln sie die und melden Sie hier die damit sie ihre Meldung und hat vor sich so noch mal was zu machen das sind die organisatorischen Dinge ja auch ich kann an der Stelle noch nochmal sehr für den Treffpunkt werden Sie kennen Termine montags bis geht zum Treffpunkt auch ein Modell Veranstaltungen wurde mit Forum und allem was dazugehört auch da die herzliche Einladung sich da anzumelden und bringen Sie sich in den Treffpunkt ein weil nur dann kann man wirklich weiß man genau wo die stellen sind wo es lohnt noch mal was zu wiederholen so dass zum organisatorischen inhaltlich hatte ich in den Beginn der Modulo Rechnungen gebracht ich habe also erklärt was den Rest Modulor n NS und und jetzt mit dem Rechenregeln einsteigen ich letztes Mal gezeigt hat und ich würd gern am Anfang für alle die die Fäden des Modulo hört sich an wie böhmisches Dorf sagen dass das wie so oft etwas ist was wir wirklich furchtbar kompliziert aussieht und was sie alle aus dem Alltag kennen jeder von ihnen rechnet jeden Tag modulo nur sie merken es nicht mit wie viel Uhr es ist in 5 Stunden nach 11 4 1 also 11. 5. hier nur 12 Uhr oder welchen Monat haben Sie haben sie 8 Monate nach Oktober nicht in 18 Monaten allein den 6. ja weil 10. 8. 6 Uhr 12 ist Mehr also jeder rechnet ständig Modulor würdig das heißt das was wir hier machen es überhaupt kein Hexenwerk ist nur anders aufgeschrieben was man das gewohnt ist aber vielleicht so als Hilfe wenn Sie so zu sein sich von was vorstellen wollen denken Sie in Stunden und machen Sie das in gleich 12 dann haben Sie die ganz normale Uhrzeit oder wenn sie ganz mitteleuropäisch die 24 gewohnt sind können Sie natürlich in der 24 setzte Moloch 24 echt deren gut also hab letztes Mal gesagt am Schluss und das welches noch beweisen dass war der Satz 1 5 1 bis es Raos mischen sich in die leben doch jetzt tut .punkt aus irgendeinem Grund tut sie es die alte Mehr Computer sein deterministisch glaub ich ihn nicht sah also Satz 1 5 und da habe ich ihn Rechenregeln für das nur hingeschrieben jeweils gleich beweisen wollen und wenn sie sich die mit Uhrzeiten vorstellen sind die auch völlig natürlich und die Rechenregeln sagen wesentlichen immer ob sie zur 1. rechnen also erst die Rechenoperation ausführen wie das Plus und dann un rechnen oder ob sie zuerst jeden einzelnen Summanden modulo n reduzieren und dann bloß rechnen ist im Prinzip egal sie müssen am Ende noch mal das Ergebnis Modulo n reduziert das Gleiche gilt fürs malen also wenn sich hier Vopos steht jeweils einmal .punkt hinsetzen gilt die gleiche Rechenregeln und das Gleiche gilt fürs potenzieren zumindest für die Basis also wenn sie a hoch b ausrechnen und das Modul un reduzieren dann können Sie auch zuerst das aber nur in reduzieren und dann diesen erst hoch nehmen und danach das ganze wieder modulo Ecken und hier für diese letzte Regel hätt ich gern keine negativen Zeiten Phonds liegen also keine negativen B weiterzufliegen was z raus sahen also reisen wir das an Nachrichten mit der Definition der ohne Rechnung also wenn man den A 1 oder allgemeinen sie a und b aus Z haben dann brauchen Sie jetzt den von B A und Medien der Rest modulo N und würde wenn man damit weiter was machen wir brauchen auch die Quotienten also die setzen wir mal wieder ein nicht KK sei der ganzzahlige Quotient von A durch N und L sei der ganzzahlige Quotient von des durch en so was heißt das das heißt Sie haben das kann man ne Plus die Zahl an modulo Ehen und dass das B das Ehrenmal Erlösplus die Zeit des Modulo das war ganzzahliges dividieren es gibt eindeutige Zahlen kurz lässt zu dass sie das A und das B so schreiben können so und wir machen uns jetzt an die Teile A B
und C hin also wir wir wollen wissen was a +plus b Module also ich nur mal aus was is a +plus gehen mehr nach dem was wir gerade uns überlegt haben ist diese Zahl kann mal n +plus am Molo B A modulo Innen und das DSL mal n +plus b modulo N das kann ein bisschen umsortieren das ist K +plus L mal +plus an oder n +plus BMO nur einen so war damals dass der Name jetzt den ganzzahliges Vielfaches von n +plus irgendwas nehme jetzt auf beiden Seiten der Gleichung zum Rest in übergehen dann kriegen wir das +plus b Modelo enden das gleiche ist wie dieser Ausdruck hier oder das Vielfache von allen nur spielt für den Rest keine Rolle der Ausdruck lästig n teilbar der fällt komplett weg also bleibt übrig modulo M +plus B modulo enden und das ganze nur un und das ist die rechte die Übertragung des Beweises von plus
aufmalen ich denke ich mir dass du selber machen er setzte sie das Plus durch Marens geht gut ich mache noch die Potenzen um die Potenz wenn man schlichtweg das Produkt zurück dann also auch die dort enden wollender ausrechnen was ist das dass es aber man nochmal ganz schön viel an nämlich bestücken modulo enden Na ja und jetzt können wir die denn teile der verwenden 10 Produkt Modelo enden das können Sie jetzt aufspalten als am aber mal an nur noch dem -minus 1 mal 1 und das Molo M multipliziert mit Volo und das Ganze wirkt nur das war der Teil wegen dem also 10 Produkts nehmen sie die B -minus 1 1. dem es als 1. und den letzten oder der werden darauf B an und das können Sie jetzt sukzessive immer weiter machen n also immer noch den nächsten Faktor einzeln rausnehmen wenn
wenn Sie dabei immer weiter machen dann kommt am Schluss genauso aus lauter Faktoren modulo allen davon die Stücke und Flussbett bitte schön noch mal Modul an zusammen dessen die Rechenregeln und wie gesagt die Bedeutung der Rechenregeln ist ein der entscheidend wenn Sie moderne rechnen dürfen sind lebenswichtig Schritt nach jedem bei jeder Rechenoperation Einzel 1. diese Mann über die Faktoren Mode berechnen und könnten und dann rechnen und das reduziert die Größe der Zahlen mit denen sie zu tun haben gewaltig bisher an einem Beispiel zeigen in dass man damit durchaus Sachen beweisen kann die nicht offensichtlich sind wir schauen uns an den Ausdruck der ist es wirklich einfach frei erfunden 9 minus 15 mal 23 +plus 700 und 5 und das Ganze hoch 322 oder wir wollen wissen was es das nur 7 da kann man sie nur mit Mühe hatten raten ist nicht schlecht weil sie haben wird Trefferwahrscheinlichkeit von einem das ist denn es gibt nur 7 verschiedene 1. Module singen aber könne rechnen und mehr man würde man sagen soll man das ausrechnen aber ohne Taschenrechner geht das gar nicht die sagen das geht problemlos ohne Taschenrechner und es geht deswegen Probleme ohne Taschenrechner weil wir unsere ganzen Rechenregeln haben wir dürfen zum Beispiel die die Basis dieser Potenz Molo 7 reduzieren bevor wir die Potenz ausrechnen das heißt sie können das umstellen zu nein -minus 15 mal 23 +plus 700 und 5 nur 7 dann diesen Rest doch 322 dann ist es am Schluss nochmal Modelo 7 wählen so wir werden sie aber die anderen in diesen Teilen auseinander dann kriegen wir was dann kriegen wir 9 oder 0 7 -minus 15 Modolo 7 so das multipliziert mit 23 0 0 7 +plus 705 0 7 so diesen ganzen Murks Yusuf 322 da der nein und 322 und dann am Schluss und im Kopf Zeile sieht es furchtbar lange aus aber der
Vorteil ist jetzt ist einfach weil was ist 9 oder 0 7 der Rest von 9 wenn sie durch 7 teilen es 2 wenn Sie 15 durch 7 teilen ganzzahlig bleibt dann geht 14 gut und ans Platten Rest von 1 23 Modelo 7 was ist da noch Quartal war 21 ist durch 7 teilbar bleiben 2 705 wissentlich auch freundlich bei 700 es offensichtlich durch 7 teilbar also bleiben 5 dann also aber dass sie auch 322 und das dann Mono 7 was steht da 2 -minus 1 ist 1 mal 2 bis 2 Moment mal doch doch genau es ist 2 plus 5 bis 7 also 7 auf 322 Mod 7 und das bitte nichts denn das eine zücken und 7 auf 322 ausrechnen sondern normalen Anteil den 10. verwenden das ist nämlich 7 und 7 hoch 322 man 7 und dann sehen Sie das ist 0 bei Siegen und 7 bis 0 und egal wie oft sie nur noch sich selbst hoch irgendwas Länder dass sie nicht mehr viel also bleibt nur übrig Nazis extrem ausführlich vorgerechnet ja ja nein der haben sie es nicht falsch so aber sie Recht ein ich müsste meinen Sie mein und an der Stelle gehören ja wenn man es ganz aber nach Geld jedoch nur 7 ändert aber nichts gut doch werden nur raus und wir haben damit gezeigt dass dieses Monster von Zahl da oben bis 7 Tage ist hätte man so nicht unbedingt gesehen haben mehr also wir haben damit 7 teilt dieses den Abend seit die Zahl 9 minus 15 mal 23 +plus 705 auch 322 wenn sich selbst mal ein bisschen versuchen wollen Klaus steht
Übungsblatt drauf dann zeigen Sie mal das 5 die Zahl 3 hoch 444 +plus 4 hoch 333 teilte sieht man auch nicht direkt bin Module Rechnung umsetzen Patzer in dem die und der Trick ist eben immer man darf reduzieren bevor man potenziert bevor man addiert bevor man multipliziert und das werden sie aber Übungsplatz sehen solche modulo Berechnungen sind insbesondere dann wenn es Unteilbarkeit geht oder wenn es darum geht um die Frage sind irgendwelche ganzzahligen Gleichung lösbar ganz oft hilfreich und ermöglichen 1 Einblicke die man eigentlich so nicht erwartet hätte dass das so sind nun nur zu tun hat gut das ist ganz grob die Einführung in dieses Modelo rechnen das wird uns immer wieder begegnen für ihn immer wieder begegnen also auch aus dieser Vorlesung heraus nach dieser Vorlesung außerhalb dieser Vorlesung werden und innerhalb von wir mal die sich so daran gewöhnt dass ihm ganz selbstverständlich über die Lippen geht das sind 2 3 +plus 8 auch mal 1 wenn Muluzi an und dann wundern sich nur noch die die neben ihm sitzen der Cafeteria drüber was sie da Frank hat Recht in allen und wie gesagt ich ging danach auf und sagen und reden ganz selbstverständlich davon dass 2 Stunden nach 11 1 sagen Sie das können Sie sagen genau den gleichen Grad schon bevor auch gerechnet gut das ist das ist Mono Rechnung dieser kommt immer wieder wir bleiben Bereich Teilbarkeit ich hatte ihn am Anfang der Begriff das größte dieses Abschnitts den Begriff größten gemeinsamen Teiler definiert und den wir uns jetzt ein bisschen wird man und was ich Ihnen
zeigen will ist ein ganz starkes ließ mich in dem Zusammenhang das uralt ist aber immer noch guttut dass der so genannte euklidische Algorithmus unter dieser Algorithmus ist eine ein algorithmisches Verfahren wie sie zu 2 beliebigen ganzen positiven Zahlen also 2 belegen natürlichen Zahlen der GGT bestimmen kann algorithmisch Berg nach einfachen 3 in Teilzeit programmierbaren Rekursion und die bestimmt den für 2 beliebige Zahlen also das ist das Ziel des jedes Abschnitts ist die algorithmische Bestimmung des geht der Text und das schöne ist der euklidische Algorithmus liefert eben eine praktische Methode den zu bestimmen aber liefert auch wenn der Rhein in der warte ich abstrakte Betrachtungen in ganz wertvolles Hilfsmittel um dann Theorie über den GGT zu machen und das entscheidende was man sich überlegen muss auf also die entscheidende Beobachtung auf dem dieser Algorithmus fußt sind die folgenden 2 die nämlich mal 1 8 jetzt ist steht die Frage im Raum was bitte schön ist ein Lemma das hat mit Lamm nix zu tuen jemals ein lateinisches Wort und heißt so viel wie ja das ist Nebel wir also in den meisten ist Salz ein einen Satz den man beweist der genauso mehr wir gebeten wahre Aussage denn darin andererseits aber auch der aber eigentlich dazu dient später an einen großen Satz zu beweisen und außerhalb des nicht so wahnsinnig viel Bedeutung hat mal Sonne mal ist normalerweise in Hilfsgröße die man später braucht mit Werkzeug mit dem man sich danach aber nicht mehr viel auseinandersetzt gut und was sagt uns dieses Lemma das sagt man sich 2 natürliche Zahlen vorgeben und ich will mal nicht die 0 dabei haben sonst das mit dem Digit-Team sind langweilig werden und ich setzt aber voraus dass das größer gleich B ist das ist keine wirklich üben wahnsinnige Voraussetzung wenn jemand 2 Zahlen gibt und diesen hat falls Kunden denn diese so Mehr wenn Sie das was bisher aber belegen dass es bisher die war und wenn es gut das ich will nur nicht mehr Hunde Fallunterscheidung haben zwar also an b sein 2 natürliche Zahlen und da Größe gleich B dann ist eine würde die Modulo Rechnungen GGT auszurechnen wenn sie den GT von A und B suchen dann behaupte ich sie können auch den GGT suchen von der Zahl B mit der Zahl Modulo und diesen gleich das ist deswegen so schön weil die Zahl am modulo B nach allen Regeln der Kunst natürlich kleine also des ist da wird also muss sie sein weil der Rest ist immer kleiner als der der Module also und Lobbyisten B und B ist auch der gleich das heißt die beiden zahlen Sie rechts in die die Täterin haben sind leider gleich B und damit haben sie das Problem auf kleinere Zahl reduziert vor Vorhaben sie A und B 1 haben sie Zeit sein die kleine gleich B sind das ist das Problem der GGT Bestimmung des auch 2 kleinere Zahl reduziert und das ist schon die Grundideen Euklidischer Algorithmus war das können setzen sich jeder wie will zensiert wenn Sie die GDT von A und B haben wollen wenn sie den von Beeren am Automobilunternehmen sie wieder den die GT von andere B und er wurde Luamodul nach die Weise die Zahl immer kleiner und irgendwann steht der GGT von 500 1 da und dann ist es nicht mehr so schwer den abzulesen und abzulesen braun sind halt die von Lemma und der sagt wenn sie es irgendwann schaffen dass ihre Zahl die die Zahl an teilt dann ist es mit dem GGT einfach mal eines der GGT von A und B natürlich du bei den ist den Teile von A und B in Teile von b und dann passt das gut an und beweisen dass Lamar
Wien das Lemma hab ich auf Folie dabei dann das hier Proben aus dem Focus rutschen und sie uns trotzdem war zur und weil der Beweis von ist die Hauptarbeit für deutlich verloren also das müssen wir zeigen müssen zeigen der GGT von A und B ist derselbe wie der GGT von B und A Modulo P damit wird drüber reden können nicht mal den GGT von A und B den ich mal die dabei geht es nur meinen Namen Setzung das ist das Ding das versuchen so was geht es für dieses die wir wollen dass wir das die was rauskriegen dass überlegen mal das Wissen über das die dass dies der größte gemeinsame Teiler von A und B also geht man auf jeden Fall das ist Haider ist das heißt die Zeit aber und Details wie ihn wenn wir wissen dass die Arterhaltung Details teilt ein bisschen was über die modulo über die die 1. wenn sich die durch die teilen wenn Sie es genau haben wollen es dir das richtige Referenz die Übung 1 4 und die sagt Ihnen das dann Monolog des kann da modulo des genauso wie Ben oder nur den dass die beiden 0 sind das teilte Z eben und sorgen in jetzt fangen an anders zu rechnen was müssen wir zeigen wir müssen zeigen das das des auch der GGT von B und Lobbyisten also mal zumindest jetzt zu zeigen dass modulo B überhaupt mit Teil dafür ist bei den es keine Teile ist dann kann so vielleicht der größte gemeinsame sein wir also schon mal das Hobby das die teilte mit dass das die des Amur Lobith halt so also schauen wir uns mal an was es an Modelo B Monodie in dem mit dem Ziel dass es bitte schön wohnen wollen das Gegenteil davon aber Lobbys der größte gemeinsame Teiler von b oder a Modedesigner Sumsemanns müssen Teile von Amor Lobbys ein sagen was ist Autolobby aber Lobby ist nach der Devise Division mit Rest der den sie kriegen wenn sie vom abziehen den Quotienten den ganzzahligen Quotienten a durch b May B 1 also und so war genau der Rest definiert die Differenz zwischen dem was sie noch verteilen können und dem was also dass das was übrig bleibt verteilen und das Model Degen sagen wenn jetzt
kommt unser Rechenregel Satz von gerade eben der Satz 1 5 eine Differenz die können wir einzeln Modelo rechnen dass es Molodi Nina aus ganzzahliges Quotient von a mal b Immuno D und dann müssen wir das ganz sicher wieder Mono den in sagen kann das hier vorne bis zum Beispiel die teilt er habe geht Zeit also das nur den 0 in hier am besten Produkt stehen 2. Mann und Produkt stehen oder nur des das gar noch weiter aufregen wieder nach 1 5 ist das ist das der ganzzahlige Quotient von A und B Molodi des multipliziert mit Tremolo des Mann das ganze Modelo den und wenn man jetzt ganz exakt ist meine große Klammer drum rum und das Modul und in dem es das letzte nur die und ist ist so das sind jetzt wahnsinnig unübersichtlich aus aber es ist genau anschaut ist es schön weil über das hier wissen wir was das Display modulo D dies der größte gemeinsame Teiler von A und B als es die insbesondere Teiler von b Zeit B also dass das hier 0 das haben nun mal irgendwas nur irgendwas kennen Nummer ist 0 also steht der nur minus 0 und nur dem Mut und dem Modul D egal da kommt einfach noch Rossen so also was haben wir damit gezeigt damit habe gezeigt dass das die die Zahl am Mundbild teilt nun damit haben wir schon mal diesen gemeinsamer Teiler von ja 2. 0 1 0 im Moment da in der 4. Zeile steht es also das steht also wenn wir und so war es gut dass wir die Klammern erinnern aber ja aber mit dem ist Physiker natürlich ist es eine Frage als würde sie es aufschreiben sie können sagen sie sie sie für Bewerber von sich Absatz 1 5 und ziehen alles auf einmal man machen über 1 9. einzeln oder ich hab jetzt also zeigen die getrennt das ist als 1 5 und das ist als 1 5 ja immer mehr Routine hat dann macht man sie 2 Schritte auf einmal zu haben denn also der Anbieter da Modelo B was wir natürlich auch haben und das haben wir schon die ganze Zeit ist die teilt Ihnen insofern ist die auf jeden Fall mal ein gemeinsamer Teiler von Amor Lobby und B und das einzige was uns noch zu tun bleibt ist das Wort größter nur wenn es ist gemeinsamer Teiler aber die Behauptung ist dies der größte gemeinsame Teiler von Amor Lobby und belegen und das ist noch zu zeigen es ist immer gut
sich zwischendrin mal zu überlegen wo war ich stehen also wo stehen wir was müsse man noch zeigen müssen noch zeigen der ist der größte gemeinsame Teiler an gemeinsamer Teiler Amber also von in von B und der Zahl an Boden begegnen so ne zeigen wir bitte schön das der der größte ist nur was wir tun müssen Sie haben die Menge der Zahl der gemeinsamen Teiler und sie müssen zeigen wie es der größte davon das größte Element klassische Klarsicht also wenn Sie so eine Situation haben dass die Methode über die gleiche das was ich in der Zeit der Stille vor für funktioniert hier sollten Sie sich aber als grundsätzlichen Ansatz Beweis Ansatz merken wenn Sie zeigen wollen irgendwas ist das größte ist der Ansatz immer der gleiche sie nehmen sich in anderen gemeinsamen Teiler an also Zeit sehen und gemeinsamer Teiler von B und Monologe in könnten sich ganz spitzfindig sagen was wenn es nur ein gibt es gar ich nehme und gemeinsam Teile der C könnte zufällig Design nur hab ich kein Problem mit aber sie ist ein gemeinsamer Teiler von b und a Lobby und was wir zeigen ist dann ist sie kleiner gleich die also zeigen Sie ihren gemeinsam bei der Minister immer kleiner oder gleich dem des und damit ist der größte weil jeder anders Kleider gleich das im Prinzip genaue Definition von guest Element ja aber das ist immer die Methode werde sich einen gemeinsamen Welle 1 ein denn das ist die gleiche Eigenschaft hat wie das von dem man zeigen will es ist das größte und zeige dass es immer kleiner gleich den von dem man zeigen will sahen was heißt das winzige gemeinsamer Teiler von b und a Mode Lobiisten dann heißt das zum meinem dann heißt das dass CBI teilt und sie die Zahl am Modelo Beta das ist genau die Eigenschaft gemeinsamer Teiler zu sein also teilt das sehen Euro Summen von diesen beiden Zahlen was Sie können jetzt B und A Modelo B nehmen und die beiden ganz beliebig oft miteinander addieren und ist halt ist sie immer noch und was ich machen will ist ich schaue mir die Zahl an K mal b +plus oder wegen Zellen Kaarst Z nun wieder einiges Chaos der 10 nehmen diese Zahl kann man dem Fluss Amur B wird immer noch von C geteilt weil sie halt das B und C teilt das und ob ich damit also ist die Frage von wo und die Summe von Enteignung wir so und jetzt wenn wir das BKA ganz speziellen so dass K nehmen nämlich als den ganzzahligen Quotienten von A und bilden und was haben wir dann dann haben wir dass dieser Ausdruck der die Kammer des Plus an oder bilden kennen wir dann das ist dann das ganz seine Quotient von Arma a durch B mal B +plus an Monolog B und nach Definition der Division mit Rest ist das genau war ist Kals genau gewählt das da rauskommt
also ein Teil von 8 1 c'était Kammer des Plus-Abo Lobby für jedes Star also auch für dieses K und damit ist sie in Teil von a so wird das 10. davon aber C ist auch ein Teil von b das heißt sie lesen gemeinsamer Teiler von A und B in den 1. gemeinsamen Teiler ist da muss auf jeden Fall kleiner gleich dem größten gemeinsamen Teiler von a und b sein bei der größte Gemeinde dass der größte gemeinsame Teiler und jeder andere gemeinsame seiner kann nicht größer sein aber das ist den und dann immer gezeigt und in jeder gemeinsame Teiler mit von B und am Ort begehen ist kleiner gleich gehen und damit ist den der größte gemeinsame Teiler von b und und begehen vor der 1. Teil
an in Teil A sagt genau der GGT von A und B ist der GGT von A und da er von deren am so hat Intel B ja für ja das Volk bei der gezeigt habe jeder gemeinsame Teiler ist kleiner gleich sind Sie an sich ziehen sich gemeinsamen Teiler 10 und wann immer sie ihren gemeinsamen Teiler haben kriegen so aus dass kleiner gleich die also ist jeder Größe bei jeder anderes kleiner gleich dass das war die ganze Rechnung auf diesem Blatt hier also das ist da habt ihr und Schwierigkeit des Beweises tatsächlich genau das zu zeigen dass es der größte in jener Zeit wieder anderes gleich ja also den Karren wir haben die gesetzt also die die Frage ist die Annahme war dass die das der größte gemeinsame Teiler ist das und sie haben wir Angst dass wir zu dem Kreis gedreht haben dass wir das verwenden bei das wäre sozusagen das voraussetzen dass wir zeigen wollen ja ja das ist nicht so also wir dass die aber einfach ist der Abkürzung jetzt wie GGT von A und B also hab ich gesetzt und ich zeige wenn die der GGT von A und B ist dann ist der auch der GGT von B und A Monologe dass es andere Zahlen allgemein ja also ist nicht sagen ich werde dagegen dieses Titelbild sondern ich bin der GGT von den 2 Zahl ist dann ist der auch der GGT von den 2 an der Zahl und wie gesagt die Idee davon ist die neuen Zahlen die man kriegt sind kleiner das heißt mit diesem Schritt reduziert man die Schwierigkeit des Problems aber statt GGT von A und B auszurechnen reicht das wichtige GT ausrechne von B Arm oder loben das ist die Grundidee und das hat mir gezeigt dass bei dieser Übergang von A und B zu be oder arm oder die bitte geht sichtlich änderten sonst noch Fragen in guter Mann im Peter es einfacher was sagte Detail wenn die Zahlen a b zufällig so sind dass das BIA teilt also an die was von ISS dann ist der GGT von den beiden B unser kurz drüber nachdenken sagen sie klar der weiß es auch relativ kurz also wir haben 2 Zahlen a und b a größer 0 größer 0 ganze Zahlen und wir wissen geht halt und was geht dann und dann ist B in gemeinsamer Teiler von a und B warum Na ja ist halt an und das BGB Teil dieses nicht so wahnsinnig verblüffend oh also der in gemeinsamer Teiler von A und B also das Baby Zeit wenn Sie mir hoffentlich glauben so jetzt nehmen sich irren in gemeinsamen Teiler von A und B hier warum mache ich das das Problem ist wieder größter gemeinsamer Teiler zu zeigen dass sie am besten gemeinsamer Teiler von A und B aber sie müssen noch zeigen wie ist der größte gemeinsame Teiler also Methode wie gerade eben sehen sich ihren gemeinsamen Teiler das C und zeigen dann ist sie kleiner gleich B ja aber das ist jetzt nicht wahnsinnig aufregend weil wenn 10 von A und von B ist also dann ist insbesondere zählt halt wie immer und wenn die Zahl der andere Teil dann muss sie kleiner gleich sein also ich meine 17 kann ich 4 teilte weil immer kleiner gleich der Zahl und dementsprechend zieht eine gleich be wenn man war schon fertig in zusammen haben Sie damit das B der GGT von A und B in Sachen im ihn gesagt das Ganze das ist der mühsame Teil vom euklidischen Algorithmus das ist das wo die Arbeit drinsteckt was wir jetzt haben ist ein Verfahren werden wir gucken wie sie sukzessive das Problem GGT von 2 Zahlen berechnen kleiner machen können sie machen jeden Schritt echt einfacher das Problem dass die Zeit nicht kleiner und damit kriegen sind sehr sehr effizient ist wenn Algorithmus zur Bestimmung von DDT wenn es mal einfach an einem Beispiel deutlich dass das Beispiel 1 9
also damit die Vorlesungen gesprengt wenn das nicht allzu groß ist aber auch was nicht 100 Prozent offensichtliches 128 und 36 ich bin mir sicher wenn sie jetzt zum bisschen mit probieren draufgehen sind sich schnell als ich mit dem Algorithmus das ist liegt daran dass die Zahlen halt relativ übersichtlich sind ich in siebenstellige und zehnstellige Zahl gibt dann nehmen Sie auch über den Algorithmus aber wir die Vorlesung soll das mal tun also was müssen wir machen Lärm an der B 128 und 36 und wird sagt uns unser sagt sie unser war wenn Sie denn die geht jeder ausrechnen wollen dann können Sie das Problem reduzieren in den See nicht den GT von den beiden ausrechnen sondern den von B und arm oder mobil also sich eben das Bier nach vorne und Schelten kommt am oder 1 muss man bisschen nachdenken zwar nur bis 72 dreimal B ist dann 108 108 ist also durch 36 teilbar dableiben Rest von 20 also das Lobby 20 an also hier schieben sich mit dem B nach unten und dann rechnen Sie hier oben dann rechnen Sie hier Modulor und schieben das Ergebnis darunter an und das ist der Algorithmus so ist aber das Problem von 8. anziehen 36 schon auf den GT von 36 und 20 reduziert also noch nach dem nach von dem Lemma gilt jetzt schon hier GGT von 128 und 36 als bin und Grüne egal ist der gegen den von 36 und 20 und wenn man Menschen wird man jetzt an der Stelle spätestens ab und sagt er man Rechner ist es mein Rechner rechnet weiter solange bis des Abbruch Kriterium erfüllt ist und das es ist sehen Sie gleich also was heißt das wenn wir die GGT hiervon ausdehnen sollen Rechner nicht die geht sie davon aus sondern den von Big B und A Modelo B also den von 20 und 16 hier also auch hier wieder die 20 rübergeschoben hier Modelo gerechnet und das Ergebnis heruntergeschrieben träge also raus das ist der GDC von 20 und 16 sehen es bleibt wirklich 4 auch wenn man jetzt hier weiter rechnet 16 rüberschieben was es 20 modulo 16 20 Modelo 16. 4 also kriegen Sie hier das ist der GGT von 16 und 4 und 4 rüberschieben UNO rechnen 16 wurde Luft hier ist 0 und sehen dass Sie dabei waren ätzende Situation von B von denen war ihre Anteile von 16 und den Moment wo das Gegenteil davon ist kriegen Sie der nächsten Morelos würde man wohl nur in der Art teilt eines im Arm oder Lobby 0 das heißt es in der Welt des Abbruch Kriterium für den Algorithmus in dem Moment wurde also wir nun rauskommt ist erledigt und der wenn BA teilt in diesen Schritt 4 aber vor einem Detail gesehen nachdem bizarre Formen immer wissen in dem Moment hier dass der GT 4 ist nur wenn Teilliste GTB so und diese 4 kommt hier unten aus grob muss raus das heißt das was in dem Moment was wegen Vobis 1. immer 0 7 steht das ist die und genau dieser Vorgang ist der so genannte euklidische Algorithmus denn vom
meist salzen im das kann man wirklich wunderbares Algorithmus angeben also sein A und B natürliche Zahlen größer 0 und ich hätt gern noch wieder das größer wie es das ist wieder keine wahnsinnige Einschränkung der Linie warten 2 Zahlen die sehr die größere als an die kleine spielen wenn die niemand 2 gleiche Zahlen gibt es das weiß ich wirklich nur Algorithmus an sondern sagen gleich dass der die die Teaser also können wir größer wie das setzen so und dann geht folgen den Algorithmus ich nenn das mal zu zeigen schreibt das man sind Funktion auf also Sie haben eine Funktion die heißt Euklid von ABI jetzt Funktion im Sinne von programmieren und nicht von Malte der ist Euklid von hat und zwar 2 Eingabeparameter nämlich die 2. Zahl a und b und was macht sie jetzt am 1. die Abbruchbedingung dann gesagt wenn das P 9 ist dann in dem Moment wo B 0 steht dann steht dem Adel also dann soll die Funktion des zurückliefern denn dass die Abbruchbedingung die Moment wo das Bier 0 ist das DDT stehen und wenn es wenig Neues dann muss das muss die Funktion einen weiteren Reduktionsschritte machen dann muss die Stadt den GT von A und B auszurechnen DDT von B und A Modulo B ausrechnen also im anderen Fall dann definiert sich durch sich selber also da wie geht von A und B ist der GT von B und modulo Billionen ja und das ist schon alles wie gesagt effizienter schöner kurzer Algorithmus in 3 Zeilen Programmierer und jetzt genau das um was wir gerade Lemma hatten also die Abbruchbedingung aus dem Teil B ist die 1. Zeile und der Schritt zur Reduktion ist die 2. zeigen so was jetzt dasteht ist noch keine mathematische Satz in seiner und des und der Algorithmus was macht der die Behauptung die hier steht ist und das ist ein
Algorithmus eine sehr relevante Eigenschaft terminiert nach endlich vielen Schritten wenn man Algorythmus hat ist das eine Eigenschaft die man sehr gern hat was anderes an da andernfalls ist das Warten zu aufwendig das das ist erst dann typische Aussage eines Satzes die der Informatik Lydia und die man auch in Informatik beweisen muss also weil ich meinte man hat doch den Formate mit beweisen zu tun weil sie diese Sorte haben sie das oft wenn sie Wahlbüros haben interessiert ein damit der Meinung unter dem Arsen wird immer noch gern dass er tut was er soll also die Behauptung ist der terminiert und liefert Ihnen den GGT von A und B in Wien das ist die Behauptung von dem Salz und ich denk ich hab ihn schon motiviert das ist das tut er unsere Seele wie sie ist dass dieses Lemma von gerade eben aber wenn man das gleich nochmal ausführlich als beweist aber erstmal normalen vor sich so ich wird dann werden wir die 2. Hälfte einsteigen und die 2. Hälfte startet mit den angekündigten Beweise Umsatz 1 also ich will Ihnen zeigen dass der Algorithmus terminiert und das das Ergebnis der GGT herauskommt dass das Ergebnis der Gegend herauskommt ist viele folgen so gesehen habe im Wesentlichen das Lemma 2 1 8 und das sehr terminiert ist auch echt ist auch nicht schwer zu sehen das liegt im Wesentlichen daran dass sie das Problem bei jedem Teilschritt also wir jedes Mal wenn sie den Anteil von über 2 1 8 anwenden wirklich echt reduzieren wird die Zahl wenn ich kleiner und damit muss halt werden dann zwangsläufig 0 sein also ich werde das aber ich probiers mal so egal was sie als A und B am Anfang haben sie haben immer wenn Sie sich jetzt Modulor B angucken und er wurde B ist ja nach wenn sie dem deutlich wider dass Daten das nächste B ein dass diese Zahl gut ist zum einen immer positiv also größer gleich 0 aber aber sie ist zum anderen echt kleiner als B wir haben oder B seien es sei denn als wie ja neben der Megabit B-Mode bes auch 0 aber bekannt wie sein sie war höchstens B -minus 1 das heißt sie haben in jedem Schritt verringert sich B immer mindestens um 1 im Normalfall siehe Beispiel oben verringert sich das P deutlich wie schnell Arbeit garantiert verminderte sich um 1 mindestens ja und das heißt also das 2. Argument von dem Euklid und es in jeden Schritt würden jeden Schritt ich Kleidern und zwar wir wissen es nicht und wie viel aber mal mindestens um 1 in jeden Schritt und nein das heißt auf die Weise wie wir jetzt eine sehr sehr grobe Abschätzung nach oben länger als billig Schritte wird der Algorithmus nicht brauchen wir
geht es hier um mindestens 1 runter also das ist jetzt wir sehr sehr grobe Abschätzung aber spätestens nach B Schritten sind sie fertig und geh t also das ist jetzt wirklich nur beweist das das Ding terminiert wenn man sich jetzt wenn man sich jetzt Gedanken drum machen will wie schnell das geht dann geht das deutlich schneller als noch bestritten ja da kann man dann auch der ganze ist kann man sich die sehr ausführlich Gedanken drum machen wie lange dauert das allerhöchstens im schlimmsten Fall unter welchen Zahlen passiert das uns oder gibt für interessante Theorie wie für Bevc alles nicht mit belasten wichtig ist dass den terminiert und was wir erst noch sehen müssen ist das heißt Ergebnisse wirklich der GGT herauskommt und um das zu formalisieren wenn ich mal nur sehr am Anfang A und B und dieses dass sie am Anfang kriegen wir nicht mal an 0 und das B das sie am Anfang rein kriegen ja nicht mal die 0 und dann macht man ja stellt man inhaltlich Algorithmus rein und dann haben als nächstes in genetischen Algorithmus B und am Morgen Moby und diese Argumente des Enten Aufrufs den wenn ich mal ein und n also a n g e n sind die Argumente von Euklid beim enden aufrufen nur diese dieser Algorithmus ist ja rekursiv nur als wenn sie mit ABE aufrufen dann wird danach noch mal wieder mit ihren Arm oder B aufgerufen und so weiter und das mache also dieses Diesel und wenn Sie das 1. Mal die Schleife geben ich das A 1 B 1 und so weiter so wird sagte er in Algorithmus wenn irgendwann mal n gleich 0 ist dann hören wir auf gleich 0 ist da liefern wir das aktuelle n zurück was bedeutet dass das PIN 0 es was ist das PIN wo kommt das her nein US wenn Sie das PIN ist der 2. 2. Argument von werden Aufruf das ist das A 1 -minus 1 modulo N -minus 1 also A 1 -minus 1 modulo B -minus 1 das ist genau das DIN und das ist im Moment 0 also haben Sie das 1 -minus 1 das SP 1 -minus 1 in dem Fall am -minus 1 teilt das ist das der Fall Beispiel gesehen haben in dem Moment wo das Bier 0 wird unten haben Sie Zeile drüber dass das wir das er teilt und dann kennen Sie den GT ja das ist das Lemma 1 8. Vitali verdienen jetzt das der GGT von BNR von A 1 -minus 1 also von A 1 -minus 1 und B 1 -minus 1 den kennen Sie jetzt 1. -minus 1 das ist das A 1 und A 1 genau das
was der Euklid zurückliefert wenn Sie dann werden nur wie wird Ihnen das in der in dem der läuft immer weiter so lang bis ohne so das aktuelle lieferte ihn zurück zwar jetzt werden wir das 1 8 an was sagt ein sagt aber in jedem Euklid wird ändert sich das der GGT nicht also das hier ist das gleiche wie der GGT von A 1 -minus 2 und der N -minus 2 weil immer wenn sie nur reinstecken ändert sich der GGT nicht dass es immer 2 8 1 2 1 8 an wann so können sie weitermachen bei beschwert Ende der sich nicht also ist das das Gleiche wie der GGT von anderen bin 0 und das ist der GGT von A und B so wenn sie jetzt da die ganze es einmal im werdend im All ende wird Schlange laufen dann kommen so von DDT von ABS Euklid von wie gesagt die Hauptarbeit liegt in dem mal 2 1 8 wir den hatte man schon gesehen wie der Hase Halle 1 zur den wieder Mehr dieser Euklidischer Algorithmus liefert Ihnen GT und ich will ihre ihre Insel an ihre Talente im durchdringen von rekursiven Algorithmen noch ein bisschen weiter denn und ihnen zeigen diese über diesen Algorithmus können wir noch ganz spannend freigibt noch erweitern und können da noch viel viel mehr Informationen rausziehen und das was jetzt kommt ist der sogenannte erweiterte euklidische Algorithmus und wer sieht das freilich 1. mal Algorithmus sehen und dann überlegen wir uns was der tut und ich sage ich bin gleich den Satz und sagen was er tut und dann Regenwand und was das bringt man so kann also die gleiche Ausgangssituation war natürlich Algorithmus ist der erweiterte Euklidischer Algorithmus also der enthält insbesondere das von gerade eben wenn er es sieht ist auch wieder eine rekursive Aufruf Strukturen so also gleiche Situation sie haben 2 natürliche
Zahlen a und b beide bitte nicht nur und das ist größer als das bin können die klären ab euklidischen Algorithmus bestimmen das mehrmals auch auch aber noch ein bisschen mehr Information mit zwar .punkt also
das der Algorithmus jetzt hat es in der erweiterte Euklid ich nenne denn mal neben erhofft Euklid erweitert Euklid der Dekret als Argument wieder das A und das B 3 4 also ich eben diesen Algorithmus A und B und was wir jetzt nach der Spruch die nicht nur den GGT aus Innsbruck denn auch aus so der Buch die noch 2 weitere Zahlen aus zwar und zwar 1. Reisen sind in der Abbruchbedingung also das bis 0 dann wissen wir dass geht der GGT steht jetzt im aber und was sie in dem Moment ausspucken ist das Triple A 1 zu 0 können Sie sagen super Algorithmus tut nicht nur zu dem an Wochen vorher die ich vorher klar bestimmt das 1 zu 0 aus wo zu Ehren sehen Sie gleich mit dem 1 zu 0 wird es mich rückwärts los gerechnet also was macht der Algorithmus wenn er denn das bin ich nun ist und dann bestimmter 3 Zahlen die XY und die bestimmte indem er sich wieder selber aufruft an nämlich genauso wie vorher B und am und B um also ich Mitglied des ist die gleiche ziert Validity von A und B und sie bestimmen dem den GGT von DNA wurde Lorbeer bestimmen mir 610 haben also das geht denn hieraus ergibt denn das ist die das wird verloren und die hinten in der letzten es passiert einiges der rechnen Sie X -minus den ganzzahligen Quotienten von aber ich bin mal 10 an so und das was lohnen wenn Sie jetzt mal nur die 1. Koordinaten von diesem Trip sich anschauen dann stellen Sie fest in der 1. im 1. Eintrag da passierte ganz normaler kritischer geworden das Kombi und A 1 Berlin und ist dann dem war zurück wenn ich den rauchen werden dann rufen wir den Algorithmus wieder auf mit Bier oder aber nur B und das war es so und das ist jetzt dieses y und das X 10 das Bauhaus sage ich Ihnen was es tut oder nicht und dann wenn wir danach sehen warum das wertvolle Informationen sind also erstens ist wieder der terminiert nach endlich vielen Schritten hin und was sind diese 3 Zahlen die ausspuckt am Ende spuckt der 3 Zahlen die K und L aus der K und allen spuckte aus und was das des ist wissen wir schon oberstes des ist das 1.
GGT von A und B in zwar und außerdem sind es kam das L das des Kaders Elsen 2 Zahlen die folgende Gleichung erfüllen also der GGT von A und B des des ist K aber bloß Elmar gehen also dies kann dass er Wasser noch ausspuckt sind 2 ganze Zahlen aus denen sie mit A und B sich 16 GGT kombinieren können auf diese Weise das ist immer selbstverständlich dass das immer geht das eine besondere Eigenschaft des WGT dass sie denn immer als so eine Kombination aus Abi schreiben können sind seine dabei ist dass kann er ganz ehrlich sein müssen wir wir hier kann ich Berichte zu zulassen so kein Problem jede Zahl so darzustellen aber er mit ganzzahligen KDL ist es nicht ganz so banal er nun und ich will ihn dann wenn man mir war ein Beispiel für einen wirklich mal durchgerechnet haben auch erklären warum das so toll ist dass man den GGT so so kombinieren kann und in der nächsten Vorlesung aber dann sehen dass das sogar ganz eine ganz fundamentale Grundlage dessen ist was sie wahrscheinlich alle kennen wenn ich von er Key Kryptographie funktioniert nicht oder erweitert gut ich will ihn das Ding nicht beweisen darin den wirklich gewesen das hier ist mühsamer und das lass mal bleiben dass das Ding terminiert dass das geht der GGT ist das können sind was Beweis von 1 9 abgeben und das andere der es mit dem Kardinäle und so weiter das ist mir relativ ausführliche Induktion nach der Anzahl der Aufrufe von dem das sowie auf den sich selbst noch mal Aufruf danach müsse zu machen aber das macht keinen Spaß ich will ihn lieber ausführlich einmal Beispiel vorrechnen von dem den ich hab den Algorithmus noch auf die Folie gepackt wenn jetzt hier so langsam und sicher nach oben verschwindet also auch andere seine Gebiet die jetzt Folie wechselnder liegt noch ne 2. dann eben so ich will ihn gut ich habe 2 ist wie gesagt ich schreibe mal schnell 2 vorhin und zwar eine direkte Folgerung ich bin im Prinzip nur Spezialfall von dem was da oben steht hinschreiben die aber sehr sehr wichtig ist wird der Zahlentheorie für Dinge die wir weitermachen wollen und zur Situation gibt es häufiger das den großen Satz haben der was ihnen was tolles liefert und davon Spezialfall oder irgendeine wenn Sie diesen Satz haben dann fällt ihnen irgendwas anderes direkt als Geschenk vor die Füße und so ein Geschenk wenn wir Mathematiker auch ein Geschenk allerdings auf Lateinisch und das ist das sogenannte Cola also wenn Sie da irgendwo an sehen dass da nicht satt sondern Corolla steht dann heißt das dass sie das meistens nach dem großen Satz und ist ein Geschenk hätte man auf diesem großen Satz sofort ziehen kann und was ich machen will ist schauen sich den Fall an das sie 2 wieder 2 ganze Zahlen haben größer 0 aber jetzt wissen sie schon vorher diesen teilerfremd oder anders gesagt der GGT S 1 nun quasi am 2. Tage die GT 1 und dann sagt uns
dieser euklidische Algorithmus unabhängig von einem algorithmischen der Kredit Algorithmus ist den sie gerade noch um auf der Flucht denn es sagt sie könnten die Gateway sie kriegen wir zahlen K und L dass sie den DDT kombinieren können als K A +plus LB also es gibt K und L auszählt so dass sie Kanal an +plus Elmar B gleich 1 haben wenn Sie Zweiteiler fremde Zahlen haben heißt es immer sie finden die ganzzahlige Kombination von den beiden die ein diese sogenannt diese Gleichung geht es dann im Zelt lösbar und das ist mehr als ist Cola light dieser weiter deutlich Algorithmus liefert Ihnen die Lösbarkeit dieser gleich und wie gesagt die Lustbarkeit der Gleichung denn er ist banal das entscheidende ist die Lustbarkeiten Z sie finden immer ganze Zahl diese Gleichung lösen so jetzt aber Beispiele für den erweiterten Euklid so was muss man
machen ich nehme an mal als Zahlen mitgebracht als 141 und die neuen denn sie natürliche mit bloßem Auge nicht Milizionäre ich Beispiele mit siebenstelligen Zahlen vorrechnen 141 ist nach Quersummen Test durch 3 teilbar aber nicht durch neue also wird wohl 3 rauskommt dank Quersumme 6 es ist der GGT wohl 3 aber es geht vor allem darum einmal diesen bei Algorithmus zu sehen und zu sehen was dieses K und L eigentlich tut also was machen euklidischen Algorithmus wir schreiben uns wie vorhin auch und den kann im Prinzip bringen wird erst mal ganz normal euklidischen Algorithmus durch also ich denn jetzt ganz stupide wie das der Rechner auch tun würde wo was schon wissen dass es 3 ist in die DTM das einzige was wir machen wenn man sich in den Algorithmus reinschauen was wir brauchen ist dieser Quotient a durch b der also neben der protokollieren damit was war der ganzzahlige Quotient von durch B so also was passiert das was passiert dann über 141 ganzzahlig durch 9 teilen im pur man mal 10 bis 90 dann kriegen auf 45 dazu 5 Zimmer 9 ist also 135 bleiben 6 übrig also das 101 wird sich durch 9 bis 15 West 6 also haben wir einmal Euklid bei mir das B hierüber und da kommt das Modul nur welche 6 also es genau wie vorhin die neuen rüberschieben hier modulo rechnen und das Ergebnis darunter stehen so sein sie was es eben gemacht haben es der muss diese 15 noch gemerkt weil die später brauchen nächste Schritt vom Euklid sie rechne 9 geteilt durch 6 in ganzzahlige Arithmetik Mal geteilt durch 6. 1 bis 3 also rutschte sexy rüber und hier steht der Rest 6 halte ich fest durch 3 ist 2 ist nur so und in dem Moment terminiert werden jetzt deutlicher Algorithmus Nummer und liefert Ihnen hier den DDT nämlich 3 in den Druck das ist das was von dem die ganze Zeit gemacht haben so dass man gucken was macht dieses Ding hier noch mehr jedes Mal wenn sie dabei der Euklid aufgerufen hat selbst ist das was rauskommt in diesen Variablen die XY ein und geht dann dieses Treppe daraus das macht aber da also müssen sie denn es geht immer weiter die 3 mit ABl sagen haben Sie nicht den Fall wir gleich 0 dann gehen Sie diese 1. Zeile von mir von der Bedienung und kriegen dass sie wieder den erweiterbar reingehen also den sie da er weiter bei Kiel 3 dann wieder nicht begleichen und die wir da rein kommen so der Kosovaren haben dann irgendwann 7 Mal aufgerufen und jetzt wird es im 7. auf das ist nämlich 0 also dem Fall 7. sondern im 1 2 3 4. 90 P 0 dann klappt also endlich aus der bei der Euklid A 1 0 raus also 3 1 0 und dann geht es jetzt im Nachklapp dieser Rechnung die und mit den Rittern steht los also der 4. erweiterte der Clipart den A 1 0 raus das hat in der 3. erweiterte Euklid aha 9 0 1 minus also ich bin mal nur raus wie wir das in den 2. und der 2. rechnet wieder diese Rechnung 1. rechnet sie wieder an den Fluss kommt was raus aber genau das machen wir jetzt auch also der innerste erweiterte Euklid er dessen rekursive Programmstruktur damit haben Sie auch wenn sie noch viel Spaß haben werden der innerste erweiterte Euklid also ich sie rufen auf für wieder aufzuholen wieder aufsuchen wieder bei mir immer aufgerufen unser Beispiel und der innerste schnappt uns aus 3 1 0 also Innersten aber diese 3 und der innerste Struktur dann hier eine 1 zu 1 0 aus jetzt kommt der Next also deutlich der 3. Euklid der sagt jetzt des XY ist immer noch das gleiche wie vorher also die 3 und für das X und Y liefert er jetzt das wird von X also ich eben das sind wir das ist das X das wird sich schien das y hierüber und an die Stelle von y setzen Sie diesen Ausdruck X -minus Der Quotient man also an diese Stelle hier an dieser Stelle vom vom L kommt jetzt der Ausdruck X von der Zeile drunter -minus Quotient man y von der Zeile drunter das ist 1 also dass diese ein Ziel um farbig also diese 1 kommt können was kommt da -minus Min -minus der Quotient der aktuelle Quotient der ist weil das ist ja hier also diese 2 wandert hin mal das y von davor dass selbst Land von der Vorwahl 0 1 also dieses selbst an bei der 10. ja
das ist diese Rechnung wird x -minus Prozent wird ab das macht der 3. der 3. in die Schachtel Kigali verliert seine gegen seinen 2. und der 2. machte genau das gleiche als wenn wir das 1. mal aus was aber da jetzt 1 -minus 2 0 das ist 1 zur jetzt nach der nächste eigentlich genau das gleiche diese 1 welche um schon das einfache Teilen und hier kommt wieder diese Rechnung also wenn ihm das von schräg links drunter nur dass der grüne Pfeil -minus jetzt kommt der blaue Pfeil den Quotienten 1 und dann kommt der rote Pfeil mal das was drunter steht das war ihr 1 also wir kriegen Sie -minus 1 noch mal die gleiche rechnet kommt äußerste Euklid der zuerst aufgerufene der schnappt sich viel ist nix y nach dieser Rechnung also was macht es geht zum einen die -minus 1 hierüber und zum anderen kommt jetzt wieder erst grün dann blau oder rot also die Einziehung rochen -minus Der Quotient mal das was drunter steht 1 -minus 15 bei -minus 1 ist 1 plus 15 bis 16 so Meister geht jetzt ausspuckt es es 3 klar ist -minus 1 und er ist 16 ist nur schnappen sie sich zweimal 3 der zweimal 2 Zahlen rechne sich selber noch mal durch der aber sie kriegen auf die Weise jetzt diese 3 Zahlen sieht in den elitären sie kriegen dieses K und L und ich habe ihm gesagt dieses K und L sind nicht irgendwelche Zahlen die auszurechnen sogar die Dame ganz besondere Eigenschaft nämlich kam mal a +plus etwa Stgt der GGT Ringen war das stimmt also was es kam mal a +plus Mrd K ist -minus 1 a ist 141 er ist 16 und wie es im neuen so bisschen Kopfrechnen üben was es 16 Mal wollen 16 mal 10. 160 16 mal 9 also 16 weniger also 144 also haben wir -minus 141 +plus 144 bis 3 und das ist der GGT von 109 41 um ein tanken das ist kein Zufall sondern so ist der der arbeitet Euklid gemacht und erweiterte Euklid also ist genau deswegen wertvoll weil diese Zahl liefert und wir werden jetzt lachte da die wir den nächsten also sehen warum das so wertvoll ist haben aber mein Aufruf ist denken Sie sich 2 Zahlen aus die nicht allzu groß sind und rechnen Sie den erweitert neue Klima selber durch und prüfen Sie nach das hinterher auch das rauskommt was rauskommen soll und dann werden Sie sehen dass geht mag ich immer auf so ich hab noch ein Beispiel oder eher noch 2 Beispiele dabei für kreative Anwendung des erweiterten Euklid wo man schon sieht was man mit dem Ding anstellen kann wie zwar 3 sowas gar mit dem Ding anstellen wir hatten freuen und ist noch ein Beispiel der hatten vorhin gesehen werden erwartete Euklid funktioniert natürlich auch sehr geliebt wie einst das will ich jetzt wieder den Spezialfall machen also wir haben 2 Zahlen a und in wieder nicht nur mit sehr ungewissen schauen aus irgendeiner Quelle dass der GGT von A und N 1 nur also wenn sie an kryptografische Anwendung denken in diese Primzahl dann es relativ leicht sicherzustellen dass der GGT von an in 1 haben so und was jetzt gesucht ist und das ist eben eine ganz häufige Problematik wenn Sie die Kryptographie gehen sie suchen der ganzen Zahl z so dass da mal X kongruent 1 modulo man schon also suchen wenn Sie so wollen was ist dieses X dieses existe Zahl die wenn sie mit aber die beziehen eines geht Module in das X ist sowas wie einst durch Aachen nur über 4 x im Kopf eines durch ein Schreiben steht aber einzig als einzeln das heißt wenn sie in der Module rechnen teilen wollen das können wir bisher nicht einsehen oder sich mitteilen wollen dann ist es ganz entscheidend diese Gleichung lösen zu können wenn Sie diese Gleichung lösen können dann haben sie das einst durch Arten können sie durch a teilen also überhaupt keine Probleme werden also in den Zuschreibungen aber das nicht geht ja also wenn 6 ist ein A 3 dann können sie so lange suchen wie sie wollen dann gibt es kein x so dass Arbeit es dreimal X 1 ist ISS-Module 6. wirklich funktioniert aber die Behauptung ist wann immer und die GT 1 haben geht das und es geht es geht mit den aber dabei tätig Lage Rhythmus es geht nicht nur immer sondern Sie können so explizit ausrechnen im wer
schmeißen Sie mal die beiden Zahlen a und n in den erweiterten Euklid dann spuckt in der Weite der EU die die 3 zu 3 Zahlen aus also ich nehme die Zahlen a und n und stecken den erweiterten Euklid Mehr was passiert jetzt Na was das des ist es keine Überraschung dass die wird wohl als 1 rauskommen die DDT von an 1 1 also kommt das die als 1 raus aber wir kriegen noch 1 ist Kama +plus mit den Kassen 11 dieser etwa bei der Clip ausspuckt so ist wenn sie die Gleichungen oder n also kriegen Sie was 1 CI-Modul un 1 modulo wieder 1 als Modelo in ist das selbe wie kam mal enden +plus L mal an modulo enden es ist wieder das Schöne kam eines durch N teilbar das 1. Kammer in oder 1 0 es bleibt also nur übrig modulo enden so sammelst immer aber oder 1 1 es ist das 6. nun kann er also jetzt das L ersetzen es gleich L und haben ihre Gleichung gelöst und er mir 1 durch a gefunden zum auf die Weise ist in der erweiterte Euklid geben in im Endeffekt zuteil wir können von einem Beispiel in zahlreichen ganz konkreten Zahlenbeispiel machen was Sie suchen es
Zahl dass 93 mal x 1 ist Mono 100 also suchen Zahl ist mit 93 multiplizieren müssen so dass die 2 letzten stellen 1 zu 0 1 sind sieht man es sich so vor dass man dem Moos würden wie 25 Tausend fordert 1 rauskommen oder so was also wenn 100 heiße genauso schauen sich die 2 letzten Ziffern so also wir können wir das lösen mit der Methode von gerade eben sie stellten 100 und 93 einen erweiterten Euklid also die ihn in den erweiterten Euklid mit 100 und 93 rein denn wenn ich ihn jetzt nicht vor dem dürfen Sie gern mal rechnen was dabei herauskommt ist die GTS 1 nicht verblüffend wenn sie 100 und 93 ankommt Truppen auf und des Fechten Stapel 2 und findet halber und sonst durch nicht viel und das klappt bei 3 90 nicht das ist glaub ich so eine Primzahl bin ich sicher ist es nicht durch 3 Jahre danke man sollte denken bevor man Mansarde Gott also 3 der war aber eben hat mit Millionen keine gemeinsam Teilers kommt 1 raus und dann kriegen Sie noch für K und L kriegen sie 40 und -minus 43 also mit der Überlegung von gerade eben dass er lässt das X setzen sie X gleich -minus 43 genauer gesagt nicht -minus 43 soll -minus 43 Molo 100 und dann na was ist -minus 43 nur 100 minus 43 Modell ohne dass 57 dabei 57 43 100 ist er und damit kriegen sie tatsächlich 57 mal 93 das kann man jetzt meinen Taschenrechner hauen zum kontrollieren und das ist 5 Tausend 300 1 also tatsächlich ein Smolow .punkt auf die Weise mit dem Reisepaket können Sie also solche die Gleichungen ohne Rechnung lösen und wie gesagt das ist nicht die gleichen die sie lösen sondern das ist die Gleichung denn sagten sie dividieren zusammen ich ich ließ das den Abstimmende Übungsaufgabe 1 15 1 der können Sie mal ein bisschen sich probieren unter Euklid theoretisch anwenden die Behauptung es wenn Sie 2 natürliche Zahlen haben die bitte schön alle nicht 0 sein Abi und n und sie wissen wie in dem Beispiel oben der GGT von A und in 1 also dem keinen gemeinsamen Teiler aus 1 bei dann wird folgende Reduktion wenn das ändern das Produkt von A und B teilt und ändert keine gemeinsamen Teiler führt an denn es ist naheliegend aber nicht ganz banal zu zeigen dass das schon das Bett halten also wenn der der GT von an der nur Sonnental das Produkt dann Talent schon das bin ich da können Sie mal das was probieren so und ich mir zum nächsten Abschnitt übergehen der uns jetzt weiterführt in dieser Arithmetik von 1. unsere kleinen Ausflug darstellt das was immer damit die Zahlentheorie heißt der ganz erst der Anfang was also drum geht und da Tabak Heilslehre und die Frage wann teilen irgendwelche komplizierten Ausdrücke andere Primzahl und so weiter und ich will Ihnen einen Satz aus der Zahlentheorie zeigen der mit dem was er macht viel zusammenhängt und der dann hinterher der ganz entscheidend ist neben dem des ist 2. wesentliche mathematische in Zutat zu Papier KI Kryptographie ist neben dem erweitert euklidischer gerückt also Appetit Fotografie zu verstehen müssen dabei deutlicher grob muss kennen wir müssen Sie den Satz der jetzt kommt den kleinen Satz von Fermat kennen und dann kann man kann man erklären wie das funktioniert also der
kleine Satz von Firma man den Namen Firma man wahrscheinlich die meist schon mal gehört außerhalb der Mathematik berühmt für seine großen Satz der seit 10 Jahren bewiesen ist unter vor 450 Jahren Leute wahnsinnig gemacht hat und der kleine den von der da gibt es aber einen verwirrten Beweis von Firma der da war der da war der Rand des Buchs wahrscheinlich breit genug also was sagt der kleine Satz von Fermat und wenn Sie hier eine Primzahl P nehmen und der natürliche Zahl Mersenne-Primzahl vielen natürliche Zahl a dann und dann schauen Sie sich aber eh er auch per die ziemlich groß sein seien ich P große Primzahlen und eine große Zahl ist auch per verdammt groß aber es interessiert sie nicht was auch PS soll es interessiert sie nur was auch per Modulo P und der kleine Satz von Fermat sagt was was an was P da kommt immer aus wenn man so können das ist erst mal unklar warum und es sei unklar wofür das gut ist unseres gutes Zeichen am Dienstag warum das so ist würd ich ihn wohl auch erst am Dienstag zeigen können weil den Beweis der ist nicht lang aber in 2 Minuten quält in den jetzt auch nicht werden aber wichtig ist eben dem was der kleine Firma macht ist der reduziert ihn das Problem der Modelo Rechnung mal wieder also Sie haben die komplizierte große Zahl auch P wenn Sie die Mode P konnte war es das kriegen sie nicht direkt aus den bisherigen Rechenregeln für die Modellrechnung Rechnung ja also wenn Sie da probieren natürlich können Sie auch Penelope ausdrücken als aber noch auch P aber dann sind sie genauso schlau wie vorher ja also das da steckt mehr dahinter als einfach Rechenregeln von Modewoche gut ich sie haben ich hätte nicht davon sagen sollen dass ich das jetzt nicht mehr lass ich mir diese Verse aus noch auf Wiedersehen sagen wo für die Aufmerksamkeit danken und schönes Wochenende wünschen bis Dienstag
Negative Zahl
Mathematik
Summand
Momentenproblem
Quotient
Platte
Zahl
Ecke
Faktorisierung
Exponent
Biprodukt
Gleichung
Zahl
Monster-Gruppe
Faktorisierung
Momentenproblem
Exponent
Zahl
Moden
Positive Zahl
Zusammenhang <Mathematik>
Größter gemeinsamer Teiler
Natürliche Zahl
Rekursion
Berechnung
Gleichung
Euklidischer Algorithmus
Teilbarkeit
Zahl
Gradient
Physiker
Momentenproblem
Größter gemeinsamer Teiler
Quotient
Zahl
Division
Numerisches Modell
Summe
Gewichtete Summe
Menge
Größter gemeinsamer Teiler
Quotient
Betafunktion
Welle
Division
Zahl
Kreis
Rechenbuch
Homogenes Polynom
Momentenproblem
Größter gemeinsamer Teiler
Ganze Zahl
Euklidischer Algorithmus
Zahl
Momentenproblem
Theorem
Natürliche Zahl
Abschätzung
EUKLID <Programm>
Euclides
Zahl
Linie
Parametersystem
Elementare Zahlentheorie
Momentenproblem
Abschätzung
EUKLID <Programm>
Struktur <Mathematik>
Euklidischer Algorithmus
Euclides
Zahl
Momentenproblem
Quotient
EUKLID <Programm>
Euclides
Euklidischer Algorithmus
Koordinaten
Zahl
Lösung <Mathematik>
Zahlentheorie
Ganze Zahl
Mathematiker
EUKLID <Programm>
Gleichung
Euklidischer Algorithmus
Gebiet <Mathematik>
Zahl
Momentenproblem
Primzahl
Kopfrechnen
Quotient
Extrempunkt
Arithmetik
Gleichung
Euklidischer Algorithmus
Zahl
Variable
Rechenbuch
Ganze Zahl
EUKLID <Programm>
Gleichungssystem
EUKLID <Programm>
Gleichung
Zahl
Mathematische Größe
Ziffer
Abstimmung <Frequenz>
Mathematik
Zahlentheorie
Primzahl
Natürliche Zahl
Arithmetik
Gleichungssystem
Gleichung
Zahl
Ausdruck <Logik>
EUKLID <Programm>
Numerisches Modell

Metadaten

Formale Metadaten

Titel Euklid
Serientitel Mathematik I für Informatik und Wirtschaftsinformatik
Teil 05
Anzahl der Teile 29
Autor Haller-Dintelmann, Robert
Lizenz CC-Namensnennung - keine kommerzielle Nutzung - Weitergabe unter gleichen Bedingungen 3.0 Deutschland:
Sie dürfen das Werk bzw. den Inhalt zu jedem legalen und nicht-kommerziellen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen und das Werk bzw. diesen Inhalt auch in veränderter Form nur unter den Bedingungen dieser Lizenz weitergeben.
DOI 10.5446/33612
Herausgeber Technische Universität Darmstadt
Erscheinungsjahr 2011
Sprache Deutsch

Inhaltliche Metadaten

Fachgebiet Mathematik

Ähnliche Filme

Loading...
Feedback