Frage zu Rabin Miller

[W*lly]

Hallo!

Ich beschäftige mich zur Zeit mit dem Rabin Miller Primzahltest und versuche ihn zu verstehen. Aber ich hab dazu mal eine Frage:
Der Test basiert ja auf der Suche nach nichttrivialen Primitivwurzeln von 1 mod p (p ist prim). In eigentlcih allen Quellen die ich im internet lese wird einfach behauptet, dass es im falle dass p prim ist nur die beiden primitivwurzeln 1 und -1 gibt. Im falle dass p nicht prim is gibt es mehrere primitivwurzeln.
Meine frage ist jetzt: wieso ist das so?

die meisten quellen gehen versuchen es so zu begründen dass die gleichung a^2≡1 mod n nur genau die lösung 1 und -1 wenn in einem körper gerechnet wird, also wenn man in der restklassenmenge einer primzahl rechnet. ich verstehe auch wieso die restklassenmenge einer primzahl ein körpers ist und die restklassenmenge einer nicht Primzahl ein ring, aber ich verstehe nicht wieso dann die gleichung a^2≡1 mod n in einem ring mehr als 2 lösungen hat.

Danke im voraus für hilfe!

[SG1]

In Z/8Z ist z.B. 3^2 = 1.

[W*lly]

hm... ja... aber das beantwortet meine frage nicht

[wolfgke]

Warum der Restklassenring bzgl. einer Primzahl ein Körper und ansonsten kein Körper ist, kann ich dir erklären:

Sei n keine Primzahl => n=a*b

a!=0, b!=0

a*b = 0 mod n

=> Widerspruch zur Nullteilerfreiheit eines Körpers

Die andere Richtung: Sei n Primzahl

und k*l= 0 mod n

=> k*l= m*n
=> entweder k oder l enthält Primfaktor n
=> k=0 mod n oder l=0 mod n
=> Nullteilerfreiheit

Nun brauchen wir noch den Satz: Ein nullteilerfreier kommutativer Ring mit endlich vielen Elementen und 1 ist ein Körper

z. z. Multiplikation ist surjektiv.
Bei endlich vielen Elementen äquivalent mit Multiplikation ist injektiv

sei x1!=x2 und a*x1=a*x2

=> a*(x1-x2)=0
=> a=0 oder x1=x2

[W*lly]

danke, aber das hatte ich ja verstanden. mir geht es nur darum warum in einem körper die gleichung a²≡1 die beiden lösungen 1 und -1 hat (also wenn man im restklassenring einer primzahl rechnet) aber in einem ring (also im restklassenring einer nicht primzahl) weitere lösungen besietzt.

[Christoph]

W@lly schrieb:

mir geht es nur darum warum in einem körper die gleichung a²≡1 die beiden lösungen 1 und -1 hat (also wenn man im restklassenring einer primzahl rechnet)

Dies gilt nicht allgemein für alle Körper, wie man an den komplexen Zahlen sieht.

Jeder Restklassenring modulo einer Primzahl hat eine Primitivwurzel. Eine Primitivwurzel ist ein Element, aus dem sich durch Potenzieren alle anderen Elemente erzeugen lassen. Zum Beispiel ist in (Z/7Z) eine Primitivwurzel die 3:

$$

\begin{eqnarray*}
3^1 &\equiv 3 \quad\mathrm{mod}; 7\
3^2 &\equiv 2 \quad\mathrm{mod}; 7\
3^3 &\equiv 6 \quad\mathrm{mod}; 7\
3^4 &\equiv 4 \quad\mathrm{mod}; 7\
3^5 &\equiv 5 \quad\mathrm{mod}; 7\
3^6 &\equiv 1 \quad\mathrm{mod}; 7\
\end{eqnarray*}$$

Das bedeutet, du nimmst aus der invertierbaren Restklasse modulo 7 irgendein Element heraus und kannst sicher sein, dass es sich als $3^k$ (für irgendein ganzzahliges k) schreiben lässt.

