infostudium.de

von **cliff** » 07.02.08 19:58

Hallo,

eine Frage zu einem Beispiel aus der heutigen Globalübung.

Herr Lübeck hat die Ordnung von 19quer mit m = 51 gezeigt.
Dazu hat er die Phi - Funktion angewendet.
(Also 51 in Primfaktoren zerlegt und dann eingesetzt) und kam dann auf
32.

Nun versteh ich den Schritt von da zur Ordnung noch nicht so ganz, denn da kommt 8 raus und ich habe mir nur das Stichwort sukzessives Quadrieren notiert.

Also wenn da einer den Schritt hat bitte mal kurz erkäutern.

von **SpatzenArsch** » 07.02.08 20:39

Hi,

ich bin mir zwar nicht sicher ob ich deine Frage richtig verstanden habe, aber ich denke du suchst die Anzahl der invertierbaren Elemente von Z/51Z (gesprochen Z modulo 51 Z) zumindest sind das genau 32 wie bei deiner Lösung.
Dazu musst du nur $\varphi(51)$ bestimmen, denn $\varphi(n)$ liefert dir die Anzahl der Elemente der Menge {1,..n-1} die den ggt 1 haben mit n. Das sind also genau die invertierbaren Elemente in dem Restklassenring Z/nZ.
Man kann dabei ausnutzen, dass die $\varphi$ -Funktion multiplikativ ist, in deinem Fall folgt also: $\varphi(51) = \varphi(3)*\varphi(17) = 2 * 16=32$ . Weiterhin gilt noch für p prim $\varphi(p) = p-1$ , darum ist die Faktorisierung in Primfaktoren doppelt sinnvoll.
Hoffe ich konnte dir mit der Antwort weiterhelfen, ansonsten versuch bitte die Frage nochmal anders zu formulieren. Ich hab zumindest nicht verstanden was 19quer sein soll.

SpatzenArsch

von fw » 07.02.08 23:06

SpatzenArsch hat geschrieben:was 19quer sein soll.

Damit meint er wohl die Äquivalenzklasse von 19 in Z/51Z. 19 (bzgl. streng genommen 19quer :-)) hat in dieser Gruppe die Ordnung 8. Als Tipp, um diese Ordnung zu finden, kann man hier den Satz von Lagrange benutzen. Die Ordnung jedes Elementes muss die Gruppenordnung teilen, d.h. die Ordnung von 19 muss ein Teiler von 32 sein! Da 32 eine 2er Potenz ist kommen auch nur Potenzen von 2 als Ordnung in Frage, daher wohl das "sukzessive Quadrieren" (d.h. einfach testen: 19^2, 19^4, 19^8.. 19^8 ist 1, also fertig)

Gruss
Flo

von **cliff** » 08.02.08 02:05

jepp meinte die Äquivalenzklasse von 19 in Z/51Z

alles klar , denke damit kann ich was anfangen...

danke schonmal

von **Chrizzo** » 14.02.08 23:54

hm, alles schön und gut, wie funktioniert das ganze mit den potenzierten "quer-Zahlen" *grübel* blick da garnet durch ^^

von fw » 15.02.08 11:01

Chrizzo hat geschrieben:hm, alles schön und gut, wie funktioniert das ganze mit den potenzierten "quer-Zahlen" *grübel* blick da garnet durch ^^

Hallo Chrizzo,

was sind denn "quer zahlen"? Meinst du ungerade Zahlen? Keine Ahnung was du meinst.. Gib mal eine Beispiel Aufgabe womit du nicht klar kommst...

Gruss
Flo

von **skka** » 15.02.08 11:16

Potenzieren von Querzahlen.. Aha... :shock:

fw hat eigentlich alles gesagt. Die Ordnung eines Elements e in diesem Kontext ist der kleinste Exponent x bei dem e^x kongruent 1 ist.

Wie fw sagte muss jede Ordnung die Gruppenordnung teilen (glaub mir jetzt einfach, ist echt einfach zu beweisen).
Da (Z/51Z)* (die multiplikative Einheitengruppe von Z/52Z) genau 32=2^5 Elemente hat muss also jede Ordnung eines Elements daraus 32 Teilen. Also muss jede Ordnung eine Zweierpotenz sein.

Darum nimmst du deine 19, quadrierst sie immer und guckst wann das Ergebnis das erste mal kongruent 1 ist. Hättest du z.B. zwei mal quadriert, wäre die Ordnung 4.

von **freiplatzzokker** » 15.02.08 11:16

Ich glaube er meint die Repräsentanten eines Restklassenrings...

