Restklassenring Zn ist Körper wenn n prim

Neue Frage »

Pascal95 Auf diesen Beitrag antworten »
Restklassenring Zn ist Körper wenn n prim
Hallo,

als ich hier großartige Unterstützung erfuhr, kam mir die Frage auf, warum ein Restklassenring ein Körper ist, wenn .

Was den Unterschied zwischen einem Ring und einem Körper ausmacht, ist mir klar:
ist eine abelsche Gruppe (bei einem Ring reichts aus wenn es eine Halbgruppe ist).

Die Frage kann man also formulieren: Warum ist die Menge mit der Multiplikation eine abelsche Gruppe, wenn sie die Elemente eines Restklassenrings einer Primzahl sind?

Dazu wurde mir geraten, ich sollte Gruppentafeln (Tabellen mit Verknüpfung, Operanden und dem Ergebnis) aufstellen, wo ich dann überprüfe:
Das habe ich dann mal für die Primzahl 5 gemacht und für die 4 (jeweils beide Verknüpfungen).

[attach]19248[/attach]

[attach]19249[/attach]

Nun fällt mir auf, dass es bei der Addition für jedes Element ein Inverses gibt, sodass das neutrale Elemente = 0 herauskommt.
Das gilt für und für .

Allerdings gibt es für die Multiplikation nicht immer Inverse.
Ein Beispiel ist dafür bei hat die 2 kein multiplikatives Inverses (die Null hat ja eine Sonderrolle, die braucht kein Inverses).
Aber bei haben auch alle Zahlen (natürlich außer der 0) ein multiplikativ Inverses.

Dabei wurde mir gesagt, dass Zahlen genau dann ein multiplikativ Inverses haben, wenn , also wenn alle Zahlen bzgl. teilerfremd sind. Und das ist eben genau dann der Fall, wenn eben jene Zahl eine Primzahl ist.

Also stellt sich die Frage, warum Zahlen ein multiplikatives Inverses besitzen, wenn sie nicht n teilen.

Ich habe vom Begriff einer Primrestklassengruppe gehört, damit komme ich nicht weiter.

Vielen Dank!
Mulder Auf diesen Beitrag antworten »
RE: Restklassenring Zn ist Körper wenn n prim
Eine Idee, das zu zeigen, ist, sich für ein beliebiges die Menge



herzunehmen. M besteht aus genau n Elementen und ist logischerweise eine Teilmenge von . Wenn man nun zeigen kann, dass diese Elemente paarweise verschieden sind, ist man fertig, denn dann muss M schon ganz sein und folglich auch die 1 enthalten, weil die 1 ja auch in liegt.
Pascal95 Auf diesen Beitrag antworten »
RE: Restklassenring Zn ist Körper wenn n prim
Das ist mir nicht ganz klar was du meinst.

Wenn z.B. , dann ist .

Dass dies eine Teilmenge ist gilt aber auch nur, wenn man dann jeweils modulo rechnet.

Wenn man z.B wählt: , dann ist und man könnte nun wählen .

Dann wäre . Wenn man nun alle Elemente rechnet ist ja , aber dann ist auch .

Nur wie meinst du dass diese Elemente paarweise verschieden sind?
Dass es in keine doppelten Elemente gibt, aber wird ja wohl keine doppelten Elemente enthalten, sondern ggf. (oder verstehe ich das falsch?)

Der Rest ist mir dann aufgrund der vorherigen Missverständnisse unklar. Darum entschuldige ich mich...
Mulder Auf diesen Beitrag antworten »
RE: Restklassenring Zn ist Körper wenn n prim
M und M' sind doch modulo 5 genau die gleichen Mengen. Wir betrachten schon die Menge M immer modulo n. Das Problem ist eben nur, dass man das, was du jetzt M' genannt hast, nicht so hinschreiben kann, wenn man n und a allgemein lässt.

Wenn man nun zum Beispiel betrachtet, dann ist beispielsweise für a=2:



Und die Elemente aus M sind dann modulo 4 nicht paarweise verschieden.

Ich ergänze mal meinen ersten Beitrag:

Zitat:
Original von Mulder
Eine Idee, das zu zeigen, ist, sich für ein beliebiges die Menge



