Der Satz von Euler
Christian Spannagel
https://www.youtube.com/watch?v=DU082wcr40A

Transkript (automatisch erstellt)

0:06 jetzt können wir auch gleich den entscheidenden Satz formulieren den Satz von
0:20 eer der Satz von Euler besagt t zweier Zahlen = 1
0:35 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
0:49 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
1:09 ist a hoch der Anzahl der zu m Teiler fremden zahlen also a hoch V von M kongruent 1 Modul
1:18 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
1:26 Beweis Beweis Voraussetzung ist erstmal es gelte GGT von A und
1:40 M ist GLE 1 also a und m sind Teiler fremd so F von M gibt uns die Anzahl der zu M
2:00 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
2:09 Zahlen zu m Teiler fremd fremde [Applaus] Zahlen aus zm weil wir betrachten nur die Zahlen jetzt modulo m gerechnet wir
2:24 rechnen immer Mod m die kann ich mal bezeichnen als K1 K2 bis
2:43 km ma wir gleich mal hier ein Beispiel nebenend dran nehmen wir mal 8 also wir haben M = 8 als
2:54 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
3:07 1 3 5 und 7 so ne Entschuldigung hier ein bisschen schreiben F von M es gibt F von M dieser Zahlen aus
3:21 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
3:34 [Musik] K und jetzt mache ich mal das folgende ich
3:43 multipliziere das ganze mal mit a BDE also AK K1 AK K2 bis A K F von M
4:00 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
4:11 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
4:24 sind no die Produkte Teiler fremd das heißt daraus kann ich folgern [Musik] GGT von A K und M ist auch gleich
4:39 1 so machen wir mal ein Beispiel ähm wir haben ja diese vier Zahlen wir
4:52 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
5:03 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
5:14 multipliziert gibt 3 diese hier mit 3 multipliziert 3 x 3 gibt 9 das ist 1 mod 8 5* 3
5:27 15 15 modo 8 ist dasselbe wie -1 modulo 8 und -1 dasselbe wie 7 7* 3 21 21 ist kongruent 5 Mod
5:46 8 aha was fällt auf ich habe alle Zahlen aus dem Bereich zwischen 1 und 8 genommen sind die
5:57 Teiler fremd sind zu 8 und habe alle mit derselben weiteren teilerfffenzahl multipliziert was fällt
6:10 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
6:30 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
6:39 kann noch was feststellen bitte ja ja keine ne Restklassen genau es
6:48 entstehen keine neuen Restklassen und es werden auch keine zwei Elemente auf dieselben Restklassen abgebildet es ist eine Permutation kommt da raus ich nehme
6:58 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
7:07 Elemente kommen wieder raus nur als unterschiedlichen Reihenfolgen ja das heißt wenn ich die a wenn ich a an alle KS ran multipliziere
7:17 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
7:29 muss gelten ai ist ungleich Quatsch ai nein a mal K ist A*
7:41 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
7:53 ungleich a mal KJ es kann nicht beides mal dieselbe Zahl rauskommen warum angenommen Aki wäre kongruent
8:07 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
8:22 dann darf ich beide Seiten durch dieselbe Zahl dividieren und dann würde da stehen aki ist Quatsch würde da stehen KI ist
8:33 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
8:43 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
8:56 die sind natürlich nicht identisch ja das heißt dann müssen auch diese beiden Zahlen unterschiedlich sein wenn ich sie mit a
9:06 multipliziere also Aki kann nicht kongruent sein zu
9:14 AKJ die Produkte sind auch alle unterschiedlich das heißt diese AK i sind exakt die ursprünglichen KI nur in der
9:25 unterschiedlichen Reihenfolge das ist eine bijektive Abbildung eine Permutation eine Menge auf sich
9:32 selbst das heißt ich kann jetzt aber auch das folgende machen ich kann K1 mal k2* K3 mal und so weiter mal
9:46 K4 von M miteinander multiplizieren ich multipliziere einfach mal alle diese teilerfremden Zahlen alle diese zu m teilerfemden Zahlen
9:58 miteinander das ist ja dann das gleiche als würde ich alle Akis miteinander
10:06 [Musik] multiplizieren die KIS und die Akis bilden ja jeweils dieselbe
10:25 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
10:35 heißt die sind kongruent modulom so jetzt kann ich noch das folgende
10:55 machen ich kann jetzt jede dieser beiden Seiten durch K1 dividieren durch K2 dividieren durch K3 dividieren weil die KI ja alle
11:06 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
11:15 alle KIS rausstreichen dann steht hier links 1 und rechts steht a mal A* a mal a mal a wie
11:27 oft f von M [Musik]
11:42 mal so Quad errad demonstrandum [Musik] ja super gell
12:05 okay bis nächste Woche