von **Neronus** » 15.02.08 13:27

Wahrscheinlich meinte er
$a \mapsto \overline{a} := a + 51Z = \{z \in Z | z mod 51 = a \}$

Das heisst, dass $\overline{Z}$ die "Querzahlen" sind.

von fw » 15.02.08 13:31

Ah, daher das quer.

Lass dich davon mal nicht irritieren, du kannst mit Restklassen hier ganz genauso rechnen wie mit "normalen" ganzen Zahlen. $\overline{x}^n = \overline{x^n}$ , beachte aber, dass x nur ein Repräsentant ist und man in der Regel den kleinsten Repräsentanten (einen der kleiner ist als die Anzahl der Elemente des Rings) sehen will (es gibt also durchaus $x$ und $y$ mit $x \ne y$ aber $\overline{x} = \overline{y}$ ), d.h. du musst das Ergebnis noch "modulo rechnen".

z.B. in $\mathbb{Z}/5\mathbb{Z}$ gilt: $\overline{2}^3 = \overline{2^3} = \overline{8} = \overline{3}$

Man sagt dann auch " $2^3$ ist gleich $3$ in $\mathbb{Z}/5\mathbb{Z}$ ", womit man eigentlich entweder meint "Die Restklasse von 2 hoch 3 ist die selbe wie die Restklasse von 3 in $\mathbb{Z}/5\mathbb{Z}$ " oder etwas weniger algebraisch " $2^3$ ist kongruent 3 modulo 5" (formal: $2^3 \equiv 3 \ (mod 5)$ )

Hoffe das hilft dir :-)

Gruss
Flo

EDIT: ups, Neronus war schneller (und kürzer) :-)

von **Chrizzo** » 15.02.08 15:30

das mit den Querzahlen habt ihr schon richtig erkannt, darum auch alles in ""

und es werden auch die Ordnungen solcher Zahlen, allerdings potenziert, gefragt....z.b. Ordnung von 19(quer)^33....da war mein Problem, aber scheint ja beantwortet zu sein ^^ thx

von fw » 15.02.08 15:43

Chrizzo hat geschrieben:z.b. Ordnung von 19(quer)^33..

$\overline{19}^{33} = \overline{19}^{32+1} = \overline{19}^{8 \cdot 4} \cdot \overline{19}^{1} = \underbrace{(\overline{19}^8)}_{= \overline{1}}^4 \cdot \overline{19}^{1} = \overline{19}$

also ist die Ordnung von $19$ die gleiche wie die von $19^{33}$ (weil $19^{33}$ und $19$ "das selbe ist" in diesem Ring, das ist hier natürlich Zufall und gilt nicht für allgemeine Potenzen, für 34 statt 33 würds z.B. nicht so klappen!) Wenn du die Ordnung von der Basis schon kennst dann ist es aber meistens leicht das Ergebnis der Potenz in dem jeweiligen Ring auszurechnen und dann von dieser Zahl die Ordnung erneut auszurechnen..

von **Chrizzo** » 15.02.08 18:08

glaub ich habs blad xD

ah mom...wie wäre das Beispiel denn mit 19^34? und bei 19^8 = 1, für welches modulo hast du hier gerechnet?

von **Chrizzo** » 15.02.08 22:04

öhm, ich habs! braucht euch also keinen Kopp mehr drum machen ^^

von **aRo** » 18.02.08 11:37

ich möchte doch nochmal nachfragen, nachdem ich mir den Thread hier durchgelesen habe.

Also, die Ordnung eines Elements muss also die Gruppenordnung teilen. Und diese Gruppenordnung ist gerade die Phi-Funktion angewendet auf m in diesem Fall?
In der Vorlesung habe ich mir aufgeschrieben, dass jede Ordnung eines Elements die Anzahl der Elemente der Gruppe teilen muss. Das wäre ja in diesem Fall das gleiche, ne? Ist das immer so?

Okay, wenn man das also hingenommen hat, mal zurück zum Bsp. m=51, Ordnung von $\bar{19}$ ist zu bestimmen.

Die Ordnung muss also eine zweierPotenz sein - klar. Ihr quadriert also sukzessive mit Zweierpotenzen und guckt, wann $19^x mod 51$ 1 ist.
Aber da habe ich anscheinend was verpasst. Das ist ja jetzt so einfach im Kopf nicht. Wo ist da der Trick?

infostudium.de

Forum zum Informatikstudium an der RWTH Aachen

[Diskrete] Restklassenring / Ordnung

Restklassenring / Ordnung