infostudium.de

von fw » 18.02.08 11:57

aRo hat geschrieben: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?

Ja, genau, "Ordnung" einer Gruppe ist nichts anderes als die Anzahl der Elemente. Das Wort hat hier quasi eine Doppelbelegung, einmal bezogen auf Gruppen und einmal auf Elemente. Bei Elementen ist die kleinste Zahl gemeint, so dass die Potenz des Elementes dieser Zahl wieder das neutrale Element ergibt. Wichtig ist hier, dass NICHT die Anzahl der Elemente (bzw. nicht die Ordnung) von $\mathbb{Z}/n\mathbb{Z}$ gemeint sind (als Ring oder als additive Gruppe), das wären nämlich genau n Stück! Gemeint ist die Anzahl der Elemente der multiplikativen Gruppe (auch "Einheitengruppe" genannt) dieses Rings, das schreibt man dann meistens mit einem Kreuzchen oder einem Stern: $(\mathbb{Z}/n\mathbb{Z})^{*}$ , und die Anzahl dieser Elemente ist gerade die Anzahl der Elemente die teilerfremd zu $n$ sind (jedes Element muss invertierbar sein! und nach meinem vorherigen Post sind das genau die, die teilerfremd zu $n$ sind), und das ist genau die Definition von $\varphi$ , d.h. $\varphi(n) := | ( \mathbb{Z}/n\mathbb{Z} )^{*} |$

aRo hat geschrieben:Aber da habe ich anscheinend was verpasst. Das ist ja jetzt so einfach im Kopf nicht. Wo ist da der Trick?

Da gibts keinen Trick, das ist nur ein bisschen Kopfrechnen mit Modulo.

$19^1 = 19 \equiv 19\ (mod 51)$
$19^2 = 361 \equiv 4\ (mod 51)$
$19^4 = 19^2 \cdot 19^2 \equiv 4 \cdot 4 \equiv 16\ (mod 51)$
$19^8 = 19^4 \cdot 19^4 \equiv 16 \cdot 16 \equiv 256 \equiv 1 \ (mod 51)$

Ok, kleiner "Trick" ist vielleicht, dass man direkt nach jedem Schritt schon modulo rechnen kann und nicht erst ganz am Ende, dadurch werden die Zahlen kleiner (19^8 kann ich natürlich nicht im Kopf ;))

Gruss
Flo

von **NeX** » 18.02.08 15:41

ich habe auch nochmal eine frage dazu...

was passiert bei zahlen die nicht zweier potenz sind wo ich somit nicht sukzessive quadrieren darf....

als Beispiel: Die Ordnung von 96 ist 60 für mod 1001

wie komme ich darauf ....bei einer "zweierpotenz" ist es kein problem mehr....aber wie geht das allgemein ....

da stehe ich irgendwie völlig auf dem schlauch.....

ps: wie sind die tags um hier latex einzubinden....habe noch nicht viel erfahrung damit ....würde es aber hier trotzdem gerne benutzen....habe in dem latex 1x1 nichts dazu gefunden....vielleicht bin ich ja auch blind...

von fw » 18.02.08 16:07

NeX hat geschrieben:als Beispiel: Die Ordnung von 96 ist 60 für mod 1001

Erstmal bestimmen wir die Gruppenordnung der multiplikativen Gruppe dieses Ringes (was für große (zusammengesetzte) Zahlen übrigens alles andere als trivial ist, da man dafür die Primfaktorzerlegung kennen muss): $| (\mathbb{Z}/1001\mathbb{Z})^{*} | = \varphi(1001) = \varphi(7 \cdot 11 \cdot 13) = \varphi(7) \cdot \varphi(11) \cdot \varphi(13) = 6 \cdot 10 \cdot 12 = 720$ . Okay, das schränkt unsere Suche schonmal sehr ein, da die Ordnung von jedem Element, also insbesondere auch von 96, ein Teiler von $720 = 2^2 \cdot 3^2 \cdot 4^1 \cdot 5^1$ sein muss.

Per Hand würde ich das nun einfach ausprobieren, mit den kleinsten Teilern anfangen, etc... Aber wenn man es implementieren will gibt es da sicher kleverere Verfahren (z.B. "Square and Multiply").. Da ich die Vorlesung nicht höre weiss ich nicht was ihr da so gemacht habt zum "schnellen Potenzieren" (Potenzieren in Gruppen geht übrigens effizient, d.h. in Polynomialzeit (im Gegensatz zu der inversen Operation, dem Logarithmus!))

