Modulare Arithmetik - Beweis?
man soll zeigen :
wie geht man hier vor ? Induktion ??
2 Antworten
65 = 5 * 13, Euler's Phi(5)= 4, Phi(13)= 12
Satz von Euler:
x^4 = 1 mod 5 --> x^12 = 1 mod 5
x^12 = 1 mod 13
--> x^12 = 1 mod 65
--> x^36 = 1 mod 65
--> x^37 = x mod 65
Ja. Der Restklassenring modulo 65 ist isomorph zum direkten Produkt der Restklassenringe modulo 5 und modulo 13.
Nein, sondern weil beide Primzahlen x^12 - 1 teilen, also auch deren Produkt
Schau dir den kleinen fermatschen Satz für endliche Gruppen an. Wie viele Elemente hat die multiplikative Gruppe?
Eventuell muss man noch überlegen, was mit den nicht in der multiplikativen Gruppe enthaltenen Elemten ist.
Ergänzung wegen der 37: 13 im Exponenten reicht auch schon. Nach dem chinesischen Restsatz kann man die Gruppe zerlegen. Dann sieht man, dass hoch 12 die Gruppenelemente (der Einheitengruppe, d.h. teilerfremd zu 65) zu 1 macht.
kannst du genauer erklären was du meinst. Ich sehe jetzt nicht direkt den Zusammenhand :(
Es ist der Ring ℤ / 65 ℤ gegeben. Nach dem chinesischen Restsatz ist der isomorph zu ℤ / 5 ℤ × ℤ / 13 ℤ. Bei Primzahlringen sind alle Elemente außer dem (additiven) neutralen Element Einheiten. Das heißt bei dem linken Faktor gibt es in der Einheitengruppe 4 Elemente und bei dem zweiten 12. Ein Element hoch die Gruppenordnung ergibt 1. Darum reicht schon hoch 12 um die Einheiten zu 1 zu machen.
Wenn jetzt die 4 und 12 teilerfremd wären, dann bräuchte man das Produkt um die zu 65 teilerfremden Zahlen zu 1 zu machen.
Jetzt bin ich gerade selber verwirrt, weil dann müsste 49 im Exponenten sein. Wegen 37 muss ich doch nochmal selber überlegen.
wieso kann man von x^12 = 1 mod 13 auf x^12 = 1 mod 65 schließen ?