ggT von Polynomen mit Euklidischen Algorithmus

09.07.2013, 21:13

Theend9219

ggT von Polynomen mit Euklidischen Algorithmus

Es gilt den ggT zu bestimmen

$\begin{eqnarray*} f(X) = X^{5}+X^{4}+X^{3}+X^{2}+X+1 \end{eqnarray*}$

und

$\begin{eqnarray*} g(X) = X^{4}-X^{3}-X+1 \end{eqnarray*}$

in $\begin{eqnarray*} \mathbb F_{2}[X] \end{eqnarray*}$

Meine Ideen: Dieser Körper hat ja nur die Elemente 0 und 1. Nun denke ich mir das ich mit Polynomdivision anfangen sollte:

$\begin{eqnarray*} f(X) = X^{5}+X^{4}+X^{3}+X^{2}+X+1 \end{eqnarray*}$ nach Überlegung wenn ich $\begin{eqnarray*} 1 \end{eqnarray*}$ einsetze erhalte ich $\begin{eqnarray*} f(1) = (1+1)+(1+1)+(1+1) = (0)+(0)+(0) = 0 \end{eqnarray*}$ , denn $\begin{eqnarray*} 1+1 \end{eqnarray*}$ ist in $\begin{eqnarray*} \mathbb F_{2}[X] \end{eqnarray*}$ ja $\begin{eqnarray*} 0 \end{eqnarray*}$ . Bei der Einsetzung mit 0 hätte ich rausbekommen $\begin{eqnarray*} f(0) = 0+0+0+0+0+1 = 0+1 = 1 \end{eqnarray*}$ . Jedoch findet sich mit $\begin{eqnarray*} f(1) \end{eqnarray*}$ , die Nullstelle des Polynoms. Also muss ich das Polynom einfach nur durch $\begin{eqnarray*} x \end{eqnarray*}$ teilen. Und erhalte: $\begin{eqnarray*} X^{4}+X^{3}+X^{2}+X^{1}+1+\frac{1}{x} \end{eqnarray*}$ , aber wie muss ich denn jetzt weiter machen?
Oder ich mache es ganz anders und teile f durch g mit jeweils den höchsten Koeffizienten.
$\begin{eqnarray*} \frac{x^{5}}{x^{4}} = x = q' \end{eqnarray*}$
Nun muss ich rechnen $\begin{eqnarray*} f-gq' \end{eqnarray*}$

$\begin{eqnarray*} =x^{5}+x^{4}+x^{3}+x^{2}+x+1 -(x*(x^{4}-x^{3}-x+1)) \end{eqnarray*}$
$\begin{eqnarray*} =2x^{4}+x^{3}+2x^{2}+1 \end{eqnarray*}$
Jetzt wieder das gleiche Spiel:
$\begin{eqnarray*} \frac{2x^{4}}{x^{4}} = 2 = q'' \end{eqnarray*}$ Dann wieder $\begin{eqnarray*} f-gq'' \end{eqnarray*}$
$\begin{eqnarray*} = 2x^{4}+x^{3}+2x^{2}+1-2(x^{4}-x^{3}-x+1) \end{eqnarray*}$
$\begin{eqnarray*} =3x^{3}+2x^{2}+2x-1 \end{eqnarray*}$

Jetzt kann ich schon aufhören, da der Grad von $\begin{eqnarray*} 3x^{3}+2x^{2}+2x-1 \end{eqnarray*}$ kleiner ist als der von g also erhalte ich
$\begin{eqnarray*} x(x^{4}-x^{3}-x+1)+2x^{4}+x^{3}+2x^{2}+1 \end{eqnarray*}$
da ich nun einen Rest erhalte, ist g kein Teiler von f
Weiss aber nicht ob das jetzt richtig ist ..
.. Liebe Grüße Shelly

09.07.2013, 23:35

lgrizu

Auf diesen Beitrag antworten »

RE: ggT von Polynomen mit Euklidischen Algorithmus
Warum ziehst du nicht einfach den euklidschen ALgorithmus durch?

Es ist zum Beispiel leicht zu sehen, dass

$\begin{eqnarray*} x^5+x^4+x^3+x^2+x+1=x \cdot (x^4+x^3+x+1)+(x^3+1) \end{eqnarray*}$

Und nun weiter...

09.07.2013, 23:39

Theend9219

Auf diesen Beitrag antworten »

RE: ggT von Polynomen mit Euklidischen Algorithmus
Entschuldigung, ... ich war gerade am editieren...