von **NeX** » 18.02.08 16:19

im grundsatz haben wir glaube ich gar nichts zum "schnellen potenzieren" gemacht...(bin mir eigentlich sicher)

es geht mir auch eigentlich nur um das allgemeine verfahren was ich jetzt glaube ich verstanden habe...sowas wird sicher nicht in der klausur vorkommen....zumindest nicht mit so großen zahlen....

es war einfach interesse halber mehr oder weniger....

d.h. ich müsste nun alles durchgehen .....was ein teiler von 720 ist und würde bei 60 feststellen das es klappt ?....

von **DominikP** » 18.02.08 18:07

NeX hat geschrieben:d.h. ich müsste nun alles durchgehen .....was ein teiler von 720 ist und würde bei 60 feststellen das es klappt ?....

so hab ich es jedenfalls bisher gemacht. mit einem taschenrechner oder einem computer-algebra system ist das kein thema.
aber per hand hab ich zum nachrechnen der übung nur die "kleinen" zahlen gemacht.

hr. lübeck ist ja der ansicht, wir brauchen keine probeklausur. das muss ich hart kritisieren, denn wir haben keine ahnung, was für aufgaben in welchem schwierigkeitsgrad uns erwarten, zumal alles im kopf zu rechnen ist.

von **Chrizzo** » 18.02.08 18:41

das dachte ich mir auch schon, vorallem da die alten Klausuren mal garnix bringen oO

btt: nehmen wir letztgenanntes Bsp., wie läuft das nochma mit 96^789 und seiner Ordnung? Habs i-wie wieder vercheckt -__-

von HE » 18.02.08 19:43

Chrizzo hat geschrieben:das dachte ich mir auch schon, vorallem da die alten Klausuren mal garnix bringen oO

btt: nehmen wir letztgenanntes Bsp., wie läuft das nochma mit 96^789 und seiner Ordnung? Habs i-wie wieder vercheckt -__-

Also, wir wissen dass 96 in der multiplikativen Gruppe $\mathbb{Z} / \mathbb{Z}*1001$ die Ordnung 60 hat. 789 kann man ganz wunderbar zerlegen in 60*13+9, daher schreiben wir $96^{789} = 96^{13*60} * 96^9 = 1 * 96^9$ .

Mit Taschenrechner ist das jetzt klein genug für brutales Ausrechnen, aber gehen wir mal aus, dass gerade mal keiner da ist. Also machen wir mal eine Faktorisierung: $96 = 2^5*3$ . Damit geht dann relativ leicht von der Hand, dass $96^2 mod 1001 = 2^{10} * 3^2 mod 1001 = 1024 * 3^2~mod~1001 = 23 * 9~mod~1001= 207~mod~1001$ . 207 ist 23*9
Also fassen wir das mal zusammen: $96^{789} = 96^9 = (96^2)^4 * 96 = (207)^4 * 96 = (23*3^2)^4 * 96 = 23^4 * 81^2 * 96$ . Naja, dann gehen wir mal einzeln dran: $81^2 = 6561= 6*1001 + 555$ , dazu dann $23^4 = 529 * 23 * 23 = (12*1001 + 155) * 23 mod 1001 = 155 * 23 = 3565 = 3*1001 + 562$ . Naja, ab da halt brutales Rechnen. Geht alles auf Papier, wenn man die Sachen passend faktorisiert und neu zusammenfasst, dass die Werte relativ klein bleiben. Den Rest halt schriftlich multiplizieren und gut ist.

von **Chrizzo** » 18.02.08 19:47

na, bis zur Hälfte binsch auch selber drauf, kam dann aber nicht weiter ^^ nette Erklärung, leuchtet ein

von **aRo** » 18.02.08 20:10

Hi!

m=97. Das Element 13 hat die Ordnung 96. Was ist die Ordnung von 13^14?

So, anscheinend geht das ganz einfach per Rechnung:

96/ggT(14,96) = 48

Kann mir jemand sagen, warum?

von **NeX** » 18.02.08 21:44