herzunehmen. M besteht aus genau n Elementen und ist logischerweise eine Teilmenge von . Wenn man nun zeigen kann, dass diese Elemente modulo n paarweise verschieden sind, ist man fertig, denn dann muss M schon ganz sein und folglich auch die 1 enthalten, weil die 1 ja auch in liegt.
Pascal95 Auf diesen Beitrag antworten »
RE: Restklassenring Zn ist Körper wenn n prim
Zitat:
Original von Mulder
M und M' sind doch modulo 5 genau die gleichen Mengen. Wir betrachten schon die Menge M immer modulo n.

Ok, hab ich mir dann doch auch so gedacht.

Zitat:
Original von Mulder
Wenn man nun zum Beispiel betrachtet, dann ist beispielsweise für a=2:



Und die Elemente aus M sind dann modulo 4 nicht paarweise verschieden,

weil es eben heißt und da kommen Elemente mehrfach vor.

So ganz klar ist es mir noch nicht, was die Menge einem nützt... verwirrt
Mulder Auf diesen Beitrag antworten »
RE: Restklassenring Zn ist Körper wenn n prim
Aha, also ist die Beweisidee noch überhaupt nicht klar. Also, wir betrachten (mit n Primzahl) und nehmen uns ein festes . Es ist



Jedes Element aus multiplizieren wir nun mit und betrachten die neue Menge, die dadurch entsteht. Die nennen wir M. Und was wir nun im wesentlichen zeigen wollen, ist, dass die 1 in M liegt. Denn dann hat in ein multiplikativ Inverses.
 
 
Pascal95 Auf diesen Beitrag antworten »
RE: Restklassenring Zn ist Körper wenn n prim
Zitat:
Original von Mulder
Und was wir nun im wesentlichen zeigen wollen, ist, dass die 1 in M liegt. Denn dann hat in ein multiplikativ Inverses.

Aha!. Denn ist ja eben eine Teilmenge von , dann wäre diese und dann ist das ja ein Inverses und ist dabei die Zahl mit der man multipliziert hat.
Mulder Auf diesen Beitrag antworten »
RE: Restklassenring Zn ist Körper wenn n prim
Zitat:
Original von Pascal95
Denn ist ja eben eine Teilmenge von

Wenn n prim ist, ist M sogar genau Zn. Das zeigen wir. Dann muss logischerweise die 1 auch in M liegen, weil sie ja auch in Zn liegt.

Und das macht man eben, indem man zeigt, dass die Elemente in M paarweise verschieden sind. M und Zn enthalten jeweils genau n Elemente. Und jedes Element aus M liegt auch in Zn. Wenn nun aber alle Elemente in M modulo n paarweise verschieden sind, enthält M genau n paarweise verschiedene Elemente, die allesamt auch in Zn liegen. Folglich: M=Zn
Pascal95 Auf diesen Beitrag antworten »

Ich glaube jetzt kommt allmählich eine Verbindung zum ggT...



Es kann ja nicht mehr Elemente als haben von der Anzahl her (weil es ja immer modulo gerechnet wird) und kann auch nicht neue zusätzliche Elemente haben, weil durch das von ja eine "obere Grenze" entstanden ist und man dann immer modulo rechnet.

Aber es kann auch passieren, dass weniger Elemente enthält als , wie es in deinem Beispiel passiert ist (da waren die Elemente ja nicht paarweise unterschiedlich).

Nun müsste man den Zusammenhang mit der Primzahl reinbringen, und zwar wenn prim, dann ist und enthält deswegen auch die .

Man müsste allerdings auch zeigen, dass nur dann wenn prim ist, gilt.

Habe ich also richtig verstanden:
ist die Zahl, zu der man das Inverse, wenn es denn existent ist, bestimmen möchte. Dabei multipliziert man alle Elemente von der Restklasse, um zu prüfen ob es bei einem klappt, dass 1 herauskommt. Wenn also 1 in der Menge ist, dann gibt es ein Inverses zu in der Restklasse.
Mulder Auf diesen Beitrag antworten »

Nimm dir zwei Elemente mit . ra und sa liegen in M und wir nehmen nun an, dass ra und sa modulo n (wobei n eine Primzahl ist) gleich sind. Jetzt wollen wir folgern, dass dann r=s sein muss.

ra und sa liegen in der selben Restklasse modulo n. Das bedeutet, wenn wir jetzt verlassen und uns das in anschauen, dass für gewisse gilt, dass



Umgeschrieben:



Also gilt:



Jetzt kommt die Primeigenschaft von n ins Spiel. Wenn eine Primzahl ein Produkt teilt, muss sie nach Definition auch schon einen der Faktoren teilen. Kann n a teilen?

Zitat:
Original von Pascal95
ist die Zahl, zu der man das Inverse, wenn es denn existent ist, bestimmen möchte.

Zu a kann man kein Inverses bestimmen. Wenn man a allgemein lässt, hat man doch keine Ahnung, wie das Inverse aussieht. Wir wollen nur zeigen, dass es existiert.
Pascal95 Auf diesen Beitrag antworten »

Zitat:
Original von Mulder
Also gilt:


Jetzt kommt die Primeigenschaft von n ins Spiel. Wenn eine Primzahl ein Produkt teilt, muss sie nach Definition auch schon einen der Faktoren teilen. Kann n a teilen?


Ich weiß leider nicht, ob du das noch auf oder auf beziehst.

Es gilt:
n teilt a wenn es eine ganze Zahl gibt, mit der n multipliziert a ergibt.
Das kann ja auch nur sein, wenn n kleiner als a ist?!?
Das kann ja nicht sein, weil ... verwirrt
Mulder Auf diesen Beitrag antworten »

Wir sind noch in Z.

Zitat:
Original von Pascal95
Das kann ja auch nur sein, wenn n kleiner als a ist?!?
Das kann ja nicht sein, weil ... verwirrt

Richtig. Also teilt n den anderen Faktor:



(r-s) muss also ein ganzzahliges Vielfaches von n sein. Nun ist aber ja, weil r und s in Zn liegen:



Was kann dann r-s nur sein?
Pascal95 Auf diesen Beitrag antworten »

Zitat:
Original von Mulder
Zu a kann man kein Inverses bestimmen. Wenn man a allgemein lässt, hat man doch keine Ahnung, wie das Inverse aussieht. Wir wollen nur zeigen, dass es existiert.

Ja, das habe ich falsch formuliert - Ich meinte das aber so wie ich es vielleicht am Ende des Satzes verbessert habe: "Wenn also 1 in der Menge ist, dann gibt es ein Inverses zu in der Restklasse."

Zitat:
Richtig. Also teilt n den anderen Faktor:



Juhu, auch mal was richtig Big Laugh

Zitat:

(r-s) muss also ein ganzzahliges Vielfaches von n sein. Nun ist aber ja, weil r und s in Zn liegen:



Was kann dann r-s nur sein?

r=s und dieses Vielfache ist dann multipliziert mit 1 weil alles andere drüber liegt.
Es heißt ja also folgt unmittelbar daraus, dass 2r >n und das wollen wir ja nicht (analog 2s>n ; das wollen wir auch nicht). Also muss r=s.

Aber,... was hat das jetzt gebracht?
Mulder Auf diesen Beitrag antworten »

Gebracht hat uns das sehr viel. Schauen wir uns M nochmal an:

Zitat:

Wir haben uns nun zwei Elemente aus M genommen: , weil ja waren.

Und wir haben nun



gesetzt und daraus gefolgert, dass dann schon r=s sein muss. Also sind alle Elemente in M paarweise verschieden.

Das klappt eben nicht, wenn n keine Primzahl ist (Beispiele haben wir oben in Z4 schon gesehen).
Pascal95 Auf diesen Beitrag antworten »

AHA Idee!

Wir haben uns die Elemente und aus herausgesucht, die durch Multiplikation von entstanden sind.

und haben die Eigenschaft, dass sie identisch bzgl. sind. [warum eigentlich?]
Wenn nun und stets identisch sind, dann sind alle Elemente paarweise verschieden, es gibt nun also genauso viele Elemente in wie in und deswegen , und deswegen , und deswegen besitzt ein Inverses in , also in .

Jetzt wäre es natürlich interessant zu wissen, warum eben diese Regel gilt:
Zitat:
Wenn eine Primzahl ein Produkt teilt, muss sie nach Definition auch schon einen der Faktoren teilen.

Diese Regel ist mir witzigerweise neu Augenzwinkern

Das heißt also, dass wenn , dann mit

Um alles abzurunden, müsste man das beweisen Big Laugh

Edit: Google hat mir da geholfen und zwar hier: Prim / Beweis [PDF] und zwar auf Seite 6... (das versteh ich noch nicht ganz... kenne Fachbegriff nicht: Lemma von Bezut... )
Mulder Auf diesen Beitrag antworten »

Zitat:
Original von Pascal95
Wenn nun und stets identisch sind, dann sind alle Elemente paarweise verschieden

Der Satz macht irgendwie keinen Sinn.

Zitat:
Original von Pascal95
[warum eigentlich?]

Weil wir das so angenommen haben. Augenzwinkern Wir haben doch gezeigt, WENN ra=sa mod n, DANN muss schon r=s sein.

Zitat:
Original von Pascal95
Um alles abzurunden, müsste man das beweisen

Lemma von Euklid

Man kann's auch sehr einfach zeigen, indem man



in Zp betrachtet und benutzt, dass Zp ein Körper (also insbesondere nullteilerfrei) ist. Andererseits haben wir ja gerade mit diesem Argument über Primzahlen bewiesen, dass Zp ein Körper ist, deswegen wäre das etwas ungünstig in diesem Fall. Augenzwinkern

Um es jedenfalls abschließend nochmal kurz zu fassen: Im Wesentlichen haben wir gezeigt, dass, wenn n prim ist, für a aus Zn gilt:



Natürlich mit a ungleich 0 Augenzwinkern
Pascal95 Auf diesen Beitrag antworten »

Warum denn "ra=sa mod n" ? (war auch nur eine Annahme?)
Mulder Auf diesen Beitrag antworten »

Zitat:
Original von Pascal95
Warum denn "ra=sa mod n" ? (war auch nur eine Annahme?)

? Hast du doch schon gefragt!? Ich meinte hier ra mod n = sa mod n.
Pascal95 Auf diesen Beitrag antworten »

Also mir ist klar, dass wir zeigen wollten, dass eben .
Was darauf folgt ist mir klar.

Nur wie wir zu gekommen sind ist mir noch nicht ganz klar.

Es war doch ungefähr so: .
Dass eine Teilmenge von ist, ist mir klar. Man hat ja alle Elemente mit einer Zahl aus multipliziert und dann modulo gerechnet.

Also stellt sich die Frage, warum eben alle Elemente in verschieden sind (sie sind paarweise verschieden). Man nimmt sich 2 Elemente und zeigt, dass sie gleich sind?
Aber warum "ra mod n = sa mod n" "r=s" induziert, ist mir klar.

Ich weiß nur nicht, warum das dann ein Beweis ist, warum hast du mit "ra mod n = sa mod n" angefangen? verwirrt Das verstehe ich nicht!
Mulder Auf diesen Beitrag antworten »

Zitat:
Original von Pascal95
Es war doch ungefähr so: .

Wobei das jetzt eine Argumentation ist, nur nur bei endlichen Mengen greift.

Zitat:
Original von Pascal95
Ich weiß nur nicht, warum das dann ein Beweis ist, warum hast du mit "ra mod n = sa mod n" angefangen. Das verstehe ich nicht!

Was soll ich darauf jetzt erwidern... den Beweis habe ja nicht ich entdeckt, ich habe ihn damals in einer VL gesehen und fand ihn ganz pfiffig. Die Frage nach dem "warum fängst du so an" ist kaum sinnvoll zu beantworten. Weil es so eben klappt. ra und sa sind doch zwei Elemente aus M. Wir haben jedes Element aus Zn mit a multipliziert und die Menge M erhalten. Alle Elemente aus der Menge M sind von der Gestalt "a mal irgendwas", wobei dieses "irgendwas" natürlich in Zn liegt.

Was wir nun gezeigt haben: Es gibt in M keine zwei voneinander verschiedenen Elemente, die modulo n dasselbe Ergebnis liefern würden. Also muss aus Anzahlgründen zwangsläufig irgendeins dabei sein, dass modulo n genau 1 ergibt. Das war ja alles, was wir eigentlich wollten. Zu zeigen, dass M genau gleich Zn ist, war dabei nur ein Umweg, den wir eben gehen mussten.

Wenn nun n nicht prim ist, gibt es in M eben sehr wohl unterschiedliche Elemente, die modulo n dasselbe liefern. Beispiel wie vorhin: n=4, a=2:



Und es ist beispielsweise. Also liegen in M weniger voneinander verschiedene Elemente als in Z4 und damit sind einfach nicht genug Elemente in M, um wirklich für jedes Element aus Z4 ein Inverses "übrig zu haben".

Sonst schlaf nochmal ne Nacht drüber, es verlangt ja niemand, dass man sowas immer gleich auf Anhieb alles durchblickt.
Pascal95 Auf diesen Beitrag antworten »

Ok, ich glaube jetzt wird mir einiges klarer.

Vielen Dank für deine Unterstützung!

Zitat:
Original von Mulder
Sonst schlaf nochmal ne Nacht drüber, es verlangt ja niemand, dass man sowas immer gleich auf Anhieb alles durchblickt.

Ja, ich geh momentan noch in die 9te Klasse und mache das so als "Interessensgebiet" Big Laugh nebenbei, aber ich sollte mich darin auf jeden Fall noch mal vertiefen.

Dann muss ich jetzt auch bald ins Bett gehen...

Vielen Dank noch mal!
Mulder Auf diesen Beitrag antworten »

Zitat:
Original von Pascal95
Ja, ich geh momentan noch in die 9te Klasse [...]

Ich muss gestehen, dass mir jetzt gerade schon ein bisschen die Kinnlade runterfällt. Dafür ist dein Wissen ja schon recht umfangreich. Freude

Es wäre trotzdem sinnvoll gewesen, mir das früher mitzuteilen, damit ich weiß, woran ich bin. Dann hätte ich vereinzelt auch anders auf dich eingehen können. Ich hatte mich nämlich schon gewundert, warum dir zum Beispiel das mit den Primzahlen nicht geläufig war. Da gibt's dann halt hier und da noch Lücken. Augenzwinkern

Edit: Ich wundere mich immer ein bisschen über deine Anzeige in der "Wer ist online"-Liste. Hast du vielleicht in deinem Profil nicht eingestellt, dass du angemeldet bleibst? Scheint mir so, als würdest du andauernd rausfliegen, oder irre ich mich da?
Pascal95 Auf diesen Beitrag antworten »

Ok, jetzt weißt du es LOL Hammer
Am besten trag ich mal in meinem Profil mein Geburtsdatum ein, dann sieht man, wie alt ich bin... muss ich gleich mal ausprobieren...

Du hast mir aber wirklich sehr gut geholfen smile

Vielen Dank dafür!

Edit:
Zitat:
Original von Mulder
Ich wundere mich immer ein bisschen über deine Anzeige in der "Wer ist online"-Liste. Hast du vielleicht in deinem Profil nicht eingestellt, dass du angemeldet bleibst? Scheint mir so, als würdest du andauernd rausfliegen, oder irre ich mich da?

Was ist denn da in der "Wer ist online"-Liste bei mir immer zu sehen?

Ich hab jetzt auch die Einstellung im Firefox gefunden, wo man festlegen kann, dass beim Beenden die Cookies nicht gelöscht werden, sodass man abgemeldet wird.
Ansonsten musste ich mich häufig neu einloggen, wenn ich den Tab nur geschlossen habe...
Mulder Auf diesen Beitrag antworten »

Zitat:
Original von Pascal95
Ansonsten musste ich mich häufig neu einloggen, wenn ich den Tab nur geschlossen habe...

Ja, hast du denn hier

[attach]19395[/attach]

das auch auf "Ja" stehen "(findest du unter "Einstellungen")? Dann fliegt man eigentlich nicht mehr raus. Das Problem hatte ich anfangs im Studentenwohnheim, warum auch immer.

Vielleicht täusche ich mich ja auch, wie gesagt. Dann ist es egal.
Pascal95 Auf diesen Beitrag antworten »

Da stand bei mir "nein" ... Ich habs mal geändert, ich war in den Einstellungen ansonsten eigentlich auch nicht weiter...
Mulder Auf diesen Beitrag antworten »

Dann hat sich das mit dem "häufig neu Einloggen" nun ja vielleicht erledigt. Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »