Erzeuger einer multiplikativen Gruppe

22.11.2008, 02:03

Bjoern1982

Erzeuger einer multiplikativen Gruppe

Hallo,

wie finde ich am Besten einen Erzeuger der multiplikativen Gruppe $\begin{eqnarray*} (Z/31^2Z)^* \end{eqnarray*}$ ?

22.11.2008, 13:21

Leopold

Auf diesen Beitrag antworten »

Ich zitiere aus Wolfgang Schwarz, Einführung in die Zahlentheorie, Wissenschaftliche Buchgesellschaft Darmstadt 1987, Seite 48:

Die primen Restklassengruppen

$\begin{eqnarray*} \mathcal{P} \left( p^{\mu} \right) \, , \ \ p \neq 2 \, , \ \mu > 1 \end{eqnarray*}$

sind zyklisch. Ist $\begin{eqnarray*} g \in \mathbb{N} \end{eqnarray*}$ Primitivwurzel modulo $\begin{eqnarray*} p \end{eqnarray*}$ von der Ordnung $\begin{eqnarray*} n \end{eqnarray*}$ in $\begin{eqnarray*} \mathcal{P} \left( p^{\mu} \right) \end{eqnarray*}$ , so ist

$\begin{eqnarray*} (1+p) \cdot g^{\frac{n}{p-1}} \end{eqnarray*}$

ein erzeugendes Element von $\begin{eqnarray*} \mathcal{P} \left( p^{\mu} \right) \end{eqnarray*}$ .

Hier müssen wir zunächst eine Primitivwurzel modulo 31 bestimmen, also ein erzeugendes Element von $\begin{eqnarray*} \mathcal{P}(31) = \mathbb{Z}_{31}^{*} \end{eqnarray*}$ . Dafür kann man $\begin{eqnarray*} g = 3 \end{eqnarray*}$ nehmen. Die Ordnung von $\begin{eqnarray*} g \end{eqnarray*}$ muß ja ein Teiler von 30 sein. Modulo 31 gilt aber

$\begin{eqnarray*} 3^1 \equiv 3 \, , \ \ 3^2 \equiv 9 \, , \ \ 3^3 \equiv 27 \, , \ \ 3^5 \equiv 26 \, , \ \ 3^6 \equiv 16 \, , \ \ 3^{10} \equiv 25 \, , \ \ 3^{15} \equiv 30 \end{eqnarray*}$

$\begin{eqnarray*} g = 3 \end{eqnarray*}$ besitzt daher die Ordnung 30 in $\begin{eqnarray*} \mathcal{P}(31) \end{eqnarray*}$ und ist somit Primitivwurzel modulo 31.

Und nun mußt du noch die Ordnung $\begin{eqnarray*} n \end{eqnarray*}$ von $\begin{eqnarray*} g=3 \end{eqnarray*}$ in $\begin{eqnarray*} \mathcal{P}(961) = \mathbb{Z}_{961}^{*} \end{eqnarray*}$ bestimmen und den obigen Satz anwenden. Für $\begin{eqnarray*} n \end{eqnarray*}$ kommen nur die Teiler von $\begin{eqnarray*} \varphi(961) = 30 \cdot 31 \end{eqnarray*}$ in Frage.

22.11.2008, 15:52

Bjoern1982

Auf diesen Beitrag antworten »

Ich habe für n 930 raus, aber damit wird $\begin{eqnarray*} (1+p) \cdot g^{\frac{n}{p-1}} \end{eqnarray*}$ ja riesig groß oder muss ich das auch erst wieder modulo 961 rechnen ?

22.11.2008, 22:40

Leopold

Auf diesen Beitrag antworten »

Ich habe auch $\begin{eqnarray*} n=930 \end{eqnarray*}$ heraus. Dann haben wir aber, ohne es zu wollen, einen anderen Erzeuger gefunden. Wer hätt's gedacht?

Im übrigen kannst du bei jedem einzelnen Multiplikationsschritt immer gleich modulo 961 rechnen.

22.11.2008, 23:09

Bjoern1982

Auf diesen Beitrag antworten »

Zitat:

Im übrigen kannst du bei jedem einzelnen Multiplikationsschritt immer gleich modulo 961 rechnen.

Wenn du damit die Berechnung der Potenzen 3^x meinst mit x aus {1,2,3,5,6,10,15,30,31,62,93,155,186,310,465,930} dann habe ich das auch so getan.

Ist nun also e=716 ein möglicher Erzeuger dieser multiplikativen Gruppe ?

Fällt dir noch ein elementarer Weg ein um auf einen Erzeuger in dieser Größenordnung zu kommen, da wir diesen Satz nicht in der Vorlesung hatten ?

Danke für deine Hilfe.

23.11.2008, 10:48

Leopold

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \mathbb{Z}_{961}^{*} \end{eqnarray*}$ ist eine zyklische Gruppe mit 930 Elementen. Sie besitzt daher $\begin{eqnarray*} \varphi(930) = 240 \end{eqnarray*}$ Erzeuger. Einer davon ist, wenn der obige Satz stimmt, das Element 716. Aber auf unserer Fahrt nach Erzeugien hat sich doch ein blinder Passagier an Bord geschlichen. Hast du ihn noch nicht bemerkt?

24.11.2008, 00:34

Bjoern1982

Auf diesen Beitrag antworten »

Natürlich, du hast vollkommen Recht smile

Da $\begin{eqnarray*} ord_{961}(3)=n=930=\varphi(31^2) \end{eqnarray*}$ ist natürlich 3 ein möglicher Erzeuger von $\begin{eqnarray*} \mathbb{Z}_{961}^{*} \end{eqnarray*}$

Vielen Dank Wink

Neue Frage »

Antworten »

Erzeuger einer multiplikativen Gruppe

Verwandte Themen