Erzeug. Elemte in Restklassen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:19 Mi 18.03.2009 | | Autor: | Oli12 |
| Aufgabe | Bestimmen Sie erzeugende Elemente in den primen Restklassengruppen
a) [mm] (\IZ/\IZ_{625})^{\times}
[/mm]
b) [mm] (\IZ/\IZ_{71^{2}})^{\times}
[/mm]
c) [mm] (\IZ/\IZ_{2*71^{2}})^{\times}
[/mm]
Hinweis: [mm] [7]_{71} [/mm] ist erzeugendes Element in [mm] (\IZ/\IZ_{71})^{\times} [/mm] |
Hi Leute,
Ich hab keine Ahnung wie ich das machen soll. Im Prinzip könnte ich ja alle Elemente der Restklassengruppen bestimmen und damit dann zeigen ob es erzeugende Elemente sind. Aber da sitz ich ja Jahre dran... gibt es denn irgendeine super schnelle (einfache) Methode mit der man zeigen kann, ob es ein erz. Element ist oder nicht?
Eine Komillitonin hat gemeint, alleine die Gruppe [mm] (\IZ/\IZ_{625})^{\times} [/mm] hat schon [mm] 5^{4}-5^{3} [/mm] = 125 Elemente... stimmt das denn überhaupt?
Bitte um Hilfe!
Danke,
Gruß
Oli
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:06 Fr 20.03.2009 | | Autor: | felixf |
Hallo Oli!
> Bestimmen Sie erzeugende Elemente in den primen
> Restklassengruppen
> a) [mm](\IZ/\IZ_{625})^{\times}[/mm]
> b) [mm](\IZ/\IZ_{71^{2}})^{\times}[/mm]
> c) [mm](\IZ/\IZ_{2*71^{2}})^{\times}[/mm]
>
> Hinweis: [mm][7]_{71}[/mm] ist erzeugendes Element in
> [mm](\IZ/\IZ_{71})^{\times}[/mm]
>
> Hi Leute,
> Ich hab keine Ahnung wie ich das machen soll. Im Prinzip
> könnte ich ja alle Elemente der Restklassengruppen
> bestimmen und damit dann zeigen ob es erzeugende Elemente
> sind.
Ja, das ist eine Moeglichkeit. Allerdings nicht die beste, wie du selber bemerkst 
> Aber da sitz ich ja Jahre dran... gibt es denn
> irgendeine super schnelle (einfache) Methode mit der man
> zeigen kann, ob es ein erz. Element ist oder nicht?
Wenn du weisst, wieviele Elemente [mm] $(\IZ/\IZ_n)^\times$ [/mm] hat (sagen wir mal $m$), dann kannst du so vorgehen, um zu gucken, ob ein Element $a$ ein erzeugendes Element ist:
1) Seien [mm] $p_1, \dots, p_t$ [/mm] alle Primzahlen, die $m$ teilen.
2) Berechne [mm] $a^{m / p_i} \mod{n}$; [/mm] ist dies 1 fuer ein $i$, so ist $a$ kein erzeugendes Element.
3) Ist [mm] $a^{m / p_i}$ [/mm] niemals 1 modulo $n$ (fuer alle $i$), so ist $a$ ein erzeugendes Element.
Das geht schonmal viel schneller :)
Jetzt gibt es noch ein paar Fakten / Tricks die du eventuell kennst oder nicht kennst, die aber sehr helfen:
a) Ist $a$ ein Erzeuger von [mm] $(\IZ/\IZ_p)^\times$, [/mm] so ist $a$ oder $a + p$ ein Erzeuger von [mm] $(\IZ/\IZ_{p^2})^\times$.
[/mm]
(Ich erinnere mich nicht 100%ig an die Aussage, aber so in etwa muesste sie stimmen. Zumindest sind $a$ und $a + p$ zwei Kanidaten die du mal testen kannst.)
b) Ist $a$ ein Erzeuger von [mm] $(\IZ/\IZ_n)^\times$ [/mm] und ist $n$ ungerade, so ist $a$ oder $a + n$ ein Erzeuger von [mm] $(\IZ/\IZ_{2 n})^\times$ [/mm] -- naemlich genau der ungerade von den beiden Werten.
> Eine Komillitonin hat gemeint, alleine die Gruppe
> [mm](\IZ/\IZ_{625})^{\times}[/mm] hat schon [mm]5^{4}-5^{3}[/mm] = 125
> Elemente... stimmt das denn überhaupt?
Ja, das stimmt.
Wenn $n$ und $m$ teilerfremd sind, so hat [mm] $(\IZ/\IZ_{n m})^\times$ [/mm] gerade [mm] $|(\IZ/\IZ_n)^\times|$ [/mm] mal [mm] $|(\IZ/\IZ_m)^\times|$ [/mm] Elemente (das zeigt man z.B. mit dem chinesischen Restsatz), und [mm] $(\IZ/\IZ_{p^n})^\times$ [/mm] hat [mm] $p^n [/mm] - [mm] p^{n - 1}$ [/mm] Elemente (das zeigt man durch ein Abzaehlargument: es gibt genau [mm] $p^{n-1}$ [/mm] Elemente in [mm] $\{ 0, 1, \dots, p^n - 1 \}$, [/mm] die nicht teilerfremd zu [mm] $p^n$ [/mm] sind).
Damit kannst du die Anzahl der Elemente in [mm] $(\IZ/\IZ_n)^\times$ [/mm] ausrechnen fuer jedes $n$, solange du die Primfaktorzerlegung von $n$ bestimmen kannst.
Ich hoffe damit kommst du jetzt weiter :)
LG Felix
|
|
|
|
