Algebra/Körper

baje · Full Member Anmeldungsdatum: 25.06.2006 Beiträge: 117

Kann mir jemand helfen?

Ich muss einen Körper K mit 25 Elementen finden:

Da habe ich K= F_5^2 gefunden, der isomorph zu Z_5/(x^2+x+1) ist.

Nun muss ich ein Element x in K finden, das die multiplikative K* erzeugt.

Die multiplikative Gruppe Z_5^2 * hat aber, mit der Eulerschen Funktion berechnet, nur 20 Elemente.

Kann mir jemand sagen, wie ich zu dem erzeugenden x komme und eventuell wo mein Denkfehler liegt.

Danke vielmals
baje

M_Hammer_Kruse · Verfasst am: 09 Feb 2010 - 12:40:26 Titel:

Ich kann Deine Notation nicht deuten, aber ich vermute, daß Deine multiplikative Verknüpfung nicht nullteilerfrei ist, wegen 25|(k*5)*(l*5).
Dann wäre sie ungeeignet, um eine Körper zu konstruieren.

Gruß, mike
_________________
√∞≠≤≥±≈∫≡¼⅓½⅔¾∧∨¬∈⊂⊄∩∪∂
αβγδεηκλμνπρσφωΓΔΘΛΣ

baje · Full Member Anmeldungsdatum: 25.06.2006 Beiträge: 117

Ja, ist nicht so einfach mit der Notation.

K ist der Körper F mit Charakteristik 5^2 und 25 Elementen

Z_5[X]/(x^2+x+1) und für die multiplikative Gruppe (Z/5Z*Z/5Z)* wäre korrekt.

Was ist jetzt genau nicht nullteilerfrei?

M_Hammer_Kruse · Verfasst am: 09 Feb 2010 - 12:57:07 Titel:

Ich verstehe die Notation immer noch nicht. Aber ich nehme an, das meint den Polynomring der Polynome über dem endlichen Körper mit 5 Elementen, faktorisiert nach x²+x+1 und als multiplikative Gruppe die Restklassen modulo 25?

Wenn es sich um die Restklassen modulo 25 handelt, dann ist das keine multiplikative Gruppe, weil die Elemente 5, 10, 15 und 20 Nullteiler sind.

Im Übrigen brauchst du für einen Körper mit 25 Elementen eine multiplikative Gruppe mit 24 Elementen, weil die Null dabei nicht mitspielt.

Gruß, mike
_________________
√∞≠≤≥±≈∫≡¼⅓½⅔¾∧∨¬∈⊂⊄∩∪∂
αβγδεηκλμνπρσφωΓΔΘΛΣ

baje · Full Member Anmeldungsdatum: 25.06.2006 Beiträge: 117

ja, du hast richtig angenommen.

gut, dann verstehe ich da eindeutig etwas nicht ganz. Confused

kannst du mir da einen tipp geben, wie ich da am besten vorgehe? (um den passenden Körper und das erzeugende Element zu finden)

M_Hammer_Kruse · Verfasst am: 09 Feb 2010 - 15:28:47 Titel:

Überlege Dir zunächst einmal, welche Elemente der Körper überhaupt hat:

Die Polynome über F_5 haben die Form ax^4+bx³+cx²+dx+e, wobei a bis e aus {0,..,5} sind. Höhere Potenzen als 4 kann es nicht geben, weil x^5=x ist. Du faktorisierst diesen Polynomring, indem Du nur die Restklassen modulo x²+x+1 betrachtest.

Wenn Du (z. B. durch Polynomdivision) den Rest berechnest, den ein Polynom ax^4+bx³+cx²+dx+e bei Division durch x²+x+1 hat, denn bekommst Du (d+a-c)*x+(e+b-c). Es ist deutlich: Die Reste sind natürlich die Polynome αx+β mit α,β aus {0,..,5}. Und das sind genau 25 unterschiedliche Elemente.

