Primitive Elemente in GF(n) < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:40 Di 26.07.2011 | | Autor: | taiBsu |
| Aufgabe | | Prüfen Sie, ob die Zahlen 2, 3, 4 und 6 primitive Elemente in GF(11) sind. Stellen Sie für diejenigen dieser vier Zahlen, die primitiv sind, die Logarithmentafel auf. |
Hallo liebes Matheraum-Team,
ich schonwieder.
Ich bin jetzt so weit, dass ich mir so ne Tabelle gemacht habe, um das jeweilige Ergebnis von [mm] 2^n [/mm] mod 11 aufzuschreiben:
[mm]\begin{tabular}[ht]{ccccccccccc}\hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
\hline2^n & 1 & 2 & 4 & 8 & 5 & 10 & 9 & 7 & 3 & 6\\
\hline \end{tabular}[/mm]
Ich frage mich aber gerade, ob es noch eine andere Möglichkeit gibt, als erst von den Zahlen 3, 4 und 6 noch alle Potenzen auszurechnen und diese modulo 11 laufen zu lassen. Man bemerke, dass wir in der Prüfung keinen Taschenrechner benutzen dürfen.
Kann mir einer helfen?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:41 Di 26.07.2011 | | Autor: | felixf |
Moin!
> Prüfen Sie, ob die Zahlen 2, 3, 4 und 6 primitive Elemente
> in GF(11) sind. Stellen Sie für diejenigen dieser vier
> Zahlen, die primitiv sind, die Logarithmentafel auf.
>
> Hallo liebes Matheraum-Team,
> ich schonwieder.
> Ich bin jetzt so weit, dass ich mir so ne Tabelle gemacht
> habe, um das jeweilige Ergebnis von [mm]2^n[/mm] mod 11
> aufzuschreiben:
>
> [mm]\begin{tabular}[ht]{ccccccccccc}\hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
\hline2^n & 1 & 2 & 4 & 8 & 5 & 10 & 9 & 7 & 3 & 6\\
\hline \end{tabular}[/mm]
>
> Ich frage mich aber gerade, ob es noch eine andere
> Möglichkeit gibt, als erst von den Zahlen 3, 4 und 6 noch
> alle Potenzen auszurechnen und diese modulo 11 laufen zu
> lassen. Man bemerke, dass wir in der Prüfung keinen
> Taschenrechner benutzen dürfen.
> Kann mir einer helfen?
Ist $G$ eine Gruppe, so hat $g [mm] \in [/mm] G$ genau dann die Ordnung $n$, wenn gilt:
a) [mm] $g^n [/mm] = 1$;
b) [mm] $g^{n/p} \neq [/mm] 1$ fuer alle Primzahlen $p$, die $n$ teilen.
Hier suchst du nach Elementen der Ordnung $11 - 1 = 10$. Nach dem kleinen Fermat weisst du, dass [mm] $g^{10} [/mm] = 1$ gilt fuer jedes $g [mm] \in [/mm] GF(11) [mm] \setminus \{ 0 \}$. [/mm] Du musst also nur noch schauen, ob fuer $g$ auch [mm] $g^2 \neq [/mm] 1 [mm] \neq g^5$ [/mm] gilt: ist beides der Fall, so ist $g$ eine Primitivwurzel.
Und 4 brauchst du eigentlich garnicht anzuschauen: wenn 2 eine Primitivwurzel ist, dann ist $4 = [mm] 2^2$ [/mm] sicher keine, da der Exponent 2 nicht teilerfremd zur Ordnung 10 ist. Und falls 2 keine Primitivwurzel ist, dann insbesondere $4 = [mm] 2^2$ [/mm] ebenfalls nicht.
Und wenn du die Logarithmentafel fuer die erste Primitivwurzel (also hier: 2) gefunden hast, kannst du auch einfach mit Exponenten rechnen, um die restlichen Zahlen zu testen: du siehst z.B., dass $3 = [mm] 2^8$ [/mm] ist. Da 8 wieder nicht teilerfremd zu 10 ist, ist 3 also keine Primitivwurzel. Und $6 = [mm] 2^9$, [/mm] und da 9 teilerfremd zu 10 ist, ist 6 also eine Primitivwurzel.
Die Logarithmentabelle fuer 6 kannst du ebenfalls aus der fuer 2 ablesen: [mm] $6^k$ [/mm] hat den Exponent $9 [mm] \cdot [/mm] k$ modulo 10, und da $9 [mm] \equiv [/mm] -1$ ist, kannst du das somit sehr schnell ausrechnen (ansonsten ist's aber auch nicht schwer) und dann einfach die Elemente aus der Logarithmentafel von 2 ablesen.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:26 Mi 27.07.2011 | | Autor: | taiBsu |
Hallo Felix,
erstmal danke für die Antwort, aber leider ist mir noch sehr viel unklar, zum Beispiel, warum ich schauen muss, ob [mm] (g^2[/mm] [mm]\neq[/mm] 1 [mm] \neq g^5) [/mm] gilt?
Außerdem würde ich gerne wissen, warum die 3 KEINE Primitivwurzel (ich schätze, das ist das gleiche wie ein "primitives Element") ist, weil 8 NICHT teilerfremd ist, die 6 aber widerrum auch nicht, WEIL die 9 teilerfremd zur 10 ist? LG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:30 Mi 27.07.2011 | | Autor: | statler |
Guten Abend, naja Nachmittag!
> erstmal danke für die Antwort, aber leider ist mir noch
> sehr viel unklar, zum Beispiel, warum ich schauen muss, ob
> [mm](g^2[/mm] [mm]\neq[/mm] 1 [mm]\neq g^5)[/mm] gilt?
Wenn g [mm] \not= [/mm] 1 weder eine Untergruppe der Ordnung 2 noch eine der Ordnung 5 erzeugt, dann kann es nur noch die ganze Gruppe werden.
> Außerdem würde ich gerne wissen, warum die 3 KEINE
> Primitivwurzel (ich schätze, das ist das gleiche wie ein
> "primitives Element") ist, weil 8 NICHT teilerfremd ist,
> die 6 aber widerrum auch nicht, WEIL die 9 teilerfremd zur
> 10 ist? LG
3 ist [mm] 2^8 [/mm] (hier jedenfalls) und [mm] 3^2 [/mm] dann [mm] 2^{16} [/mm] = [mm] 2^{6}, [/mm] weil ja [mm] 2^{10} [/mm] = 1 ist. Die Potenzen von 3 sind also gerade die Potenzen von 2 mit geradem Exponenten, da fehlt die Hälfte der Gruppe und wird also so nicht erzeugt.
[mm] 2^9 [/mm] z. B. erzeugt die Gruppe: Wenn ich alle Potenzen bilde, kriege ich im Exponenten alle Vielfachen von 9 und also alle Reste modulo 10. Alles babyeierleicht.
Gruß aus HH-Harburg und Feierabend
Dieter
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:32 Mi 27.07.2011 | | Autor: | felixf |
Moin,
oder etwas abstrakter: das folgt alles im Wesentlichen aus folgender Aussage:
Ist $g [mm] \in [/mm] G$ ein Element der Ordnung $n$, so hat [mm] $g^m$ [/mm] die Ordnung [mm] $\frac{n}{ggT(n, m)}$.
[/mm]
LG Felix
|
|
|
|
