Inverse eines Polynoms

12.06.2009, 18:32

mathestudi

Auf diesen Beitrag antworten »

Inverse eines Polynoms

Hallo,

ich habe ein Problem mit folgender Aufgabe:

Berechnen Sie das Inverse von $\begin{eqnarray*} X^2+1 \end{eqnarray*}$ modulo dem Polynom $\begin{eqnarray*} X^4+3 \end{eqnarray*}$ in $\begin{eqnarray*} \mathbb F_5[X] \end{eqnarray*}$ .

Meine Überlegungen soweit:

$\begin{eqnarray*} K=\mathbb F_5[X] \end{eqnarray*}$ , $\begin{eqnarray*} f(x)=X^4+3 \end{eqnarray*}$ ,
$\begin{eqnarray*} \mathbb F_5[X]/(f)=\left\{\sum_{i=0}^3~a_ix^i | a_i \in \left\{0,1,2,3,4\right\}\right\}=a_3x^3+a_2x^2+a_1x+a_0 \end{eqnarray*}$

Inverse zu $\begin{eqnarray*} X^2+1 \end{eqnarray*}$ in $\begin{eqnarray*} \mathbb F_5[X]/(f) \end{eqnarray*}$ :
$\begin{eqnarray*} 1 \equiv \left(X^2+1\right) \cdot \left(b_0+b_1X+b_2X^2+b_3X^3\right) mod \left(X^4+3, 5\right) \end{eqnarray*}$
$\begin{eqnarray*} \equiv \left(b_0+b_1X+(b_0+b_2)X^2+(b_1+b_3)X^3+b_2X^4+b_3X^5\right) mod \left(X^4+3, 5\right) \end{eqnarray*}$

Es gilt: $\begin{eqnarray*} X^4+3 \equiv 0 mod \left(X^4+3, 5\right) \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow X^4 \equiv -3 \equiv 2 mod \left(X^4+3, 5\right) \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow 1 \equiv \left(b_0+b_1X+(b_0+b_2)X^2+(b_1+b_3)X^3+b_2 \cdot 2+b_3 \cdot 2 \cdot X\right) mod \left(X^4+3, 5\right) \end{eqnarray*}$
$\begin{eqnarray*} \equiv \left((b_0+2b_2)+(b_1+2b_3)X+(b_0+b_2)X^2+(b_1+b_3)X^3\right) mod \left(X^4+3, 5\right) \end{eqnarray*}$

Stimmt das soweit? Wenn ja, wie muss ich jetzt weitermachen?

Viele Grüße und Danke!

13.06.2009, 18:43

Reksilat

Auf diesen Beitrag antworten »

RE: Inverse eines Polynoms
Hallo mathestudi,

Ich habe das jetzt nicht genau nachgerechnet (dafür ist dann am Ende die Probe da Augenzwinkern

Augenzwinkern

). Der nächste Schritt ist es nun, einen Koeffizientenvergleich in der letzten Gleichung vorzunehmen. Du erhältst ein LGS in vier Gleichungen mit vier Unbekannten:

$\begin{eqnarray*} 1\equiv b_0+2b_2\mod 5 \end{eqnarray*}$
$\begin{eqnarray*} 0\equiv b_1+2b_3\mod 5 \end{eqnarray*}$
$\begin{eqnarray*} ... \end{eqnarray*}$

PS: Du betrachtest hier Polynome und keine Funktionen, die Bezeichnung $\begin{eqnarray*} f(x) \end{eqnarray*}$ ist also vollkommen unangebracht.

Gruß,
Reksilat.

13.06.2009, 23:27

mathestudi

Auf diesen Beitrag antworten »

Hallo Reksilat,

danke für deine Hilfe.

Ich habe den Koeffizientenvergleich gemacht, ausgerechnet und erhalte
$\begin{eqnarray*} b_0=1 \end{eqnarray*}$ , $\begin{eqnarray*} b_1=0 \end{eqnarray*}$ , $\begin{eqnarray*} b_2=0 \end{eqnarray*}$ , $\begin{eqnarray*} b_3=0 \end{eqnarray*}$ (jeweils mod 5)

Das dann in meine Ursprüngliche Kongruenz eigesetzt:
$\begin{eqnarray*} 1 \equiv \left(X^2+1\right) \cdot \left(1+0X+0X^2+0X^3\right) mod \left(X^4+3, 5\right) \end{eqnarray*}$
$\begin{eqnarray*} \equiv \left(X^2+1\right) mod \left(X^4+3, 5\right) \end{eqnarray*}$

Ich verstehe nur nicht ganz, warum ich diesen Koeffizientenvergleich so machen kann!?
Was ist denn nun mein Inverses zu $\begin{eqnarray*} X^2+1 \end{eqnarray*}$ ? Doch nicht die 1, oder? verwirrt

verwirrt

Grüße

13.06.2009, 23:38

Reksilat

Auf diesen Beitrag antworten »