Damit hast du auch schon deinen Körper, einschließlich der Multiplikation.

Denn diese Polynome mit zwei Koeffizienten kannst Du als Repräsentanten der Restklassen hernehmen und miteinander multiplizieren. Das ist am Beispiel leichter, als es allgemein vorzurechnen:

Das Produkt von (3x+4) und (x+1) ist 3x²+7x+4. Das ist leider kein Polynom mit zwei Koeffizienten, aber Dich interessieren ja nur die Restklassen. 3x²+7x+4 gehört zu selben Klasse wie sein Rest bei Division durch x²+x+1. Und der ist 4x+3.
Damit hast Du (3x+4)*(x+1)=(4x+1).

Allgemein (ax+b)*(cx+d)=acx²+(ad+bc)x+bd=(ad+bc-ac)x+(bd-ac).

So kannst Du die vollständige Multiplikationstabelle aufstellen.

Gruß, mike
_________________
√∞≠≤≥±≈∫≡¼⅓½⅔¾∧∨¬∈⊂⊄∩∪∂
αβγδεηκλμνπρσφωΓΔΘΛΣ

baje · Full Member Anmeldungsdatum: 25.06.2006 Beiträge: 117

Vielen Dank, warst mir eine grosse Hilfe.

In diesem Fall ist ja Z_5[X]/(x^2+x+1) der richtige Körper, oder?
Er ist nur nicht zu (Z/5Z*Z/5Z)* isomorph. das sehe ich jetzt auch, denn der hat ja nur 16 Elemente...

nochmals danke
Grüsse
Baje

Annihilator · Verfasst am: 09 Feb 2010 - 19:11:31 Titel:

Z_5[x]/(x²+x+1) ist isomorph zu F_25, weil x²+x+1 irreduzibel in Z_5[x] ist; es stimmt also. Die additive Gruppe von F_25 ist isomorph zu (Z_5, +) × (Z_5, +) und die multiplikative zu (Z_24, +), also ist sie zyklisch und es gibt einen Erzeuger. Den zu finden, ist aber nicht einfach. Bin mir nicht sicher, aber ich glaube, dafür gibt es keine effektive Lösungsstrategie. x ist zum Beispiel schon mal kein Erzeuger, da x³ kongruent zu 1 ist.

@M_Hammer_Kruse
Nicht den Ring der Polynome mit dem Ring der Polynomfunktionen verwechseln. Beim zweiten gilt x⁵ = x, aber im ersten nicht, da es einfach verschiedene Polynome sind.
_________________
Schnauze voll von Error 500 und co?
bildungs-foren.de

baje · Full Member Anmeldungsdatum: 25.06.2006 Beiträge: 117

Vielen Dank

hat mir sehr geholfen... Razz

Inri · Newbie Anmeldungsdatum: 10.02.2010 Beiträge: 9

Annihilator · Verfasst am: 10 Feb 2010 - 11:55:10 Titel:

Nuja, man kann eigentlich jede natürliche Zahl hinschreiben, solange man mit n eigentlich [n] meint, also die Äquivalenzklasse von n bezüglich der Relation {(x, y) € N² | x mod 5 = y mod 5}. Aber ja, du hast natürlich Recht, dass die 5 überflüssig ist, da sie kongruent zu 0 ist, bzw [5] = [0] gilt.
_________________
Schnauze voll von Error 500 und co?
bildungs-foren.de

Inri · Newbie Anmeldungsdatum: 10.02.2010 Beiträge: 9

M_Hammer_Kruse · Verfasst am: 10 Feb 2010 - 17:01:17 Titel:

Kann man. Aber tatsächlich ist es ein Flüchtigkeitsfehler von mir, und es sollte {0,...,4} heißen.

Danke für den Hinweis auf die saubere Unterscheidung zwischen Polynom und Polynomfunktion. Auch da war ich ein wenig unscharf.

