Primzahl n stark pseudoprim zu allen Basen a < n???

Neue Frage »

Mutza Auf diesen Beitrag antworten »
Primzahl n stark pseudoprim zu allen Basen a < n???
Folgender Beweis ist gesucht:

Sei n eine Primzahl (Aussage A), dann ist n stark pseudoprim für alle 0 < a < n.

Es gilt

Eine ungerade Zahl ist stark pseudoprim zur Basis a, wenn gilt

Aussage B:

ODER

Aussage C: für r < s

Ich weiß nicht wie ich an den Beweis rangehen soll...

Habe folgende Wege versucht, allerdings hab ich den richtigen Weg nicht gefunden...
1) Aus A und nicht B folgt C
2) Aus A und nicht C folgt B
3) Aus nicht B und nicht C folgt nicht A
Mutza Auf diesen Beitrag antworten »
RE: Primzahl n stark pseudoprim zu allen Basen a < n???
Ich habe inzwischen einen Link mit Beweis gefunden, allerdings versteheich den Beweis nicht, da er auf "Restklassen" und Restklassengruppen" basiert, was für mich wiederum nur böhmische Dörfer sind.

Hier der Link: http://home.arcor.de/alex.79/uni%20stuff/Rabin-Miller%20Test.pdf

Ich hoffe, jemand kann mir das erklären.

MfG der Mutza
Irrlicht Auf diesen Beitrag antworten »

Hm, also der Beweis ist sehr gut verständlich. Wenn du Probleme mit Restklassen und Restklassengruppen hast, dann solltest du allerdings auch mit Kongruenzen mod n ein Problem haben, denn das ist nichts anderes.

Daher frag ich einfach nochmal nach: Wo genau liegt dein Problem jetzt und was genau verstehst du nicht?
Mutza Auf diesen Beitrag antworten »

Was Kongruenzen und mod n bedeuten, das weiß ich (auch nicht erst seit gestern) nur die Begriffe Restklasse, bzw. Restklassengruppe sind mir noch nie untergekommen. Vielleicht wäre eine simple Definition der beiden Begriffe ja schon ausreichend.
Oder wenn jemand diesen Beweis einfach mal ohne die beiden Begriffe verfassen könnte...
Ben Sisko Auf diesen Beitrag antworten »

Ein Beispiel für eine Restklasse, dann ist es dir bestimmt klar.
Modulo 5 ist die Restklasse von 3 die Menge {..., -7, -2, 3, 8, 13, 18,...}. Die Restklassengruppe besteht dann aus den 5 Restklassen.

Gruß vom Ben
Mutza Auf diesen Beitrag antworten »

OK, dann nehmen wir das Ding mal auseinander:

Zitat:
Sei a ein ganze Zahl, die zu n teilerfremd ist.

(und 1 < a <n könnte da auch noch stehen)
Wenn n Primzahl ist, kann man sich den Satz nicht generell sparen???

Zitat:
Die Ordnung der primen Restklassengruppe mod n ist n-1 = d*2^s, weil n eine Primzahl ist.

Ich versuche mal zu interpretieren.
prime Restklassengruppe = Restklassengruppe beim Teilen durch Primzahl????
Ordnung der Restklassengruppe = Anzahl der verschiedenen Restklassen in der Gruppe???
Aussage des Satzes also: a mod n könnte n-1 verschiedene Reste haben???
Was soll der Zusatz
Zitat:
weil n Primzahl ist
???

Zitat:
Daher ist die Ordnung k der Restklasse a^d + nZ eine Potenz von 2

Wie bitte????
Was is den jetzt dann die Ordnung einer Restklasse???
Was ist nZ???
und woher kommt die Aussage generell???

Ich denke, wenn ich den Teil verstehe, dann kapier ich auch den Rest...(schon wieder dieses Wort)
 
 
Ben Sisko Auf diesen Beitrag antworten »

Wenn ich mich nicht irre, dann ist die Ordnung der Restklassengruppe die kleinste natürlich Zahl k, so dass für m aus der Restklassengruppe gilt .

Das Besondere daran, wenn n prim ist, ist dass dann die Restklassen einen Körper bilden.

Vielleicht hilft dir das kurzfristig schonmal weiter. Könnte ansonsten jemand meine Aussagen bestätigen, bzw. noch etwas fundierter helfen?

Gruß vom Ben
Irrlicht Auf diesen Beitrag antworten »

Die Ordnung eines Elements hat Ben ja schon definiert. Wenn du ein Element x einer multiplikativen Gruppe hast und du weisst, dass x^b = 1 ist, dann ist die Ordnung von x ein Teiler von b. Das musst du fuer den Beweis wissen.
Also ich schreib den Beweis jetzt mal in meinen Worten. Der Querstrich über manchen Elementen bezeichnet einfach die Restklasse dieses Elements mod n.



Sei a eine ganze Zahl, die zu n teilerfremd ist. Weil n eine Primzahl ist, ist die Ordnung der multiplikativen Gruppe gleich n-1. Schreiben wir mit ungeradem d.
Wir betrachten die Restklasse . Da , teilt die Ordnung k von die Zweierpotenz , ist also selbst wieder eine Zweierpotenz.

1. Fall:
Dann ist , d.h. .

2. Fall:
Dann hat die Restklasse die Ordnung 2 wegen .
Das einzige Element der Ordnung 2 in ist aber . Also gilt .
Mutza Auf diesen Beitrag antworten »

Da wir die Begriffe Ordnung, Restklasse usw nicht verwenden dürfen (nicht in der VL definiert) werd ich dann jetzt mal versuchen, das ganz auf die Begriffe Kongruenz, Satz von Fermat etc. herunterzubrechen...

Trotzdem schonmal danke, ich seh jetzt zumindest, wie es funktionieren sollte.

MfG der Mutza
FelixB Auf diesen Beitrag antworten »

Im Gegensatz zu dir checke ich das noch nciht so wirklich, erst recht nciht, wie ich das ohne "Ordnung" und "Restklasse" machen soll... hast da evtl. noch ein paar kleine Tipps?

thx
Felix
Irrlicht Auf diesen Beitrag antworten »

Ich werd mal überlegen, ob es noch irgendwie anders, aber nicht gross komplizierter geht. Wir müssen ja eigentlich nur noch die Ordnung erklären, denn die Restklassen kann man ja komplett durch Kongruenzen ersetzen (Überall wo ein quer oben steht, statt dem Gleichheitszeichen ein Kongruenzzeichen schreiben.)

Und ansonsten dürft ihr doch die Begriffe verwenden, wenn ihr sie auf eurem Übungsblatt definiert und die benötigten Eigenschaften nachweist. Das wäre im Fall der Ordnung nur Folgendes:

1. Definitiion: Die Ordnung einer ganzen Zahl a mod n ist die kleinste positive ganze Zahl s mit a^s kongruent 1 mod n.

2. Ist t eine positive ganze Zahl mit a^t kongruent 1 mod n, so ist s ein Teiler von t. (Das müsstet ihr noch beweisen, ist aber ganz leicht. Teilt t mit Rest durch s, dann ist t = qs + r. Dann einfach einsetzen und ausrechnen und feststellen, dass r kleiner als s ist, aber a^r kongruent 1 mod n ist. Also ist r=0.)

3. Eine ganze Zahl hat modulo n die Ordnung 2, wenn a nicht kongruent 1 mod n ist, aber a^2 kongruent 1 mod n ist.

Ich habe nützliche Begriffe immer auf dem Übungsblatt verwendet und die nötigen Eigenschaften (sofern es nicht zuviele waren) vorher schnell bewiesen. Dann kann auch kein Korrektor euch was abziehen, weil ja alles da steht, was bekannt ist.
Neue Frage »
Antworten »



Verwandte Themen

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