Jede Restklasse modulo einer Primzahl hat eine Primitivwurzel, die ich im folgenden g nenne. Wie man auch an dem Beispiel oben sieht, ist $g^{p-1} \equiv 1 \quad\mathrm{mod}\; p$. Ist die Potenz von g nicht irgendein Vielfaches von p-1, so erhält man sicher nicht 1, weil g eine Primitivwurzel ist. Eine Primitivwurzel durchläuft beim Potenzieren erst alle anderen Elemente (von denen es p-2 gibt), bevor die 1 drankommt.

p-1 ist gerade, wenn man den Sonderfall p = 2 mal außer acht lässt. Deswegen darf man (p-1)/2 betrachten und stellt fest:
$\left(g^{\frac{p-1}2}\right)^2 = g^{p-1} \equiv 1 \quad\mathrm{mod}\; p$. Das heißt, $g^{\frac{p-1}2}$ ist etwas, das, wenn man es quadriert, 1 ergibt. Das es nicht die 1 selbst ist, ist klar, weil g eine Primitivwurzel ist.

Sei $x$ eine Lösung der Gleichung $x^2 \equiv 1 \quad\mathrm{mod}\; p$. Dann lässt sich x mit einem geeigneten k schreiben als $g^k$. Jetzt weiß man aber, dass $\left(g^k\right)^2 = g^{2k} \equiv 1 \quad\mathrm{mod}\; p$. g potenziert mit irgendwas gibt aber, weil g eine Primitivwurzel ist, genau dann 1, wenn der Exponent ein ganzzahliges Vielfaches von p-1 ist. Was für Möglichkeiten bleiben nun für k, damit 2k ein Vielfaches von p-1 ist?

1. k ist selbst ein Vielfaches von p-1.
2. k ist kein Vielfaches von p-1, aber ein Vielfaches von (p-1)/2.

Das waren alle Möglichkeiten für k. Bei der 1. Möglichkeit ist x = 1. Wir müssen noch -1 vergeben, das ja (wie bekannt ist) eine Lösung der qudratischen Gleichung ist. Also ist $g^{\frac{p-1}2} = -1 \quad\mathrm{mod}\; p$.

Weitere Lösungen kann es nicht geben, die Fälle 1 und 2 sind die einzigen.

W@lly schrieb:

aber in einem ring (also im restklassenring einer nicht primzahl) weitere lösungen besietzt.

Auch in einem Ring kann es bei den eindeutigen Lösungen 1, -1 bleiben. Nimm zum Beispiel (Z/6Z). Wenn ich mich nicht verrechnet habe, besitzt die Gleichung $x^2 \equiv 1 \quad\mathrm{mod}\; 6$ genau zwei Lösungen, 1 und -1.

Anders als im primen Restklassenring besteht jedoch die Möglichkeit, dass es weitere Lösungen gibt.

[Jester]

Christoph schrieb:

W@lly schrieb:

mir geht es nur darum warum in einem körper die gleichung a²≡1 die beiden lösungen 1 und -1 hat (also wenn man im restklassenring einer primzahl rechnet)

Dies gilt nicht allgemein für alle Körper, wie man an den komplexen Zahlen sieht.

Hä, was sieht man da jetzt genau? Auch in C gibt's nur die Lösungen +/-1.

[Christoph]

Jester schrieb:

Christoph schrieb:

W@lly schrieb:

mir geht es nur darum warum in einem körper die gleichung a²≡1 die beiden lösungen 1 und -1 hat (also wenn man im restklassenring einer primzahl rechnet)

Dies gilt nicht allgemein für alle Körper, wie man an den komplexen Zahlen sieht.

Hä, was sieht man da jetzt genau? Auch in C gibt's nur die Lösungen +/-1.

Stimmt, mein Fehler. Ich hatte irgendwie an "Einheitswurzeln" gedacht und dabei das "2. Einheits~" vergessen.