Inverse eines Polynoms bestimm < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:01 Fr 08.01.2010 | | Autor: | SUNNY000 |
Hallo Leute,
ich Skript haben wir ein Beispiel für das Bestimmen der Inverse eines Polynoms mit Hilfe des Erweiterten Euklidischen Algorithmus. An sich ist mir klar, wie die Vorgehensweise ist, allerding kann ich an diesem Beispiel beim besten Willen nicht verstehen, wie man auf das Ergebnis kommt.
[mm] a(x)=x^2
[/mm]
Wir bestimmen das Inverse von a(x) modulo [mm] m(x)=x^8+x^4+x^3+x+1 [/mm] mit dem EA
[mm] m(x):x^2 [/mm] = [mm] x^6+x^2+x [/mm] Rest x+1
[mm] \Rightarrow [/mm] x+1 = [mm] m(x)-x^2 [/mm] * [mm] (x^6+x^2+x)
[/mm]
[mm] x^2:(x+1)=(x+1) [/mm] Rest 1
[mm] \Rightarrow [/mm] 1= [mm] x^2-(x+1)(x+1)
[/mm]
und nun rückwärts einsetzen:
[mm] 1=x^2-(x+1)(x+1)
[/mm]
[mm] =x^2-(x+1)*(m(x)-x^2*(x^6+x^2+x))
[/mm]
[mm] =x^2-(x+1)*m(x)+(x+1)*x^2*(x^6+x^2+x)
[/mm]
......
Und hier liegt mein Progblem. Wie kommt die dritte Zeile zustande?
[mm] x^2-(x+1)*m(x)+(x+1)*x^2*(x^6+x^2+x)
[/mm]
Ich wäre für jeden Tipp dankbar.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:05 Fr 08.01.2010 | | Autor: | rainerS |
Hallo!
> und nun rückwärts einsetzen:
> [mm]1=x^2-(x+1)(x+1)[/mm]
> [mm]=x^2-(x+1)*(m(x)-x^2*(x^6+x^2+x))[/mm]
> [mm]=x^2-(x+1)*m(x)+(x+1)*x^2*(x^6+x^2+x)[/mm]
> ......
>
> Und hier liegt mein Progblem. Wie kommt die dritte Zeile
> zustande?
Durch einfaches Ausmultiplizieren der Klammer [mm] $(m(x)-x^2*(x^6+x^2+x))$ [/mm] nach dem Distributivgesetz.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:13 Fr 08.01.2010 | | Autor: | SUNNY000 |
hmm, das habe ich auch versucht, aber es kommt nicht hin. Ich setze für m(x) das Polynom ein und multipliziere die Klammern beim letzten Teil aus:
[mm] x^2-(x+1)((x^8+x^4+x^3+x+1)-(x^8+x^4+x^3))
[/mm]
[mm] =x^2-(x+1)(x+1)
[/mm]
Somit lande ich wieder bei der Ausgangssituation (die erste Zeile). Was übersehe ich?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:47 Fr 08.01.2010 | | Autor: | rainerS |
Hallo!
(Was ich vorhin übersehen habe: bei der zweiten Division ist ein Vorzeichen falsch:
[mm] x^2 : (x+1) = (x \red{-}1) [/mm]
Aber das nur nebenbei.)
Du darfst $m(x)$ nicht wieder einsetzen.
Du suchst doch Polynomne $b(x)$ und $c(x)$ mit $a(x)*b(x) + c(x)*m(x) = 1$. $b(x)$ ist das Inverse, also:
[mm] x^2-(x-1)\cdot{}(m(x)-x^2\cdot{}(x^6+x^2+x)) [/mm]
Nach [mm] $x^2$ [/mm] gruppieren:
[mm] 1 = x^2 (1+ (x-1)(x^6+x^2+x)) - (x-1) m(x) [/mm]
[mm] b(x) = x^7 -x^6+x^3-x+1 [/mm]
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:02 Fr 08.01.2010 | | Autor: | SUNNY000 |
Hallo Rainer und danke dir für die schnelle Antwort. Bei der Division war das Vorzeichen richtig, ich habe vergessen dummerweise zu erwähnen, dass a [mm] \in \IZ_{2}^8 [/mm] ist.
Aber das ist ja im Prinzip irrelevant, da ich ja nur das Vorgehen verstehen möchte. Entweder ich bin komplett raus oder habe einfach eine Blockade, aber ich komme einfach nicht darauf, wie du es rausbekommst :
1 = [mm] x^2 [/mm] (1+ [mm] (x-1)(x^6+x^2+x)) [/mm] - (x-1) m(x)
Multiplizierst du denn gar nicht [mm] x^2\cdot{}(x^6+x^2+x) [/mm] aus?
Wäre es möglich, dass du mir den Anfang schrittweise zeigst?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:07 Fr 08.01.2010 | | Autor: | rainerS |
Hallo!
> Hallo Rainer und danke dir für die schnelle Antwort. Bei
> der Division war das Vorzeichen richtig, ich habe vergessen
> dummerweise zu erwähnen, dass a [mm]\in \IZ_{2}^8[/mm] ist.
>
> Aber das ist ja im Prinzip irrelevant, da ich ja nur das
> Vorgehen verstehen möchte. Entweder ich bin komplett raus
> oder habe einfach eine Blockade, aber ich komme einfach
> nicht darauf, wie du es rausbekommst :
> 1 = [mm]x^2[/mm] (1+ [mm](x-1)(x^6+x^2+x))[/mm] - (x-1) m(x)
> Multiplizierst du denn gar nicht [mm]x^2\cdot{}(x^6+x^2+x)[/mm]
> aus?
[mm] $x^2=a(x)$, [/mm] das muss doch als Faktor stehen bleiben. Du hast im 1. Schritt
[mm] x+1 = m(x) - a(x) * (x^6+x^2+x) [/mm]
Im zweiten
[mm] 1 = a(x) - (x+1) (x-1) \,[/mm]
[mm] 1= a(x) - (x-1) (m(x) - a(x) * (x^6+x^2+x)) [/mm]
[mm] 1= a(x) (1+(x-1)*(x^6+x^2+x)) - (x-1) m(x) [/mm]
Der Faktor hinter $a(x)$ ist das gesuchte Inverse.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 21:43 Fr 08.01.2010 | | Autor: | SUNNY000 |
1= a(x) - (x-1) (m(x) - a(x) [mm] \cdot{} (x^6+x^2+x))
[/mm]
Jetzt multipliziere ich aus und komme auf:
[mm] x^2-(x-1)*m(x)-((x-1)*x^2*(x^6+x^2+x))
[/mm]
[mm] =x^2-(x-1)*m(x)-x^2*((x-1)*(x^6+x^2+x))
[/mm]
und an der Stelle komme ich nicht weiter. Bei mir ist hier 2 mal [mm] x^2 [/mm] vorhanden. Und ich kann es nicht mal ausklammern, da das erste [mm] x^2 [/mm] eine Subtraktion ist. Ich frage mich, wie du im letzten Schritt auf nur ein mal [mm] x^2 [/mm] kommst und die (1 +(x-1)? Woher ist die 1?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:20 Fr 08.01.2010 | | Autor: | SUNNY000 |
Die Frage hat sich jetzt erledigt :) Ich danke dir für deine Antworten.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:46 Fr 08.01.2010 | | Autor: | SUNNY000 |
Ich habe jetzt an diesem Beispiel eine Aufgabe berechnet. Mich würde interessieren, ob das Endergebnis korrekt ist?
m(x) ist wie gehabt, [mm] a(x)=x^3 [/mm] und wir befinden uns immer noch in [mm] \IZ_{2}^8
[/mm]
Nachdem ich den EEA angewendet habe, bekomme ich
[mm] 1=x^3-(x+1)*x^2
[/mm]
[mm] =x^3-x^2*(m(x)-x^3*(x^5+x+1))
[/mm]
[mm] =x^3-(x^2*m(x))+x^3*(x^2*(x^5+x+1))
[/mm]
[mm] =x^3*(x^7+x^3+x^2)-x^2*m(x)
[/mm]
die Inverse wäre somit [mm] a^{-1}=x^7+x^3+x^2
[/mm]
Diese könnte ich dann noch um [mm] x^2 [/mm] kürzen [mm] a^{-1}=x^5+x+1
[/mm]
Wäre das korrekt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:36 Sa 09.01.2010 | | Autor: | rainerS |
Hallo!
> Ich habe jetzt an diesem Beispiel eine Aufgabe berechnet.
> Mich würde interessieren, ob das Endergebnis korrekt ist?
>
> m(x) ist wie gehabt, [mm]a(x)=x^3[/mm] und wir befinden uns immer
> noch in [mm]\IZ_{2}^8[/mm]
>
> Nachdem ich den EEA angewendet habe, bekomme ich
> [mm]1=x^3-(x+1)*x^2[/mm]
Diese Gleichung ist offensichtlich falsch. Rechts steht [mm] $-x^2$, [/mm] nicht $1$. Ich vermute, da hast dich bei der Division $a(x):(x+1)$ verrechnet.
Viele Grüße
Rainer
> [mm]=x^3-x^2*(m(x)-x^3*(x^5+x+1))[/mm]
> [mm]=x^3-(x^2*m(x))+x^3*(x^2*(x^5+x+1))[/mm]
> [mm]=x^3*(x^7+x^3+x^2)-x^2*m(x)[/mm]
>
> die Inverse wäre somit [mm]a^{-1}=x^7+x^3+x^2[/mm]
> Diese könnte ich dann noch um [mm]x^2[/mm] kürzen [mm]a^{-1}=x^5+x+1[/mm]
Warum meinst du, dass du einfach kürzen darfst?
>
> Wäre das korrekt?
Mach die Probe:
[mm] x^3 * (x^7+x^3+x^2) = x^{10}+x^6+x^5 [/mm]
muss bei Division durch $m(x)$ den Rest 1 ergeben.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:24 So 10.01.2010 | | Autor: | SUNNY000 |
Hallo, ich hatte mich wirklich verrrechnet gehabt. Trotzdem komme ich in meinem Beispiel nicht auf das richtige Ergebnis. Hier nochmal meine Lösung:
EEA:
[mm] m(x):x^3=x^5+x+1 [/mm] Rest x+1
[mm] \Rightarrow x+1=m(x)-x^3*(x^5+x+1)
[/mm]
[mm] x^3:(x+1)=x^2+x+1 [/mm] Rest 1
[mm] \Rightarrow 1=x^3-(x+1)*(x^2+x+1)
[/mm]
Nun setze ich rückwärts ein:
[mm] 1=x^3-(x^2+x+1)*(x+1)
[/mm]
[mm] =x^3-(x^2+x+1)*(m(x)-x^3*(x^5+x+1))
[/mm]
[mm] =x^3-(x^2+x+1)*m(x)+x^3(((x^2+x+1)*(x^5+x+1))
[/mm]
[mm] =x^3-(x^2+x+1)*m(x)+x^3(x^7+x^6+x^5+x^3+1)
[/mm]
also :
[mm] 1=x^3(x^7+x^6+x^5+x^3+1)-(x^2+x+1)m(x)
[/mm]
Nur leider wenn ich alles ausmultipliziere um die Probe zu machen, komme ich auf [mm] 1=x^3+1. [/mm] Wo habe ich einen Fehler gemacht?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:22 Mo 11.01.2010 | | Autor: | rainerS |
Hallo!
> Hallo, ich hatte mich wirklich verrrechnet gehabt. Trotzdem
> komme ich in meinem Beispiel nicht auf das richtige
> Ergebnis. Hier nochmal meine Lösung:
> EEA:
> [mm]m(x):x^3=x^5+x+1[/mm] Rest x+1
> [mm]\Rightarrow x+1=m(x)-x^3*(x^5+x+1)[/mm]
>
> [mm]x^3:(x+1)=x^2+x+1[/mm] Rest 1
Du rechnest immer noch in [mm] $\IZ_2$ [/mm] ? Sonst wäre der Rest $-1$.
> [mm]\Rightarrow 1=x^3-(x+1)*(x^2+x+1)[/mm]
>
> Nun setze ich rückwärts ein:
> [mm]1=x^3-(x^2+x+1)*(x+1)[/mm]
> [mm]=x^3-(x^2+x+1)*(m(x)-x^3*(x^5+x+1))[/mm]
> [mm]=x^3-(x^2+x+1)*m(x)+x^3(((x^2+x+1)*(x^5+x+1))[/mm]
> [mm]=x^3-(x^2+x+1)*m(x)+x^3(x^7+x^6+x^5+x^3+1)[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
>
> also :
> [mm]1=x^3(x^7+x^6+x^5+x^3+1)-(x^2+x+1)m(x)[/mm]
Du hast den allerersten Summanden [mm] $x^3$ [/mm] vergessen:
1 = [mm] x^3 -(x^2+x+1)*m(x)+x^3(x^7+x^6+x^5+x^3+1) = x^3 (1- x^7+x^6+x^5+x^3+1) - (x^2+x+1)*m(x)[/mm].
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:45 Mo 11.01.2010 | | Autor: | SUNNY000 |
Hallo Rainer und lieben dank für den Tipp. Nun ergibt die Probe auch eine 1. Ich befinde mich immer noch in [mm] \IZ_{2}, [/mm] ja. Für meine Aufgabe müsste ich nun die Inverse (1- [mm] x^7+x^6+x^5+x^3+1) [/mm] in die Binär-Darstellung bringen. Wenn ich das Polynom zusammenfasse, bekomme ich dann [mm] (-x^7+x^6+x^5+x^3+2) [/mm] raus? Darf denn [mm] x^7 [/mm] überhaupt im Minusbereich sein? Wenn ich ein simples Polynom hätte, bspw. [mm] (x^7+x^6+x^5+x^3+1), [/mm] dann wäre ja die Binär-Darstellung 1110 1001, aber wie sieht sowas bei (1- [mm] x^7+x^6+x^5+x^3+1) [/mm] aus?
Lg
Sunny
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:43 Mo 11.01.2010 | | Autor: | rainerS |
Hallo!
> Hallo Rainer und lieben dank für den Tipp. Nun ergibt die
> Probe auch eine 1. Ich befinde mich immer noch in [mm]\IZ_{2},[/mm]
> ja. Für meine Aufgabe müsste ich nun die Inverse (1-
> [mm]x^7+x^6+x^5+x^3+1)[/mm] in die Binär-Darstellung bringen. Wenn
> ich das Polynom zusammenfasse, bekomme ich dann
> [mm](-x^7+x^6+x^5+x^3+2)[/mm] raus? Darf denn [mm]x^7[/mm] überhaupt im
> Minusbereich sein? Wenn ich ein simples Polynom hätte,
> bspw. [mm](x^7+x^6+x^5+x^3+1),[/mm] dann wäre ja die
> Binär-Darstellung 1110 1001, aber wie sieht sowas bei (1-
> [mm]x^7+x^6+x^5+x^3+1)[/mm] aus?
[mm] $\IZ_2$ [/mm] hat doch nur zwei Elemente; das eine kannst du auffassen als die Äquivalenzklasse aller geraden ganzen Zahlen, das andere als die aller ungeraden ganzen Zahlen. Daher darfst du alle geraden Zahlen durch 0 und alle ungeraden Zahlen durch 1 ersetzen:
[mm] -x^7+x^6+x^5+x^3+2 \equiv x^7 + x^6 +x^5+ x^3 [/mm]
Und jetzt mache selber die Probe: Was ergibt
[mm] x^3 * (x^7 + x^6 +x^5+ x^3) [/mm]
bei Division durch $m(x)$ ?
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:22 Di 12.01.2010 | | Autor: | SUNNY000 |
Hallo Rainer, habe die Probe gemacht und es kommt 1 raus :) Ich danke dir vielmals für deine Hilfe. Was mich noch interessieren würde, ist, welche Regeln sind es, die besagen, dass bspw. [mm] x^2+x^2 [/mm] weggestrichen werden können? (Wie in meinem Beispiel mit dem Ausmultiplizieren)
Ich danke dir nochmal für deine hilfreichen Tipps.
|
|
|
|
