Primitivwurzeln

10.10.2023, 15:00

Bingo1

Primitivwurzeln

Hallo,

angenommen $\begin{eqnarray*} ggT(a,N) = 1 \end{eqnarray*}$ und $\begin{eqnarray*} (g^b)^N = 1 \end{eqnarray*}$ , dann sind $\begin{eqnarray*} (g^b)^{ai} \end{eqnarray*}$ für $\begin{eqnarray*} i = 0 \end{eqnarray*}$ bis $\begin{eqnarray*} N-1 \end{eqnarray*}$ gerade $\begin{eqnarray*} 1,g,g^b, (g^b)^2,...,(g^{b})^{N-1} \end{eqnarray*}$ . Wir wissen außerdem $\begin{eqnarray*} g^N = 1 \end{eqnarray*}$ .

Meine bescheidene Frage ist an dieser Stelle ist, wie man auf diese Sequenz kommt? Dieses $\begin{eqnarray*} a \end{eqnarray*}$ scheint für spezielle Indizes zu verschwinden, wobei interessant ist, dass es auch ein einzelnes $\begin{eqnarray*} g \end{eqnarray*}$ gibt...

Grüße,
Bingo

10.10.2023, 15:46

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Bingo1
angenommen $\begin{eqnarray*} ggT(a,N) = 1 \end{eqnarray*}$ und $\begin{eqnarray*} (g^b)^N = 1 \end{eqnarray*}$ , dann sind $\begin{eqnarray*} (g^b)^{ai} \end{eqnarray*}$ für $\begin{eqnarray*} i = 0 \end{eqnarray*}$ bis $\begin{eqnarray*} N-1 \end{eqnarray*}$ gerade $\begin{eqnarray*} 1,{\color{red}g},g^b, (g^b)^2,...,(g^{b})^{N-1} \end{eqnarray*}$ . Wir wissen außerdem $\begin{eqnarray*} g^N = 1 \end{eqnarray*}$ .

Ich denke, das $\begin{eqnarray*} {\color{red}g} \end{eqnarray*}$ ist zuviel, vermutlich beim Copy+Paste durchgerutscht.

Zu beachten ist, dass die angegeben Werte i.a. NICHT in der Seqeunz $\begin{eqnarray*} i = 0,1,\ldots,N-1 \end{eqnarray*}$ durchlaufen werden, sondern ggfs. auch in anderer Reihenfolge...

10.10.2023, 15:51

Bingo1

Auf diesen Beitrag antworten »

Danke! Also mit $\begin{eqnarray*} 1,{\color{red}g},g^b, (g^b)^2,...,(g^{b})^{N-1} \end{eqnarray*}$ steht es in meinem Skript, aber ich denke auch, dass das ein Tippfehler ist.

Aber wie kommt man denn auf diese Sequenz? Weil eigentlich hätten wir ja immer noch das $\begin{eqnarray*} a \end{eqnarray*}$ zu beachten, denn $\begin{eqnarray*} (g^b)^{a \cdot 0} = 1, (g^b)^{a \cdot 1}, ... , (g^b)^{a \cdot (N-1)} \end{eqnarray*}$ , aber warum verschwindet das $\begin{eqnarray*} a \end{eqnarray*}$ aus dem Exponent?

10.10.2023, 16:24

HAL 9000

Auf diesen Beitrag antworten »

Ich gehe erstmal davon aus, dass du von einer Gruppe sprichst mit neutralem Element 1.

Betrachten wir zunächst mal die Ordnung $\begin{eqnarray*} m \end{eqnarray*}$ des Elements $\begin{eqnarray*} h:=g^b \end{eqnarray*}$ : Wegen $\begin{eqnarray*} h^N = 1 \end{eqnarray*}$ wissen wir auf jeden Fall $\begin{eqnarray*} m\mid N \end{eqnarray*}$ , und die Elemente $\begin{eqnarray*} 1,h,h^2,\ldots,h^{m-1} \end{eqnarray*}$ sind paarweise verschieden und bilden zusammen eine Untergruppe $\begin{eqnarray*} U \end{eqnarray*}$ deiner Ausgangsgruppe.

Bestimmen wir nun noch die Ordnung $\begin{eqnarray*} m' \end{eqnarray*}$ von $\begin{eqnarray*} h^a \end{eqnarray*}$ :

