Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Der Satz von Euler
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 57 Zeilen
- jetzt können wir auch gleich den entscheidenden Satz formulieren den Satz von
- eer der Satz von Euler besagt t zweier Zahlen = 1
- ist dann folgt das raus dass wenn ich a hoch F von M nehme ich nehme die Anzahl der zu m Teiler fremden zahlen als Exponenten
- dieser Potenz dann ist es kongruent 1 modulo m wenn Sie ein Modul haben und eine Zahl die Teiler fremd ist zu diesem m dann
- ist a hoch der Anzahl der zu m Teiler fremden zahlen also a hoch V von M kongruent 1 Modul
- m das mag hilfreich sein das ist so ein Trick den man dann solchen Kontexten anwenden können Voraussetzung ist und das machen wir jetzt in den
- Beweis Beweis Voraussetzung ist erstmal es gelte GGT von A und
- M ist GLE 1 also a und m sind Teiler fremd so F von M gibt uns die Anzahl der zu M
- fremden Zahlen an die jetzt kleiner gleich m sind das heißt wenn ich irgendein Modul habe dann kann ich die zu m Teiler fremden
- Zahlen zu m Teiler fremd fremde [Applaus] Zahlen aus zm weil wir betrachten nur die Zahlen jetzt modulo m gerechnet wir
- rechnen immer Mod m die kann ich mal bezeichnen als K1 K2 bis
- km ma wir gleich mal hier ein Beispiel nebenend dran nehmen wir mal 8 also wir haben M = 8 als
- Beispiel dann haben wir vorhin gesagt von 8 4 es gibt also zu 8 Teiler fremde Zahlen in dem Bereich zwischen 1 und 8 und das sind die Zahlen was haben wir da
- 1 3 5 und 7 so ne Entschuldigung hier ein bisschen schreiben F von M es gibt F von M dieser Zahlen aus
- zm ich nehme mir die ich nehmen gerade die Zahlen raus die Teiler fremd sind zum zu m und das sind F von m und die bezeichne ich mal als
- [Musik] K und jetzt mache ich mal das folgende ich
- multipliziere das ganze mal mit a BDE also AK K1 AK K2 bis A K F von M
- ich multipliziere all diese Zahlen all diese teilerfremden Zahlen mit einer mit dem a das ja auch Teiler fremd ist was bedeutet das nun für diese für diese
- Produkte hier AK1 ak2 AK3 und so weiter die sind auch alle Teiler fremd zu m ja das waren alles Teiler fremde Zahlen zu m die a a ist auch Teiler fremd also
- sind no die Produkte Teiler fremd das heißt daraus kann ich folgern [Musik] GGT von A K und M ist auch gleich
- 1 so machen wir mal ein Beispiel ähm wir haben ja diese vier Zahlen wir
- nehmen jetzt mal A g= 3 ja wir nehmen A = 3 ist auch Teiler fremd zu 8 jetzt multipliziere ich all diese Zahlen mit der
- 3 und ich rechne immer modulo 8 ich rechne immer in Z8 in dem Fall also rechne immer ein zm also diese teilerfemde Zahl mit 3
- multipliziert gibt 3 diese hier mit 3 multipliziert 3 x 3 gibt 9 das ist 1 mod 8 5* 3
- 15 15 modo 8 ist dasselbe wie -1 modulo 8 und -1 dasselbe wie 7 7* 3 21 21 ist kongruent 5 Mod
- 8 aha was fällt auf ich habe alle Zahlen aus dem Bereich zwischen 1 und 8 genommen sind die
- Teiler fremd sind zu 8 und habe alle mit derselben weiteren teilerfffenzahl multipliziert was fällt
- auf hallo Sie haben noch alle Augen im Kopf oder was fällt auf wie nennt man das hier was da rauskommt das ganze Ding da
- ja auch wieder Teil genau es kommt wieder nur Teiler fremde Zahlen raus hat man vol festgestellt al sind alle Teiler fremd aber es kommt noch was raus man
- kann noch was feststellen bitte ja ja keine ne Restklassen genau es
- entstehen keine neuen Restklassen und es werden auch keine zwei Elemente auf dieselben Restklassen abgebildet es ist eine Permutation kommt da raus ich nehme
- die Elemente die ich vorher hatte ah ja ne ich habe die Elemente die ich vorher hatte alle mit derselben Zahl multipliziert und exakt dieselben
- Elemente kommen wieder raus nur als unterschiedlichen Reihenfolgen ja das heißt wenn ich die a wenn ich a an alle KS ran multipliziere
- kommen wieder alle KS raus nur in unterschiedlichen Reihenfolgen es können nicht zwei gleiche KI rauskommen warum nicht kann man sich auch überlegen es
- muss gelten ai ist ungleich Quatsch ai nein a mal K ist A*
- KJ Modul m glaub wir überziehen heute ein paar Minuten bleiben sie trotzdem noch Stück ruhig wir sind gleich soweit wir sind gleich fertig a mal KI ist
- ungleich a mal KJ es kann nicht beides mal dieselbe Zahl rauskommen warum angenommen Aki wäre kongruent
- AKJ Mod m angenommen das wäre der Fall dann könnte ich hier vorne durch a teilen denn a und m sind ja Teiler fremd
- dann darf ich beide Seiten durch dieselbe Zahl dividieren und dann würde da stehen aki ist Quatsch würde da stehen KI ist
- kongruent KJ Modul M a ist Teiler frem zu m hab wir vorhin gesagt darf ich beide Seiten nicht a teilen dann wäre KI auch
- kongruent KJ modulo m aber die KS die sind ja nicht gleich ich habe doch explizit alle KS hier genommen die Teiler frem sind zu m kleiner GLE m und
- die sind natürlich nicht identisch ja das heißt dann müssen auch diese beiden Zahlen unterschiedlich sein wenn ich sie mit a
- multipliziere also Aki kann nicht kongruent sein zu
- AKJ die Produkte sind auch alle unterschiedlich das heißt diese AK i sind exakt die ursprünglichen KI nur in der
- unterschiedlichen Reihenfolge das ist eine bijektive Abbildung eine Permutation eine Menge auf sich
- selbst das heißt ich kann jetzt aber auch das folgende machen ich kann K1 mal k2* K3 mal und so weiter mal
- K4 von M miteinander multiplizieren ich multipliziere einfach mal alle diese teilerfremden Zahlen alle diese zu m teilerfemden Zahlen
- miteinander das ist ja dann das gleiche als würde ich alle Akis miteinander
- [Musik] multiplizieren die KIS und die Akis bilden ja jeweils dieselbe
- Menge auf der einen Seite multipliziere ich 1 3 x 5 x 7 auf der anderen im Beispiel multipliziere ich 3 x 1 x 7 x 5 kommt beides mal dasselbe raus das
- heißt die sind kongruent modulom so jetzt kann ich noch das folgende
- machen ich kann jetzt jede dieser beiden Seiten durch K1 dividieren durch K2 dividieren durch K3 dividieren weil die KI ja alle
- Teiler fremd sind zu m ne ich kann dar auf beiden Seiten durch K1 durch K2 durch K3 durch und so weiter durch K4 von M teilen das heißt ich kann hier
- alle KIS rausstreichen dann steht hier links 1 und rechts steht a mal A* a mal a mal a wie
- oft f von M [Musik]
- mal so Quad errad demonstrandum [Musik] ja super gell
- okay bis nächste Woche