Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » ggT, Nullteiler von Polynomen in Restklassen

ggT, Nullteiler von Polynomen in Restklassen

Universität / Fachhochschule

Gruppen

Körper

Polynome

Ringe

Algebraische Zahlentheorie

Primzahlen

Teilbarkeit

Tags: Algebraische Zahlentheorie, Euklid, ggT, Gruppen, Körper, modulo, polynom, Primzahl, Ring, Teilbarkeit

student11 aktiv_icon

00:33 Uhr, 03.12.2011

Ich habe wirklich lange versucht, doch mir fehlt sowohl das Verständnis der Theorie (bez. der allgemeinen Vorgehensweise) als auch für das Lösen einer konkreten Aufgabe.
Es geht darum, in einem gegebenen Ring GF(3)

[

x]mod(x^2+2) (Also die Menge aller Polynome

a (x),

die "kleiner" als

x^{2} + 2

sind, und Koeffizienten in GF(3)=

{

0,1,2} haben)
Dieser Ring hat 9 Elemente: GF(3)

[

x]mod(x^2+2)={0,

1, 2, x, 2 x, x + 1, 2 x + 1, x + 2, 2 x + 2}

.

Nun soll ich die Gruppe GF(3)*

[

x]mod(x^2+2) bestimmen, wobei die Gruppe mit

\cdot

so definiert ist, dass: für alle

a (x),

die in dieser Gruppe sind: ggT(a(x),

x^{2} + 2) = 1

.

ggT von Polynomen könnte man ja über Euklid bestimmen.. Das habe ich dann auch versucht.. Ich habe mir überlegt, dass 0 nicht in Frage kommen kann und auch 2 nicht geeignet ist.
Mit Euklid erhalte ich für

x :

(x^{2} + 2) = x \cdot x + 2

x = 2 x \cdot 2 + 0

- \to

ggt=2

für

2 x :

x^{2} + 2 = 2 x \cdot 2 x + 2

2 x = x \cdot 2 + 0

- \to

ggt=2

. .

. für die anderen nur noch Werte mit

x

drin, also lineare Polynome..

Nun stellt sich die Frage, ob das genügt, wenn ich als Rest einen konstanten Faktor (ein Polynom des Grads

0)

bekomme, oder ob ich wirklich ggT 1 bekommen muss, denn 1 erhalte ich mit Euklid nie. Mache ich einen grundlegenden Fehler?

Für mich wäre dann GF(3)*

[

x]..={1,

x, 2 x}

Als zweites ist die Aufgabe gegeben, eines dieser Elemente auszusuchen, und ein Inverses zu finden. Da es sich um eine Gruppe handelt, muss das ja für jedes Element der Fall sein.
1 trivial.

Das Inverse von

x,

hab ich mir gedacht, könnte man via Euklid berechnen (durch Rückwärtseinsetzen), doch das geht ja nicht, wenn ich nicht ggT 1 bekomme.. Durch Ausprobieren komme ich auch auf keine sinnvolle Lösung..

Ich habe versucht:

x*(ax+b)=t*(x^2+2)

+ 1

a \cdot x + b = t \cdot x^{2} + 2 t + 1

Doch diese Gleichung macht irgendwie auch keinen Sinn..

Mir wäre irgendwie Euklid noch sympathisch, war dieser Algorithmus in

Z

eine grosse Hilfe. Doch bei den Polynomen ist das irgendwie verwirrend. Es scheint nicht ein eindeutiger Rest zu geben, auch bei der Polynomdivision nicht?

Wäre froh für hilfreiche Tipps, denn auch mit Durchprobieren hat es nicht geklappt..
Stehe wohl auf der Leitung..

Vielen Dank für eure Hilfe.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Polynomfunktionen / ganzrationale Funktionen - Einführung
Raummessung
Rechnen mit Klammern
Teilbarkeit natürlicher Zahlen

hagman aktiv_icon

01:19 Uhr, 03.12.2011

g g T (2, x^{2} + 2) = 1

wegen

2 \cdot 2 + 0 \cdot (x^{2} + 2) = 1

.
Allgemeiner gedacht: Der ggT von

x^{2} + 2

und

a \cdot x + b

muss ja wohl ein Polynom

c \cdot x + d

sein.
Falls

c \neq 0,

hat letzteres die Nullstelle

- \frac{d}{c}

in GF(3), was also auch Nullstelle von

x^{2} + 2

sein müsste - Widerspruch! Also ist

c = 0

. Bekanntlch kann

d = 0

dann nicht mehr auftreten, also ist

d = 1

oder

d = 2

. Da 2 ein eEinheit ist, kann man dann ebensogut

d = 1

erreichen. Mithin ist

g g T (x^{2} + 2, a \cdot x + b)

für alle Polynome

a \cdot x + b

(außer dem Nullpolynom) 1.

Was ist das Inverse von x? Beachte

x \cdot x \equiv x \cdot x - (x^{2} + 2) = - 2 = 1

student11 aktiv_icon

08:47 Uhr, 03.12.2011

Hmm. Ja ok das hab ich mir gedacht, dass wenn die anderen beiden

(x, 2 x)

Elemente sind, dann muss 2 auch.
Aber kommt man irgendwie mit Euklid auch auf dieses Resultat? Muss der ggT effektiv 1 sein, oder genügt es, wenn man eine Konstante bekommt?
Das was du machst, leuchtet mir irgendwie schon ein, aber es ist irgendwie ein wenig "willkürlich", ich sehe noch keine wirkliche Strategie dahinter, ich möchte eine Vorgehensweise, die immer ohne Probleme funktioniert.. Gibt es sowas denn eigentlich?

hagman aktiv_icon

13:55 Uhr, 03.12.2011

Muss immer 1 herauskommen?
Nun ja. Eigentlich gibt es keinen echt "größten" gemeinsamen Teiler, wenn man gar keine vernünftige Größer-als-Relation hat. In GF(3) gilt ja beispielsweise nicht einmal

2 > 1,

denn durch Addition von 1 würde

0 > 2,

danach

1 > 0

folgen, zusammen also

2 > 1 > 0 > 2

munter im Kreis.
Allgemein ist der ggT nicht einfach ein Element des Ringes, sondern ein Ideal. Wenn man Glück hat, handelt es sich um ein Hauptideal, also eines, das man beschreiben kann als sämtliche Vielfache eines bestimmten Elementes. Nur hat man bei der Wahl dieses "bestimmten Elementes" eine gewisse Freiheit: Man kann statt

a

auch

u \cdot a

wählen, wenn

u

eine Einheit ist (also ein multiplikativ Inverses besitzt). Daher ist das von 1 erzeugte Ideal dasselbe wie das von 2 erzeugte.

student11 aktiv_icon

14:33 Uhr, 03.12.2011

Bei uns in der Defintion steht mit ggT=1, aber auch, dass in dem Sinne ein Polynom irreduzibel ist, wenn es nur durch konstante Faktoren und ein Vielfaches von sich selbst teilbar ist.. Da fliesst deine Aussage mit ein..

Also kann ich in jedem Fall Euklid anwenden, und falls ich deg(r(x))=0, wobei

r (x)

das Restpolynom ist, davon ausgehen, dass der ggT 1 ist, ausser wenn der Rest=0 ist, dann ist der ggT das teilende Polynom..

Also falls ich ggT(a(x),

b (x))

berechnen muss, wobei deg(a(x))>deg(b(x)), dann kann ich Polynomdivision machen.. (bzw. Euklid..)
Bleibt kein Rest, ist der ggT=b(x).
Bleibt ein konstanter Rest (nicht

0),

ist ggT=1?
Und bleibt ein grösserer Rest (mindestens linear), dann??

Hmm.. Ich versteh das immer noch nicht ganz..
Bei den ganzen Zahlen kann ich ja beispielsweise die Linearkombination rechnen, die den ggT darstellt, also ggT(a,b)=u*a+v*b, indem ich Euklid anwende. Ich habe dann für beispielsweise

17

und

97 :

97 = 5 \cdot 17 + 12

17 = 1 \cdot 12 + 5

12 = 2 \cdot 5 + 2

5 = 2 \cdot 2 + 1

2 = 2 \cdot 1 + 0

- \to

ggT=1

1 = 5 - 2 \cdot 2 = 5 - 2 \cdot (12 - 2 \cdot 5) = 5 \cdot 5 - 2 \cdot 12 = 5 \cdot (17 - 1 \cdot 12) - 2 \cdot 12 = 5 \cdot 17 - 7 \cdot 12 = 5 \cdot 17 - 7 \cdot (97 - 5 \cdot 17) = 40 \cdot 17 - 7 \cdot 97

Das Inverse könnte ja man dann dort rauslesen, also das Inverse von

17

bezüglich

Z 97

wäre dann

40,

40 \cdot 17 = 1

(modulo

97) .

.

Wenn ich das analog anwenden möchte für Körper/Ringe mit Polynomen müsste ich ja auch ggT=1 bekommen, oder?

denn nehme ich

x^{2} + 2 = x \cdot x + 2

x = 2 x \cdot 2 + 0

Dann wäre der ggT=2
und

2 = x^{2} + 2 - x \cdot x

Und das Inverse somit

- x,

was in GF(3)

2 x

entspricht.
Dann wäre nach dieser Theorie

2 x

das multiplikative Inverse von

x

(aber irgendwie ja mit 2 statt mit

1)

KONTROLLE:
Wenn ich dann

x \cdot (2 x)

rechne gibt das

2 x^{2},

was dividiert durch

x^{2} + 2

ja dann:

2 x^{2} : (x^{2} + 2) = 2

Rest 2

Aber das ist ja nicht, was ich wollte...???

Wo liegt mein Überlegungsfehler??

hagman aktiv_icon

15:41 Uhr, 03.12.2011

Für das Inverse solltest du dann doch genau 1 und nicht irgendeine Konstante heraus bekommen.

x \cdot x = x \cdot x + 2 + 1 \equiv 1 mod (x^{2} + 2)

student11 aktiv_icon

15:51 Uhr, 03.12.2011

Hmm.. diese Gleichung leuchtet ein.. Offensichtlicher könnte es eigentlich gar nicht sein..

Trotzdem komm ich irgendwie nicht los von Euklid..
Wieso geht denn das nicht? Kann ich mit Euklid denn gar nicht auf Rest 1 kommen? Müsste ich den Algorithmus noch weiter ziehen? Modifizieren?

Oder macht Euklid einfach keinen Sinn mit Polynomen?

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

947187

947054

	Status: nicht eingeloggt	Noch nicht registriert?