Wenn man die Polynome f(x)=αx+β, welche die Elemente des Körpers repräsentieren, kurzerhand mit (αβ) bezeichnet, dan ist (12) ein erzeugendes Element der multiplikativen Gruppe. Und natürlich alle Potenzen von (12), bei denen der Exponent zu 24 teilerfremd ist.

Allerdings habe ich das auch nur Aufstellen der Verknüpfungstabelle und durch aufsuchen der Ordung einer Reihe von Elementen herausbekommen. Wie man dem mit einem systematischen und schlagkräftigen Algorithmus beikommen kann, weiß ich nicht.

Gruß, mike
_________________
√∞≠≤≥±≈∫≡¼⅓½⅔¾∧∨¬∈⊂⊄∩∪∂
αβγδεηκλμνπρσφωΓΔΘΛΣ

baje · Full Member Anmeldungsdatum: 25.06.2006 Beiträge: 117

Jetzt habe ich aber doch noch eine Frage:

Wenn ich einen Körper mit 16 Elementen suche, finde ich Z_2[x]/(x^4+x+1) isomorph zu F_16. Die additive Gruppe ist isomorph zu Z/4Z x Z/4Z und die multiplikative zu F_15*

Mike, mit deiner Methode (Polynomdivison) komme ich aber hier nicht weiter, weil (x^4+x+1) ja grösser ist als ax+b. Wie bestimme ich hier die Elemente. Und ist das überhaupt notwendig um zu zeigen, dass der Körper 16 Elemente hat?

M_Hammer_Kruse · Verfasst am: 11 Feb 2010 - 11:33:34 Titel:

Z_2[x]/(x^4+x+1) ist also der Polynomring der Polynome über dem endlichen Körper ({0,1},+,*)?

Wenn Du den nach x^4+x+1 faktorisierst, dann bekommst du alle Restklassen, die durch die Polynome ax³+bx²+cx+d repräsentiert werden. Das sind tatsächlich 16 Stück, weil a, b, c und d je zwei Werte annehmen können.

Wenn Du hier die multiplikativen Eigenschaften untersuchen willst, mußt Du z. B. das Produkt von ax³+bx²+cx+d und ex³+fx²+gx+h ermitteln und dessen Rest bei der Division durch x^4+x+1 bestimmen. Das ist natürlich auch ein Polynom dritten Grades.

Polynome der Form ax+b spielten als Repräsentanten der Elemente nur in dem anderen Körper eine Rolle, weil Du dort nach x²+x+1 faktorisiert hast.

Gruß, mike
_________________
√∞≠≤≥±≈∫≡¼⅓½⅔¾∧∨¬∈⊂⊄∩∪∂
αβγδεηκλμνπρσφωΓΔΘΛΣ

baje · Full Member Anmeldungsdatum: 25.06.2006 Beiträge: 117

Sorry, ich habe es immer noch nicht ganz verstanden.
Wieso nimmst du ein Polynom 3. Grades? und wie soll ich x^4+x+1 faktorisieren, wenn es doch irreduzibel ist?

M_Hammer_Kruse · Verfasst am: 11 Feb 2010 - 12:08:43 Titel:

Deine Schwierigkeit beruht offenbar auf einem Mißverständnis des Begriffs Faktorisierung.

Du sollst nicht "das Polynom ... faktorisieren", sondern "den Polynomring nach dem Polynom ... faktorisieren". Das bedeutet hier: die Restklassen bilden, die sich bei der Division durch dieses Polynom bilden.

Diese Bedeutung des Begriffs entstammt der Gruppentheorie, wo man von Faktorisierung einer Gruppe nach einem Normalteiler spricht. Dabei werden die n Elemente einer endlichen Gruppe in j gleichgroße Nebengruppen sortiert, die wie der Normalteiler je k Elemente haben. Die Gruppe besitzt dann n=l*k Elemente. Daher "Faktorisierung".

