Gruppe - Generator < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | a) Der Generator g der Gruppe [mm] \IZ_{n}* [/mm] (Gruppe mit Multiplikation mod n, ohne die 0), erzeugt selber eine Gruppe <g>. Beweisen Sie!
b) In der Gruppe [mm] \IZ_{n}* [/mm] sind alle Elemente ausser 1 und n-1 Generatoren. Beweisen Sie! |
Die Gruppe [mm] \IZ_{n}* [/mm] ist folgendermassen zu verstehen:
Bsp: [mm] \IZ_{5}* [/mm] = {1, 2, 3, 4} (alle Zahlen von 0-5 die teilerfremd zu 5 sind)
Neutralelement: 1
Inverses 1: 1
Inverses 2: 3
Inverses 4: 4
Generator g: 2, 3
a) Wieso ist <g> eine Gruppe?
Der Generator g erzeugt eine Gruppe mit [mm] g^{n} [/mm] wobei n [mm] \in \IN.
[/mm]
Also ist <g> = [mm] {g^{1}, g^{2}, g^{3}...}.
[/mm]
Aber wie hängt das mit der Gruppe [mm] \IZ_{n}* [/mm] zusammen? Wieso sind alle <g>'s eine Gruppe? Muss man das nicht wieder beweisen (Neutralelement, Assoziativ, Inverses)?
b) 1 kann verständlicherweise kein Generator sein, da [mm] 1^{1}, 1^{2}, 1^{3}...etc. [/mm] immer 1 gibt und somit nicht alle Elemente erzeugt werden können!
Für n-1 gibt es einen bestimmten Satz, den ich aber nicht ganz verstehe.
(n-1) (n-1)
= [mm] n^{2} [/mm] - 2n + 1
[mm] n^{2} [/mm] ist teilbar durch n, 2n ist teilbar durch n, also bleibt nur die 1! Die 1 mod n ist immer 1! Also kann es kein Generator sein.
Wieso macht man (n-1) (n-1)? Nur weil es einmal die 1 gibt, heisst es nicht dass es immer die 1 geben muss, oder?
Ich versteh' das irgendwie einfach nicht...
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:21 Fr 31.08.2007 | | Autor: | trinkMilch |
Hi...
zu a)
Die Gruppe [mm]\IZ_{n}^{*}[/mm] ist ja die Menge [mm]\{ x \in \IZ{n} : \gcd(x,n) = 1 \}[/mm]
Für Gruppen [mm]\IZ_{p}^{*}[/mm] mit p = Prim ist dies ja die Menge
{1;2;3;...;p-1}
Wenn du nun ein Element aus dieser Gruppe nimmst. a [mm]\in \IZ_{p}^{*}[/mm] und rechnest [mm] a^{1}, a^{2}, a^{3} [/mm] ... usw entsteht immer eine Untergruppe.
Anhand eines Beispiels, welches direkt ein Gegenbeispiel für deinen Aufgabenteil b) ist
Gruppe [mm]\IZ_{7}^{*}[/mm] und a = 4
[mm] a^{0} [/mm] = 1 mod 4
[mm] a^{1} [/mm] = 4 mod 7
[mm] a^{2} [/mm] = 2 mod 7
[mm] a^{3} [/mm] = 1 mod 7 = [mm] a^{0}
[/mm]
Hier wird also eine Untergruppe erzeugt mit nur 3 Elementen... {1;4;2}
(Die Anzahl der Elemente der Untergruppen die erzeugt werden sind immer ein Teiler von (p-1) bzw. phi(n) )
und aus dieser Untergruppe kommt man halt nicht mehr raus...
man kann nun ein neues a wählen aus {1;4;2} aber immer wenn man
[mm] a^{x} [/mm] ausrechnet mit x [mm]\in \IN[/mm] Erhält man entweder dieselbe Menge {1;4;2} oder eine Untermenge die hier in diesem Fall nur ein Element haben kann, da 1 der einzige Teiler von 3 ist.
Prüfen:
a=1
[mm] 1^0 [/mm] = 1
[mm] 1^1 [/mm] = [mm] 1^0 [/mm] = 1
=> {1}
a=2
[mm] 2^0 [/mm] = 1
[mm] 2^1 [/mm] = 2
[mm] 2^2 [/mm] = 4
[mm] 2^3 [/mm] = [mm] 2^0 [/mm] = 1
=> {1;4;2}
a=4
[mm] 4^0 [/mm] = 1
[mm] 4^1 [/mm] = 4
[mm] 4^2 [/mm] = 2
[mm] 4^3 [/mm] = [mm] 4^0 [/mm] = 1
=> {1;4;2}
zu b)
wie oben gezeigt, wenn n=7 und alle zahlen zwischen 1 und n-1 generatoren seien sollen, dann muss 4 ja auch ein generator sein..
aber a = 4 erzeugt uns {1;4;2} und nicht {1;2;3;4;5;6}
zum verständnis
1 und (n-1) können keine generatoren sein...
[mm] 1^0 [/mm] = [mm] 1^1 [/mm] = [mm] 1^2 [/mm] = 1 mod n
also ´die Zahl 1 erzeugt uns immer eine Untergruppe mit nur einem Element: {1}
wenn a = (n-1)
[mm] a^{0} [/mm] = 1 mod n
[mm] a^{1} [/mm] = [mm] (n-1)^{1} [/mm] = n-1 mod n
[mm] a^{2} [/mm] = [mm] (n-1)^{2} [/mm] = [mm] n^{2} [/mm] - 2*n +1 = 1 mod n
also a= (n-1) erzeugt Untergruppe mit 2 Elementen: {1; n-1}
|
|
|
|