10.07.2013, 09:20

lgrizu

Auf diesen Beitrag antworten »

RE: ggT von Polynomen mit Euklidischen Algorithmus
Ich verstehe auch nicht ganz, was du da machst...

Im $\begin{eqnarray*} \mathbb F_2 \end{eqnarray*}$ ist 2=0

10.07.2013, 09:42

Theend9219

Auf diesen Beitrag antworten »

RE: ggT von Polynomen mit Euklidischen Algorithmus
Hey Igrizu, also muss ich für alle 2en eine 0 schreiben? Und ich hatte dort einfach versucht zu dividieren..mit rest

10.07.2013, 10:24

lgrizu

Auf diesen Beitrag antworten »

RE: ggT von Polynomen mit Euklidischen Algorithmus
Das ist ja auch richtig, bedenke aber, dass wir im $\begin{eqnarray*} \mathbb F_2 \end{eqnarray*}$ rechnen. Und da ist 1+1=0 und 1=-1, also die 1 selbstinvers.

10.07.2013, 15:42

Theend9219

Auf diesen Beitrag antworten »

RE: ggT von Polynomen mit Euklidischen Algorithmus
Okay, danke.
Dann würde ich es folgendermaßen machen:
$\begin{eqnarray*} f(x) = x^{5}+x^{4}+x^{3}+x^{2}+x+1 \end{eqnarray*}$
$\begin{eqnarray*} g(x) = x^{4}-x^{3}-x+1 \end{eqnarray*}$

also nochmal:
$\begin{eqnarray*} \frac{x^{5}}{x^{4}} = x \end{eqnarray*}$ also $\begin{eqnarray*} x^{5}+x^{4}+x^{3}+x^{2}+x+1-((x^{4}-x^{3}-x+1)\cdot x)= 2x^{4}+x^{3}+2x^{2}+1 \end{eqnarray*}$

$\begin{eqnarray*} \frac{2x^{4}}{x^{4}} = 2 \end{eqnarray*}$ dann wäre ich hier ja schon fertig .. weil ja nur die Elemente 0 und 1 enthalten sind, und ich dann für 2= 0 setze und erhalte:

$\begin{eqnarray*} 2x^{4}+x^{3}+2x^{2}+1-0 = 2x^{4}+x^{3}+2x^{2}+1 \end{eqnarray*}$
Liebe Grüße

10.07.2013, 20:01

lgrizu

Auf diesen Beitrag antworten »

RE: ggT von Polynomen mit Euklidischen Algorithmus

Zitat:

Original von Theend9219
Okay, danke.
Dann würde ich es folgendermaßen machen:
$\begin{eqnarray*} f(x) = x^{5}+x^{4}+x^{3}+x^{2}+x+1 \end{eqnarray*}$
$\begin{eqnarray*} g(x) = x^{4}-x^{3}-x+1 \end{eqnarray*}$

also nochmal:
$\begin{eqnarray*} \frac{x^{5}}{x^{4}} = x \end{eqnarray*}$ also $\begin{eqnarray*} x^{5}+x^{4}+x^{3}+x^{2}+x+1-((x^{4}-x^{3}-x+1)\cdot x)= 2x^{4}+x^{3}+2x^{2}+1 {\color{red}=x^3+1} \end{eqnarray*}$

Okay, wir haben also:

$\begin{eqnarray*} x^5+x^4+x^3+x^2+x+1=x \cdot (x^4+x^3+x+1)+(x^3+1) \end{eqnarray*}$

Nun weiter mit Euklid

Zitat:

Original von Theend9219
$\begin{eqnarray*} \frac{2x^{4}}{x^{4}} = 2 \end{eqnarray*}$ dann wäre ich hier ja schon fertig .. weil ja nur die Elemente 0 und 1 enthalten sind, und ich dann für 2= 0 setze und erhalte:

$\begin{eqnarray*} 2x^{4}+x^{3}+2x^{2}+1-0 = 2x^{4}+x^{3}+2x^{2}+1 \end{eqnarray*}$
Liebe Grüße

keine Ahnung, was du hier machst und warum du nur die 2 vor dem $\begin{eqnarray*} x^0 \end{eqnarray*}$ gleich 0 setzt, aber siehe oben...

10.07.2013, 20:57

Theend9219

Auf diesen Beitrag antworten »