1) Aus $\begin{eqnarray*} \left(h^a\right)^m = \left(h^m\right)^a = 1 \end{eqnarray*}$ folgt $\begin{eqnarray*} m'\mid m \end{eqnarray*}$ .

2) Aus $\begin{eqnarray*} \operatorname{ggT}(a,N)=1 \end{eqnarray*}$ folgt zwingend $\begin{eqnarray*} \operatorname{ggT}(a,m)=1 \end{eqnarray*}$ , und aus $\begin{eqnarray*} h^{am'}=1 \end{eqnarray*}$ folgt $\begin{eqnarray*} m\mid m'a \end{eqnarray*}$ , was mit der erwähnten Teilerfremdheit vcon $\begin{eqnarray*} a,m \end{eqnarray*}$ dann $\begin{eqnarray*} m\mid m' \end{eqnarray*}$ bedeutet.

Also insgesamt $\begin{eqnarray*} m'=m \end{eqnarray*}$ , somit sind $\begin{eqnarray*} 1,h^a,h^{2a},\ldots,h^{\left(m-1\right)a} \end{eqnarray*}$ paarweise verschieden und liegen gemäß Konstruktion alle in $\begin{eqnarray*} U \end{eqnarray*}$ , und damit SIND sie in ihrer Gesamtheit auch ganz $\begin{eqnarray*} U \end{eqnarray*}$ (jeweils genau $\begin{eqnarray*} m \end{eqnarray*}$ Elemente).

Jetzt haben wir "nur" über die Indizes $\begin{eqnarray*} i=0,\ldots,m-1 \end{eqnarray*}$ statt über $\begin{eqnarray*} i=0,1,\ldots,N-1 \end{eqnarray*}$ gesprochen, aber der Rest sind langweilige Wiederholungen:

Offenkundig ist sowohl $\begin{eqnarray*} h^{i+jm} = h^i \end{eqnarray*}$ als auch $\begin{eqnarray*} h^{\left(i+jm\right)a} = h^{ia} \end{eqnarray*}$ für alle $\begin{eqnarray*} i=0,\ldots,m-1 \end{eqnarray*}$ sowie $\begin{eqnarray*} j=0,1,\ldots,\frac{N}{m}-1 \end{eqnarray*}$ , und dieses $\begin{eqnarray*} i+jm \end{eqnarray*}$ durchläuft nun den ganzen geforderten Indexbereich $\begin{eqnarray*} 0,1,\ldots,N-1 \end{eqnarray*}$ .

10.10.2023, 17:38

Bingo1

Auf diesen Beitrag antworten »

Danke! Aus $\begin{eqnarray*} ggT(a,N)=1 \end{eqnarray*}$ folgt zwingend $\begin{eqnarray*} ggT(a,m)=1 \end{eqnarray*}$ , warum? Es war doch $\begin{eqnarray*} ggT(a,N)=ggT(a,qm) = 1 \end{eqnarray*}$ , denn $\begin{eqnarray*} m|N \end{eqnarray*}$ .

10.10.2023, 18:13

Malcang

Auf diesen Beitrag antworten »

Hallo zusammen,

HAL, ich hoffe es ist ok wenn ich mich hier einklinke. Möchte dir nicht dazwischenfunken!

Zitat:

Original von Bingo1
Danke! Aus $\begin{eqnarray*} ggT(a,N)=1 \end{eqnarray*}$ folgt zwingend $\begin{eqnarray*} ggT(a,m)=1 \end{eqnarray*}$ , warum? Es war doch $\begin{eqnarray*} ggT(a,N)=ggT(a,qm) = 1 \end{eqnarray*}$ , denn $\begin{eqnarray*} m|N \end{eqnarray*}$ .

Der letzte Teil ist genau die Antwort auf deine Frage.
Von HAL 9000 wissen wir, dass $\begin{eqnarray*} m \end{eqnarray*}$ ein Teiler von $\begin{eqnarray*} N \end{eqnarray*}$ ist. Nehmen wir nun an, $\begin{eqnarray*} \operatorname{ggT}(a, m) = g >1. \end{eqnarray*}$
Dann gelten $\begin{eqnarray*} g\mid a \end{eqnarray*}$ und $\begin{eqnarray*} g\mid m. \end{eqnarray*}$
Wegen $\begin{eqnarray*} g\mid m \end{eqnarray*}$ gilt aber auch $\begin{eqnarray*} g\mid N. \end{eqnarray*}$
Wir haben also $\begin{eqnarray*} g\mid a \end{eqnarray*}$ und $\begin{eqnarray*} g\mid N \end{eqnarray*}$ mit $\begin{eqnarray*} g>1, \end{eqnarray*}$ also einen Widerspruch zur Teilerfremdheit von $\begin{eqnarray*} a \end{eqnarray*}$ und $\begin{eqnarray*} N. \end{eqnarray*}$

10.10.2023, 18:18

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
HAL, ich hoffe es ist ok wenn ich mich hier einklinke. Möchte dir nicht dazwischenfunken!

Zum einen habe ich nichts gegen Dazwischenfunken, solange es nicht grob falsch oder extrem ablenkend ist. Zum anderen war ich fertig, und Nachfragen können gern auch andere beantworten - erst recht, wenn ich nicht online bin.

Eine Anmerkung noch zur Threadüberschrift: Um Primitivwurzeln geht es hier bei dieser Aussage an sich überhaupt nicht. Möglicherweise ist mit $\begin{eqnarray*} g \end{eqnarray*}$ hier eine Primitivwurzel gemeint, d.h., die Ordnung von $\begin{eqnarray*} g \end{eqnarray*}$ ist dann $\begin{eqnarray*} N \end{eqnarray*}$ . Ändert aber nichts am obigen Lösungsweg, bei dem dann $\begin{eqnarray*} m=N \end{eqnarray*}$ selbst im Fall " $\begin{eqnarray*} g \end{eqnarray*}$ ist Primitivwurzel" nur dann gelten würde, falls auch $\begin{eqnarray*} \operatorname{ggT}(b,N)=1 \end{eqnarray*}$ gilt.

11.10.2023, 09:36

Bingo1

Auf diesen Beitrag antworten »

Danke! Also nochmal zu meiner Frage, warum das $\begin{eqnarray*} a \end{eqnarray*}$ in $\begin{eqnarray*} (g^b)^{a \cdot 0} = 1, (g^b)^{a \cdot 1}, ... , (g^b)^{a \cdot (N-1)} \end{eqnarray*}$ verschwindet. Das liegt daran, weil $\begin{eqnarray*} (g^b)^{a \cdot 0} = 1, (g^b)^{a \cdot 1}, ... , (g^b)^{a \cdot (N-1)} \end{eqnarray*}$ und $\begin{eqnarray*} 1,g^b, (g^b)^2,...,(g^{b})^{N-1} \end{eqnarray*}$ bis auf die Reihenfolge gleich sind, richtig?

11.10.2023, 09:57

HAL 9000

Auf diesen Beitrag antworten »

Mir gefällt diese Charakterisierung " $\begin{eqnarray*} a \end{eqnarray*}$ verschwindet" nicht, weil das ja nicht passiert. Das $\begin{eqnarray*} a \end{eqnarray*}$ bewirkt, dass die Werte in einer anderen Reihenfolge angeordnet sind. Als Menge betrachtet - oder sollte ich besser sagen Liste - sind beide gleich.

11.10.2023, 10:05

Bingo1

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Mir gefällt diese Charakterisierung " $\begin{eqnarray*} a \end{eqnarray*}$ verschwindet" nicht, weil das ja nicht passiert.

Ja, richtig. Ich wollte auch eher ausdrücken, dass was in deinem Nachfolgesatz steht:

Zitat:

Original von HAL 9000Das $\begin{eqnarray*} a \end{eqnarray*}$ bewirkt, dass die Werte in einer anderen Reihenfolge angeordnet sind.

Zur Threadüberschrift, wenn Primitivwurzel kein Oberbegriff ist, was dann?

11.10.2023, 11:15

HAL 9000

Auf diesen Beitrag antworten »

Weiß ich nicht, aber Fakt ist, dass in dieser Aussage nicht vorausgesetzt werden muss, dass $\begin{eqnarray*} g \end{eqnarray*}$ Primitivwurzel ist. Man schreibt ja beispielsweise auch nicht als Überschrift für den Kosinussatz "Aussage über das gleichseitige Dreieck", obwohl das zweifelsohne richtig ist.

Neue Frage »

Antworten »

Primitivwurzeln

Verwandte Themen