Gruß, mike
_________________
√∞≠≤≥±≈∫≡¼⅓½⅔¾∧∨¬∈⊂⊄∩∪∂
αβγδεηκλμνπρσφωΓΔΘΛΣ

Annihilator · Verfasst am: 11 Feb 2010 - 15:32:11 Titel:

F_16 ist isomorph zu Z_2[x]/(x^4+x+1). Da geh ich mit. Allerdings ist die additive Gruppe isomorph zu (Z_2, +)^4 = (Z_2, +) × (Z_2, +) × (Z_2, +) × (Z_2, +) und die multiplikative Gruppe zu (Z_15, +) und nicht zu F_15, weil es F_15 gar nicht gibt (F_15* auch nicht).
_________________
Schnauze voll von Error 500 und co?
bildungs-foren.de

baje · Full Member Anmeldungsdatum: 25.06.2006 Beiträge: 117

Ja, das ist mit der multiplikativen Gruppe ist mir eigentlich klar. Hab da wohl zu schnell eingetippt.

habe aber noch immer nicht den Durchblick bei dem Faktorisieren...

Annihilator · Verfasst am: 11 Feb 2010 - 16:12:33 Titel:

Mal ganz grob die allgemeine Variante:

Wenn f eine n-stellige Operation einer algebraischen Struktur S ist, dann ist die n-stellige Operation g der zugehörigen Faktor-Struktur S/H definiert als:

g([x_1], [x_2], ..., [x_n]) = [f(x_1, x_2, ..., x_n)]

Wobei [s] die Klasse von s bezüglich der Kongruenzrelation H ist.

Wenn du also als Struktur den Ring (Z_2[x], +, ·) hast, dann wäre M = {(p, q) € Z_2[x] × Z_2[x] | p mod (x⁴+x+1) = q mod (x⁴+x+1)} eine Kongruenzrelation dieses Rings. In der Faktorstruktur (Z_2[x]/M, #, *) wird dann gerechnet:

[p] # [q] = [p + q]
[p] * [q] = [p · q]

Das praktische an Restklassenringen (wie dies einer ist): Man kann auch wie folgt rechnen:

[p] # [q] = [(p + q) mod (x⁴+x+1)]
[p] * [q] = [(p · q) mod (x⁴+x+1)]

Es stellt sich heraus, dass alle Äquivalenzklassen sich durch Polynome repräsentieren lassen, deren Grad kleiner als 4 ist, also alle der Form (ax³+bx²+cx+d), wie Mike schon schrieb.

Man schreibt bei Resklassenringen selten die Relation selbst hin, sondern hier eben Z_2[x]/(x⁴+x+1).
_________________
Schnauze voll von Error 500 und co?
bildungs-foren.de

baje · Full Member Anmeldungsdatum: 25.06.2006 Beiträge: 117

Super!! Danke.

So, jetzt habe ich's verstanden: f=x^4+x+1 und (x^4+x)=1 mod f

1=1 mod f
x=x mod f
...

x^5=(x+1) mod f

usw.

Danke nochmal für die ausführliche Erklärung.

Grüsse
Barbara

Annihilator · Verfasst am: 11 Feb 2010 - 17:55:07 Titel:

x^5 ist nicht kongruent zu x+1, sondern zu x²+x, denn x^5 = (x) · (x^4+x+1) + (x²+x).
_________________
Schnauze voll von Error 500 und co?
bildungs-foren.de

baje · Full Member Anmeldungsdatum: 25.06.2006 Beiträge: 117

Rechenfehler, mist!!

Ist mir jetzt überall klar.

Also noch ein Beispiel: x^6=(x^3+x^2) mod f

und stimmt es, dass x^4=(x+1) mod f ist? Da x^4=f-(x+1)

Annihilator · Verfasst am: 11 Feb 2010 - 19:06:00 Titel:

Ja, das haut hin.
_________________
Schnauze voll von Error 500 und co?
bildungs-foren.de