RE: ggT von Polynomen mit Euklidischen Algorithmus
Wie kommst du auf dieses $\begin{eqnarray*} x^{3}+1 \end{eqnarray*}$ ??

10.07.2013, 21:10

lgrizu

Auf diesen Beitrag antworten »

RE: ggT von Polynomen mit Euklidischen Algorithmus
Polynomdivision und die Eigenschaft, dass 1+1=0 ist, das habe ich aber auch schon mehrfach gesagt.....

10.07.2013, 21:54

Theend9219

Auf diesen Beitrag antworten »

RE: ggT von Polynomen mit Euklidischen Algorithmus
Hey Igrizu,

tut mir leid aber ich kann hier leider nicht weiter machen ..., ich komme nicht auf diese $\begin{eqnarray*} x^{3}+1 \end{eqnarray*}$ .. was ist denn der Divisor deiner Polynomdivision? Bei mir wäre der Leitkoeffizient für die Polynomdivision ja die 1.. weil $\begin{eqnarray*} 1+1+1+1+1+1 = 0 \end{eqnarray*}$ und nun würde ich mit Polynomdivision $\begin{eqnarray*} x^{5}+x^{4}+x^{3}+x^{2}+x+1 : (x-1) \end{eqnarray*}$ da komm ich aber auch nicht auf dein Ergebnis ... tut mir leid ..

11.07.2013, 00:01

lgrizu

Auf diesen Beitrag antworten »

RE: ggT von Polynomen mit Euklidischen Algorithmus
Du sollst doch den euklidschen Algorithmus anwenden, oder sehe ich etwas nicht?

Der Funktioniert doch folgendermaßen zur Bestimmung des ggT von $\begin{eqnarray*} a \end{eqnarray*}$ und $\begin{eqnarray*} r_0 \end{eqnarray*}$

$\begin{eqnarray*} a=q_1 \cdot r_0+r_1 \end{eqnarray*}$

$\begin{eqnarray*} r_0=q_2 \cdot r_1+r_2 \end{eqnarray*}$

...

$\begin{eqnarray*} r_{n-1}=q_{n+1} \cdot r_n+0 \end{eqnarray*}$

Dann ist $\begin{eqnarray*} r_n \end{eqnarray*}$ der gesuchte ggT.

Wir haben:

$\begin{eqnarray*} a=x^5+x^4+x^3+x^2+x+1 \end{eqnarray*}$ und $\begin{eqnarray*} r_0=x^4+x^3+x+1 \end{eqnarray*}$

Bedenke zuerst einmal, dass wir im $\begin{eqnarray*} \mathbb F_2 \end{eqnarray*}$ rechnen, also -1=1 gilt und deshalb alle Koeffizienten, die nicht 0 sind eins sein müssen, wir also erst mal nur positive Vorzeichen haben und das ferner gilt 2=0.

Jetzt Polynomdivision mit Rest:

$\begin{eqnarray*} (x^5+x^4+x^3+x^2+x+1) : (x^4+x^3+x+1)=x \text{ Rest } x^3+1 \end{eqnarray*}$

Das sollte eigentlich klar sein, aber da die Frage aufgetaucht ist, einmal ausführlich:

$\begin{eqnarray*} ({\color{red}x^5}+x^4+x^3+x^2+x+1) : ({\color{red}x^4}+x^3+x+1)=x \end{eqnarray*}$
$\begin{eqnarray*} -(x^5+x^4+x^2+x) \end{eqnarray*}$
------------------------------------
$\begin{eqnarray*} x^3+1 \end{eqnarray*}$

Nun haben wir also

$\begin{eqnarray*} a=x^5+x^4+x^3+x^2+x+1 \end{eqnarray*}$

$\begin{eqnarray*} r_0=x^4+x^3+x+1 \end{eqnarray*}$

$\begin{eqnarray*} r_1=x^3+1 \end{eqnarray*}$

$\begin{eqnarray*} q_1=x \end{eqnarray*}$

14.07.2013, 14:41

Theend9219

Auf diesen Beitrag antworten »

RE: ggT von Polynomen mit Euklidischen Algorithmus
Ah! Dankeschön. Hätte ich man auch diese untereinanderschreibweise für die Division verwendet. Ich hatte immer versucht jeweils die höchsten Exponenten von f mit g zu dividieren. Aber jetzt ist es mir klar..

Liebe Grüüüüße!

Neue Frage »

Antworten »

ggT von Polynomen mit Euklidischen Algorithmus

Verwandte Themen