Primitivwurzeln < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:58 Di 11.10.2005 | | Autor: | Kudi |
Hallo!
Wie bestimmt man sämtliche Primitivwurzeln modulo 25?
Ich weiß zum Beispiel, dass 2,3 und 8 zu diesen Primitivwurzeln gehöhren. Aber warum?
Und wie berechnet man modulo 25 verschiedene Lösungen x [mm] \in \IZ [/mm] von
[mm] x^{7} [/mm] =-11 (mod 25)? Das hat doch auch was mir den Primitivwurzeln zu tun, oder?
Vielen Dank für eure Hilfe
und viele Grüße
|
|
| |
|
Hallo Martin,
ich bin mir über den Begriff "Primitivwurzel" nicht ganz im klaren, aber aus dem Kontext müsste es darum gehen:
Der Ring mod 25 hat Nullteiler: alle Vielfache von 5 (das sind 4 Stück).
Der Rest ist invertierbar, bildet also eine multiplikative Untergruppe.
Jetzt sind 2, 3, 8 erzeugende Elemente dieser Untergruppe:
[mm] 2^{20} [/mm] = [mm] 3^{20} [/mm] = [mm] 8^{20} [/mm] = 1 mod 25, d.h. die Untergruppe der fehlenden 20 Elemente lässt sich durch Potenzen einer "Primitivwurzel" darstellen. Damit ist auch klar,dass die gesuchte Lösung von [mm] x^{7} [/mm] = -11 sich auf jede Primitivwurzel zurückführen lässt durch z.B.
[mm] (2^{z})^{7} [/mm] = -11 = 14 = [mm] 2^{6} [/mm] , mit [mm] 2^{z} [/mm] = x, also
[mm] 2^{7z-6} [/mm] = 1 bzw. 7z-6 = 0 mod 20.
Du kannst sozusagen den Logarithmus ziehen.
Daraus folgt z = 18 und x = 19 und [mm] x^{7} [/mm] = -11.
Grüße, Richard
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:52 Mi 12.10.2005 | | Autor: | Kudi |
Hallo!
Zunächst mal vielen Dank für deine Antwort. Aber leider ist mir nicht alles klar. Wieso muss ich zum Beispiel 2 ^{20} =1 mod 25 berechnen? Ist der Exponent immer 20?
Ich sehe auch den Zusammenhang zur Lösung von [mm] x^{7} \equiv-11(mod25) [/mm] nicht.
Viele Grüße
|
|
|
| |
|
Hallo Martin,
"primitive Wurzel" und "Erzeugende" ist (vermutlich) dasselbe: da musst Du Dich etwas in Algebra schlaumachen. Jetzt nur soviel:
Bei endlichen multiplikativen Gruppen gibt es sog. zyklische Untergruppen, die von der Form [mm] a^{n} [/mm] zu einer "Erzeugenden" a gebildet werden. Wenn gleich die ganze Gruppe von einem Element erzeugt wird, d.h.: für jedes x der Gruppe gibt es ein n [mm] \in [/mm] IN mit x = [mm] a^{n}, [/mm] dann ist sie zyklisch erzeugt (und abelsch).
Bei Ringen mod [mm] p^{k} [/mm] mit Primzahl p gibt es [mm] (p-1)p^{k-1} [/mm] invertierbare Elemente, also in Deinem Beispiel 20 = 4*5, die eine zyklische Untergruppe bilden. In Deinem Fall werden also die invertierbaren Elemente zyklisch erzeugt (20 + 5 Nullteiler ergibt 25). Da [mm] 2^{20} [/mm] = 1 ist, aber [mm] 2^{10} [/mm] = -1 (nachrechnen!) ist 2 Erzeugende (und 3 und 8 auch), denn für jeden Exponenten 0 [mm] \le [/mm] n < 20 ergibt [mm] 2^{n} [/mm] ein anderes Element der Untergruppe, die aber selbst nur 20 Elemente hat. D.h: Du kannst alle Elemente der invertierbaren Gruppe durch Potenzen von 2 darstellen (oder von 3 oder 8 etc.).
Da die Gleichung [mm] x^{7} [/mm] = -11 (-11 ist kein Vielfaches von 5, also invertierbar) nur auf dieser Gruppe gelöst werden kann (auch x muss dazu gehören) kannst Du die Gleichung in eine Exponentengleichung zur Basis 2 verwandeln:
Statt [mm] x^{7} [/mm] für alle x der Untergruppe durchzurechnen, ist es schneller, alle [mm] 2^{n} [/mm] zu bestimmen (vor allem, wenn man noch mehr Gleichungen auf dem Ring zu lösen hat und er nicht bloß 25 Elemente hat, sondern sehr viel mehr) und dann eine Gleichung der Form mx + b = 0 mod ord(Untergruppe) zu lösen, also hier 7z-6 = 0 mod 20.
Hoffentlich ist's jetzt etwas klarer, und wenn Du eine schnellere Lösung findest, bin ich sehr interessiert!
Gruß Richard
|
|
|
|
