Beweis über die Anzahl der Elemente in einer Menge

11.05.2015, 20:07	pansox	Auf diesen Beitrag antworten »
Beweis über die Anzahl der Elemente in einer Menge Hallo zusammen, ich versuche seit Stunden etwas zu beweisen, aber ich komme nicht voran. Vielleicht kann mir jemand von euch ja einen Tipp geben. Ich wähle zwei Primzahlen p und q, wobei q (p-1) ganzzahlig teilen soll. Ich wähle ein x zwischen 1 und p-1 und berechne ein g wie folgt: $\begin{eqnarray} g = x^{\frac{p-1}{q}} mod\ p \end{eqnarray}$ Nun soll ich zeigen, dass die Menge $\begin{eqnarray} \{ g^1 mod\ p,\ g^2 mod\ p,\ g^3 mod\ p,\ g^4 mod\ p ... \} \end{eqnarray}$ aus genau q Elementen besteht. Ich komme einfach nicht dahinter. Es geht ja schon los, dass egal welches x ich wähle, alle Möglichkeiten für $\begin{eqnarray} g^1 \end{eqnarray}$ ebenfalls nur q verschiedene Elemente haben und ich glaube gar, dieselben Elemente sind, wie bei der o.g. Menge, wenn ich ein x fest aber beliebig wähle. Ich wäre für jede Hilfe dankbar. Viele Grüße pan //Edit: Das x soll natürlich so gewählt werden, dass $\begin{eqnarray} g \neq 1 \end{eqnarray}$
11.05.2015, 21:21	HAL 9000	Auf diesen Beitrag antworten »
Das ist doch sehr einfach: Offenbar ist $\begin{align} g^q \equiv x^{p-1} \equiv 1\bmod p \end{align}$ also ist $\begin{align} \operatorname{ord}(g) \mid q \end{align}$ . Da außerdem $\begin{align} g\neq 1 \end{align}$ und somit $\begin{align} \operatorname{ord}(g) > 1 \end{align}$ gefordert wird, bleibt wegen der Primzahleigenschaft von $\begin{align} q \end{align}$ nur noch $\begin{align} \operatorname{ord}(g) = q \end{align}$ übrig.
11.05.2015, 21:48	pansox	Auf diesen Beitrag antworten »
HAL, 1000 Dank dafür. Ehrlich gesagt war das Thema der "Ordnung" mir komplett unbekannt. Aber ich habe es begriffen und bin begeistert. Dann kann mein endlos vollgeschriebenes Whiteboard nun wieder gesäubert werden :-) Viele Grüße pan
11.05.2015, 22:15	pansox	Auf diesen Beitrag antworten »
Hallo HAL, hallo Mitleser, ich muss doch noch mal fragen, ich bin leider fälschlich davon ausgegangen, dass ich verstünde, weshalb aus $\begin{eqnarray} ord(g) = q \end{eqnarray}$ hervorginge, dass die gesuchte Menge genau q Elemente hat? Wenn $\begin{eqnarray} ord(g)=q \end{eqnarray}$ ist, besagt das doch nur, dass die kleinste Potenz q ist, damit $\begin{eqnarray} g^q = 1\ mod\ p \end{eqnarray}$ ist. Ich sehe leider den Zusammenhang noch nicht. Woher weiß ich denn, dass es nicht trotzdem mehr Elemente gibt? Dass es mindestens q geben muss, verstünde ich noch, denn eben erst die q'te Potenz erfüllt diese Gleichung. Aber dass die $\begin{eqnarray} q+1 \end{eqnarray}$ 'te Potenz wieder ein Element der Menge erzeugt, sehe ich leider noch nicht? Danke für die Unterstützung! pan //Edit: Könnte ich denn vielleicht sagen: $\begin{eqnarray} g^{q+1}\ mod\ p = g^q g^1\ mod\ p = 1 * g^1 mod\ p \end{eqnarray*}$ etc. ?
11.05.2015, 22:18	HAL 9000	Auf diesen Beitrag antworten »
Oh nein, das sind Fragen... Für $\begin{align} m>0 \end{align}$ ist $\begin{align} g^{q+m} = g^q\cdot g^m \equiv 1\cdot g^m = g^m\bmod p \end{align}$ , war also irgendwíe schon mal da dieses Element, oder?
11.05.2015, 22:24	pansox	Auf diesen Beitrag antworten »
Ja, perfekt. Danke :-)
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »