Ordnung von Gruppenelementen (Grundsatzfrage)

06.07.2009, 17:45

zem

Ordnung von Gruppenelementen (Grundsatzfrage)

Hallo an alle!
Ich schreibe bald eine Kryptographie-Klausur und habe ein Verständnisproblem beim Thema "Ordnung eines Gruppenelementes modulo m". Habe schon überall nach einem verständlichen Algorithmus gesucht, wie man diese Ordnung berechnet, verstehe aber nur "Bahnhof" :-( ...
Also, nehmen wir mal ein Beispiel:
"Bestimmen Sie die Ordnung von [9] in $\begin{eqnarray*} Z^*_{46} \end{eqnarray*}$ ". Die Lösung sagt einfach nur: " $\begin{eqnarray*} ord([9])=11 \end{eqnarray*}$ ".
Alles, was ich bis jetzt verstanden habe, ist, dass die Ordnung eines Elementes a der kleinste Exponent n ist, für welchen $\begin{eqnarray*} a^n \equiv 1 \mod m \end{eqnarray*}$ gilt und dass die Ordnung des Elementes die Ordnung der Gruppe teilt.
So, die Ordnung der Gruppe ist ja $\begin{eqnarray*} \varphi(46) = 46(1-1/2)(1-1/23) = 22 \end{eqnarray*}$ . Mir ist schon klar, dass 11 ein Teiler von 22 ist, aber wie komme ich auf die 11? Denn 2 ist ja auch ein Teiler von 22, ist aber nicht die Ordnung von 9!? Aber die Ordnung von [45] soll beispielsweise 2 sein. Auch hier: warum nicht die 11???.
Wie ist denn die korrekte Vorgehensweise beim Bestimmen der Elementenordnung einer zyklischen Gruppe? Ich vermute, ich stehe einfach nur voll am Schlauch, weil ich etwas außer Acht lasse...

Vielen Dank schonmal im voraus an denjenigen, der sich ein bisschen Zeit für mich nimmt!

Korrektur: Halt, jetzt sehe ich, dass das mit dem Teiler nur gilt, wenn m eine Primzahl ist! Und 46 ist ja gar keine! Jetzt versteh ich gar nix mehr :-(

06.07.2009, 18:16

Elvis

Auf diesen Beitrag antworten »

Die genaue Ordnung eines Elements muss man natürlich stets berechnen. Alles was man sagen kann ist, dass die Ordnung eines Elements die Gruppenordnung teilt.
Das gilt für jede Gruppe, denn die Ordnung eines Elements ist die Ordnung der von diesem Element erzeugten Untergruppe, und diese teilt die Gruppenordnung.
In diesem Fall gilt: $\begin{eqnarray*} ord([9]) \ne 2 \end{eqnarray*}$ , also $\begin{eqnarray*} ord[(9)]=11 \end{eqnarray*}$ , und das ist doch ziemlich schnell herausgekommen.

06.07.2009, 18:19

Elvis

Auf diesen Beitrag antworten »

Nachtrag: Es ist auch $\begin{eqnarray*} ord([9]) \ne 1 \end{eqnarray*}$ , wie man sieht.
Muss man auch noch $\begin{eqnarray*} ord([9]) \ne 22 \end{eqnarray*}$ zeigen, um das Ergebnis zu bekommen ???

06.07.2009, 18:25

Elvis

Auf diesen Beitrag antworten »

Falls deine Frage einfach heißen sollte, warum $\begin{eqnarray*} ord([9]) \ne 2 \end{eqnarray*}$ ist, so ist das so wegen $\begin{eqnarray*} 9^2=81 \equiv 35 \ne 1 \mod 46 \end{eqnarray*}$

06.07.2009, 19:37

zem

Auf diesen Beitrag antworten »

Vielen Dank für die schnelle Hilfe!

Also, ich fasse mal zusammen:
Zur Bestimmung der Ordnung eines Gruppenelements $\begin{eqnarray*} a \end{eqnarray*}$ modulo $\begin{eqnarray*} m \end{eqnarray*}$ macht man folgende Schritte:
1. Bestimme $\begin{eqnarray*} \varphi(m) \end{eqnarray*}$ und zerlege in Primfaktoren.
2. Nehme den kleinsten Primfaktor n und rechne $\begin{eqnarray*} a^n \pmod m \end{eqnarray*}$ .
3. Kommt 1 raus, so ist $\begin{eqnarray*} ord([a]) = n \end{eqnarray*}$ , sonst nimmt man den nächsthöheren Primfaktor usw.
(4. Falls $\begin{eqnarray*} ord([a]) = \varphi(m) \end{eqnarray*}$ , so ist $\begin{eqnarray*} a \end{eqnarray*}$ eine Primitivwurzel modulo $\begin{eqnarray*} m \end{eqnarray*}$ .)

Alles richtig?
Mann, scheint ja wirklich einfach zu sein. Wieso habe ich das nur nie verstanden? Hammer

Hm...
Nochmals vielen-vielen Dank!!!

06.07.2009, 19:46

Auf diesen Beitrag antworten »

Zitat:

Original von zem
Alles richtig?

Fast: Es klingt fast so, als testest du nur Primteiler als mögliche Ordnungen - i.a. kommen aber auch andere Teiler von $\begin{eqnarray*} \varphi(m) \end{eqnarray*}$ als Ordnung in Frage.

Zitat:

Original von Elvis
Muss man auch noch $\begin{eqnarray*} ord([9]) \ne 22 \end{eqnarray*}$ zeigen, um das Ergebnis zu bekommen ???

Hast du darauf eine "schnelle" Antwort? Augenzwinkern

06.07.2009, 23:10

zem

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Fast: Es klingt fast so, als testest du nur Primteiler als mögliche Ordnungen - i.a. kommen aber auch andere Teiler von $\begin{eqnarray*} \varphi(m) \end{eqnarray*}$ als Ordnung in Frage.

Stimmt, das war mir erst gar nicht bewusst, dass Teiler nicht gleich Primfaktoren sind. Also muss ich noch die Zahlen testen, die ein Produkt der einzelnen Primfaktoren bilden... Und die Potenzen der einzelnen Faktoren... Was in unserem Beispiel ja nicht der Fall ist, da unser "phi" 22 ist, also 2 mal 11...
Vielen Dank für den Hinweis!

Zitat:

Original von Arthur Dent

Zitat:

Original von Elvis
Muss man auch noch $\begin{eqnarray*} ord([9]) \ne 22 \end{eqnarray*}$ zeigen, um das Ergebnis zu bekommen ???

Hast du darauf eine "schnelle" Antwort?

Hm... Also, wenn ich die Frage richtig verstehe... Ich habe doch schon den kleinsten Exponenten gefunden (11), bei dem die Zahl 9 eine 1 modulo 46 ergibt, oder? Das reicht doch schon... verwirrt

07.07.2009, 00:23

Auf diesen Beitrag antworten »

Du hast also $\begin{eqnarray*} 9^{11} \bmod 46 \end{eqnarray*}$ echt ausgerechnet? Oder weshalb bist du dir sicher, dass es nicht doch die "volle" Ordnung 22 ist? Augenzwinkern

07.07.2009, 01:51

zem

Auf diesen Beitrag antworten »

Klar, mit schnellem Potenzieren oder mit CAS. Oder sieht man das "mit bloßem Auge", also auch ohne g^n mod m zu rechnen? verwirrt

07.07.2009, 10:37

Auf diesen Beitrag antworten »

Ja, man sieht es direkt an $\begin{eqnarray*} 9=3^2 \end{eqnarray*}$ : Denn dann ist

$\begin{eqnarray*} 9^{11} = 3^{22} \equiv 1\mod 46 \end{eqnarray*}$

sofort klar.

11.07.2009, 10:24

zem

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Ja, man sieht es direkt an $\begin{eqnarray*} 9=3^2 \end{eqnarray*}$ : Denn dann ist

$\begin{eqnarray*} 9^{11} = 3^{22} \equiv 1\mod 46 \end{eqnarray*}$

sofort klar.

Sorry, und warum ist "sofort klar", dass $\begin{eqnarray*} 3^{22} \equiv 1\mod 46 \end{eqnarray*}$ ?
Weil 3 eine Primitivwurzel modulo 46 ist?

11.07.2009, 10:33

Bjoern1982

Auf diesen Beitrag antworten »

Nein, wegen dem Zusammenhang $\begin{eqnarray*} a^{\varphi(n)} \equiv 1\ mod\ n \end{eqnarray*}$ mit ggt(a,n)=1

http://de.wikipedia.org/wiki/Satz_von_Euler

11.07.2009, 11:22

Elvis

Auf diesen Beitrag antworten »

Ja, allgemeiner gilt für jede endliche Gruppe $\begin{eqnarray*} G\,\,\,\, \forall a\in G : a^{ord(G)}=1 \end{eqnarray*}$

Beweis: Weil die Ordnung von a die Gruppenordnung teilt, ist $\begin{eqnarray*} ord(G)=ord(a) \cdot n \end{eqnarray*}$

Also $\begin{eqnarray*} a^{ord(G)}=a^{ord(a)\cdot n}=(a^{ord(a)})^n=1^n=1 \end{eqnarray*}$

11.07.2009, 12:21

Auf diesen Beitrag antworten »

Zitat:

Original von zem
Weil 3 eine Primitivwurzel modulo 46 ist?

Ist sie übrigens nicht, mit einer analogen Argumentation wie bei der 9, nur nicht so einfach zu sehen: Es ist

$\begin{eqnarray*} 3 \equiv 49 = 7^2 \mod 46 \end{eqnarray*}$

Die 7 ist dann allerdings eine primitive Wurzel modulo 46. Augenzwinkern

Neue Frage »

Antworten »

Ordnung von Gruppenelementen (Grundsatzfrage)

Verwandte Themen