Chrizzo hat geschrieben:das dachte ich mir auch schon, vorallem da die alten Klausuren mal garnix bringen oO

btt: nehmen wir letztgenanntes Bsp., wie läuft das nochma mit 96^789 und seiner Ordnung? Habs i-wie wieder vercheckt -__-

du nimmst :

60 / ggt(60, 789)

der ggt(60, 789) ist leicht zuerrechen mit dem euklidischen Algorithmus

also haben wir 60 / 3 = 20....und fertig.....

das klappt (zumindest was wir bis jetzt durchgerechnet haben) immer wenn man eine ordnung vorgegeben hat

@aRo...

warum das so ist wissen wir auch noch nicht genau....

von **Chrizzo** » 18.02.08 22:18

thx Nex, auch wenns mir durch den vorherigen Post klar war, aber warum das nu so ist, schliess ich mich dir ma an ;D

von **zorgblaubaer** » 19.02.08 00:24

aRo hat geschrieben:Hi!

m=97. Das Element 13 hat die Ordnung 96. Was ist die Ordnung von 13^14?

So, anscheinend geht das ganz einfach per Rechnung:

96/ggT(14,96) = 48

Kann mir jemand sagen, warum?

naja der ggT von 14 und 96 ist doch 2 und 96/2 ist ganz klar 48

von **Chrizzo** » 19.02.08 01:04

jaja, aber warum kann man das so einfach rechnen war die urspr. Frage

von **DominikP** » 19.02.08 13:14

Okay.
Die Aufgaben, bei denen eine Ordnung vorgeben ist, gehen bei mir jetzt recht gut.

Schwieriger finde ich es, wenn KEINE Ordnung vorgegeben ist. Bzw. nur deswegen, weil in der Klausur Taschenrechner tabu sind.

Aufgabe 4 von Blatt 7, fände ich dann schon zu hart. Irgendwie fehlt mir die Vorstellung, wie schwierig das Kopfrechnen in der Klausur wird.

Beispiel (Ü-Blatt 7, Aufgabe 4, 3. Teilaufgabe):
(das "quer" spare ich mir diesmal, wir rechnen im Restklassenring modulo 51)

-Die Ordnung von 25 ist : ?

Lösung: Ich habe mit der Euler'schen Phi Funktion die Ordnung des Restklassenrings bestimmt. Euler_Phi(51) = phi(7) * phi(17) = 2 * 16 = 32, das geht noch leicht im Kopf.

Die Ordnung muss also nun ein Teiler von 32 sein. Hier kommen 2,4,8,16 in Frage.
Ich prüfe nun durch
25^2 modulo 51 = 1 ?
25^4 modulo 51 = 1 ?
25^8 modulo 51 = 1 ? -> JA

Aber 25^8 im Kopf? Das kann doch nicht sein. Oder gibt es einen einfacheren Lösungsweg?

von fw » 19.02.08 13:25

Hallo Dominik,

DominikP hat geschrieben:25^2 modulo 51 = 1 ?
25^4 modulo 51 = 1 ?
25^8 modulo 51 = 1 ? -> JA

Aber 25^8 im Kopf? Das kann doch nicht sein. Oder gibt es einen einfacheren Lösungsweg?

Ja, den gibt es, und den habe ich in diesem Thread auch schon erwähnt, du kannst nämlich nach jedem Schritt bereits reduzieren (modulo rechnen).

$25^2 = 625 \equiv 13\ (mod\ 51)$
$25^4 = (25^2)^2 \equiv 13^2 \equiv 169 \equiv 16\ (mod\ 51)$
$25^8 = 25^4 \equiv 16^2 \equiv 256 \equiv 1\ (mod\ 51)$

Damit werden die Zahlen, die du im Kopf rechnen musst, deutlich kleiner. Das ganze beruht natürlich auf der Tatsache, dass aus $a \equiv b\ (mod\ n)$ folgt, dass auch $a^2 \equiv b^2\ (mod\ n)$ gilt. 32 selbst kommt übrigens auch als Ordnung in Frage (aber natürlich keine größeren Zahlen), nicht nur 2,4,8 und 16.

Gruss
Flo

infostudium.de

Forum zum Informatikstudium an der RWTH Aachen

[Diskrete] Restklassenring / Ordnung