Deine Lösung ist ja auch nicht richtig. Wenn $\begin{eqnarray*} b_0=1 \end{eqnarray*}$ und $\begin{eqnarray*} b_2=0 \end{eqnarray*}$ ist, so steht in der Gleichung

$\begin{eqnarray*} 1\equiv (b_0+2b_2)+(b_1+2b_3)X+(b_0+b_2)X^2+(b_1+b_3)X^3 \mod \left( 5\right) \end{eqnarray*}$

rechts vor $\begin{eqnarray*} X^2 \end{eqnarray*}$ der Koeffizient $\begin{eqnarray*} 1 \end{eqnarray*}$ - und das darf nicht sein.

13.06.2009, 23:45

mathestudi

Auf diesen Beitrag antworten »

ok, aber genau das kommt doch bei dem Koeffizientenvergleich raus?!

Die vier Gleichungen sind doch
$\begin{eqnarray*} 1\equiv b_0+2b_2\mod 5 \end{eqnarray*}$
$\begin{eqnarray*} 0\equiv b_1+2b_3\mod 5 \end{eqnarray*}$
$\begin{eqnarray*} 1\equiv b_0+b_2\mod 5 \end{eqnarray*}$
$\begin{eqnarray*} 0\equiv b_1+b_3\mod 5 \end{eqnarray*}$

Und wenn ich das Umforme kommen die oben genannten Lösungen für b1... raus.

13.06.2009, 23:51

Reksilat

Auf diesen Beitrag antworten »

Auf der linken Seite steht eine $\begin{eqnarray*} 1 \end{eqnarray*}$ , also $\begin{eqnarray*} 1+0\cdot X+0\cdot X^2+0\cdot X^3 \end{eqnarray*}$ .

Frage mich echt, wie Du auf die 1 in der dritten Gleichung kommst. verwirrt

verwirrt

Anzeige

14.06.2009, 00:03

mathestudi

Auf diesen Beitrag antworten »

Eben hats mit dem Koeffizientenvergleich klick gemacht! Finger1

Finger1

Ich wusste ja nicht, warum / wie / weshalb ich den machen soll und wusste daher auch nicht, welche Koeffizienten ich (für links) eigentlich nehmen soll...
aber da steht ja so ne schöne $\begin{eqnarray*} 1 \equiv ... \end{eqnarray*}$

statt der 1 in Gleichung drei steht dann da eine 0.

Meine Ergebnisse für $\begin{eqnarray*} b_0=4 \end{eqnarray*}$ , $\begin{eqnarray*} b_1=0 \end{eqnarray*}$ , $\begin{eqnarray*} b_2=1 \end{eqnarray*}$ , $\begin{eqnarray*} b_3=0 \end{eqnarray*}$

Wenn ich das dann ich die Kongruenz einsetzte, ergibt das auch 1 = 1.

Das Inverse zu $\begin{eqnarray*} x^2+1 \end{eqnarray*}$ ist dann $\begin{eqnarray*} x^2+4 \end{eqnarray*}$ , richtig?

Damit müsste ich dann fertig sein?!

14.06.2009, 00:13

Reksilat

Auf diesen Beitrag antworten »

Richtich!

Freude

Ciao,
Reksilat.

14.06.2009, 00:18

mathestudi

Auf diesen Beitrag antworten »

Dankeschön!!! Wink

Wink

Darf ich vielleicht noch den zweiten Teil der Frage anschließen?

Wir sollen zum Invertieren von Polynomen jetzt noch den folgenden Satz beweisen.
Wie kann ich da rangehen?

Zeigen Sie, dass ein Polynom f genau dann modulo einem anderen Polynom g mit deg f < deg g multiplikativ invertierbar ist, wenn ggT(f,g)=1 gilt.

14.06.2009, 00:31

Reksilat

Auf diesen Beitrag antworten »

Du zeigst Hin- und Rückrichtung, wobei beides nicht wirklich schwer ist, wenn Du Dir mal überlegst, was ggT(f,g)=1 eigentlich bedeutet.

14.06.2009, 00:35

mathestudi

Auf diesen Beitrag antworten »

Das mit Hin- und Rückrichtung bei einem gwd Beweis sollte klar sein Augenzwinkern

Augenzwinkern

ggT(f,g)=1 bedeutet, dass es Polynome s, t gibt mit s*f+t*g=1

14.06.2009, 00:45

Reksilat

Auf diesen Beitrag antworten »

Wenn keine Ideen kommen, muss man eben alles haarklein aufschreiben. Für die einen ist es klar, für andere eben nicht und der Helfer sitzt da und soll wissen, was sich der Fragesteller schon für Gedanken gemacht hat.

Du musst jetzt eigentlich nur noch überlegen, was es bedeutet, dass $\begin{eqnarray*} f \end{eqnarray*}$ modulo $\begin{eqnarray*} g \end{eqnarray*}$ invertierbar ist und geeignet argumentieren. Die Aufgabe benötigt keine besonderen Ideen, sondern ist stures Geradeausdenken. Da weiß ich auch nicht, was ich noch groß sagen soll.

gn8,
Reksilat.
Schläfer

Schläfer

14.06.2009, 00:54

mathestudi

Auf diesen Beitrag antworten »

Zitat:

Original von Reksilat
Wenn keine Ideen kommen, muss man eben alles haarklein aufschreiben. Für die einen ist es klar, für andere eben nicht und der Helfer sitzt da und soll wissen, was sich der Fragesteller schon für Gedanken gemacht hat.

Big Laugh

hast du natürlich auch recht... also das war das einzige, was mir an dieser aufgabe klar was... Augenzwinkern

Augenzwinkern

Ich schreib mal alles auf, was mir einfällt:

ggT(f,g)=1 bedeutet, dass es Polynome s, t gibt mit s*f+t*g=1

f ist modulo g invertierbar heißt, dass es ein inverses Element $\begin{eqnarray*} s=f^{-1} \in K/(g) \end{eqnarray*}$ gibt.
Damit gilt dann $\begin{eqnarray*} s \cdot f \equiv 1 (mod g) \end{eqnarray*}$

Was heißt deg f < deg g?

14.06.2009, 12:35

mathestudi

Auf diesen Beitrag antworten »

So, neuer Tag, neuer Versuch...

Ich versuch mal alles zu ordnen, was ich gestern nur so hingschrieben habe.

z.z.:
"-->" Wenn ein Polynom f modulo einem anderen Polynom g mit deg f < deg g multiplikativ invertierbar ist, gilt ggT(f,g)=1.

"<--" Wenn ggT(f,g)=1 und deg f < deg g, dann ist das Polynom f modulo dem Polynom g multiplikativ invertierbar.

Hierzu schon mal die erste Frage:
Sehe ich das richtig, dass ich in beiden Fällen deg f < deg g voraussetzen muss oder muss ich bei der Rückrichtung zeigen, dass wenn ggT(f,g)=1, so gilt auch deg f < deg g?

Ist deg f der Grad des Polynoms f?

Nun zu dem Beweis. Zunächst mal die Rückrichtung.
Bew. "<--":
Es gilt ggT(f,g)=1, also existieren Polynome s, t mit s*f+t*g=1.
Somit ist $\begin{eqnarray*} s \equiv f^{-1} \in K/(g) \end{eqnarray*}$ das inverse Element von f.

Bin ich damit schon fertig (also mit der einen Richtung)?

Bew. "-->":
Annahme: f besitzt ein inverses Element $\begin{eqnarray*} s \equiv f^{-1} \in K/(g) \end{eqnarray*}$ .
Damit gilt, dass $\begin{eqnarray*} s \cdot f \equiv 1 (mod f) \end{eqnarray*}$ ist.
Daher existiert ein Polynom $\begin{eqnarray*} t \in K \end{eqnarray*}$ , sodass s*f+t*g=1 ist.
Jedes Polynom, dass sich derart schreiben lässt ist teilbar duch den ggT(f,g).
Daraus folgt, dass ggT(f,g)=1.

Und war das jetzt die andere Richtung?

Sollte das soweit passen, bleibt nur noch die Sache mit deg f < deg g...

14.06.2009, 16:55

Reksilat

Auf diesen Beitrag antworten »

Sieht so weit ganz gut aus. Lohnt sich eben nochmal eine Nacht drüber zu schlafen. Augenzwinkern

Augenzwinkern

Zuerst zu "deg g<deg f":

1) Richtig, gemeint ist der Grad des Polynoms.

2) Die Aufgabe ist etwas widersprüchlich formuliert, da man den Grad hier gar nicht benötigt. Lasse das einfach weg und zeige:
$\begin{eqnarray*} {\rm ggT}(f,g)=1 \end{eqnarray*}$ $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ $\begin{eqnarray*} f \end{eqnarray*}$ ist mod $\begin{eqnarray*} g \end{eqnarray*}$ invertierbar.
Der Grad ist hier nämlich nicht so wichtig, denn...

3) Die Aussage ggT(f,g)=1 hat mit dem Grad der Polynome nichts zu tun, es lässt sich also in keinem Fall deg f<deg g daraus folgern.

4) Wenn wir $\begin{eqnarray*} f \end{eqnarray*}$ modulo $\begin{eqnarray*} g \end{eqnarray*}$ betrachten, dann können wir oBdA immer annehmen, dass deg f< deg g gilt. Das wird hier aber ebenfalls nicht benötigt, und so können wir das auch bleiben lassen.

Deine Argumentation oben ist schlüssig und Du hast ja selbst gesehen, dass Du den Grad der Polynome nicht benötigst. Eine exakte Formulierung, in der der Grad auftaucht kann ich auch nicht liefern. Ich würde das so stehen lassen.

Gruß,
Reksilat.

14.06.2009, 17:55

mathestudi

Auf diesen Beitrag antworten »

Vielen Dank für deine Hilfe! Wink

Wink

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »