ggT von Polynomen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:21 Fr 23.04.2010 | | Autor: | Freak84 |
| Aufgabe | | Sei [mm] \IZ_{3} [/mm] = {0,1,2}. Löse zu [mm] f=x^5+1 [/mm] , [mm] g=x^3+2 \in \IZ_{3}[x] [/mm] die Gleichung fu+gv=ggT(f,g) für u,v [mm] \in \IZ_{3}[x] [/mm] mit dem erweitertem Eukliedischem Algorithmus für Polynome. |
Hi
Ich habe in meinem Skrip immer nur den Algo für ganze Zahlen gefunden, glaube aber, dass ich diesen einfach 1 zu 1 auf die Polynome übertragen kann. Ich komme allerdings nicht wirklich zu einem guten Ergebnis, daher habe ich mich erstmal darauf beschränkt den ggT(f,g) zu berechnen und habe heraus bekommen, dass die beiden Polynome Teilerfremd sind.
Hier meine Rechnungen. Alles halt im dem [mm] \IZ_{3}
[/mm]
[mm] x^5+1 [/mm] = [mm] x^2 [/mm] * [mm] (x^3+2) [/mm] rest [mm] x^2+1
[/mm]
[mm] x^3+2 [/mm] = x * [mm] (x^2+1) [/mm] rest 2x+2
[mm] x^2+1 [/mm] = 2x * (2x+2) rest 2x+1
2x+2 = 1 * (2x+1) rest 1
2x + 1 (2x+1) * 1 rest 0
Dieses bedeutet doch nun, dass der ggT=1 ist oder ?
Wäre super wenn ihr mich berichten würdet falls ich total falsch liege
Gruß
|
|
| |
|
Hallo Michael,
> Sei [mm]\IZ_{3}[/mm] = {0,1,2}. Löse zu [mm]f=x^5+1[/mm] , [mm]g=x^3+2 \in \IZ_{3}[x][/mm]
> die Gleichung fu+gv=ggT(f,g) für u,v [mm]\in \IZ_{3}[x][/mm] mit
> dem erweitertem Eukliedischem Algorithmus für Polynome.
> Hi
> Ich habe in meinem Skrip immer nur den Algo für ganze
> Zahlen gefunden, glaube aber, dass ich diesen einfach 1 zu
> 1 auf die Polynome übertragen kann. Ich komme allerdings
> nicht wirklich zu einem guten Ergebnis, daher habe ich mich
> erstmal darauf beschränkt den ggT(f,g) zu berechnen und
> habe heraus bekommen, dass die beiden Polynome Teilerfremd
> sind.
>
> Hier meine Rechnungen. Alles halt im dem [mm]\IZ_{3}[/mm]
>
> [mm]x^5+1[/mm] = [mm]x^2[/mm] * [mm](x^3+2)[/mm] rest [mm]x^2+1[/mm]
> [mm]x^3+2[/mm] = x * [mm](x^2+1)[/mm] rest 2x+2
> [mm]x^2+1[/mm] = 2x * (2x+2) rest 2x+1
> 2x+2 = 1 * (2x+1) rest 1
> 2x + 1 (2x+1) * 1 rest 0 ![[ok]](/images/smileys/ok.gif "[ok]")
>
> Dieses bedeutet doch nun, dass der ggT=1 ist oder ?
Ganz genau! ![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]")
> Wäre super wenn ihr mich berichten würdet falls ich total
> falsch liege
Nein, alles richtig!
>
> Gruß
LG
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 17:16 Fr 23.04.2010 | | Autor: | Freak84 |
Vielen Dank für die schnelle Überprüfung.
Nun soll ich ja noch die Gleichung Lösen mit dem Erweitertem Algo. Kann ich da auch einfach den Euklid nehmen oder muss ich da was an den startbedingungen ändern. Da werden ja 4 Werte am Anfang gefestgelegt bei uns heißen sie. [mm] t_{-1}=0, t_{0}=1, s_{-1}=1, s_{0}=0.
[/mm]
Mit denen rechnet man ja dann muter rum. Allerdings bekomme ich am schluss in der Gleichnung nie den ggT raus.
Es muss ja das u und v geben, dass hier fu + gv = ggT(f,g) = 1 oder ?
Gruß
|
|
|
| |
|
Hallo nochmal,
> Vielen Dank für die schnelle Überprüfung.
>
> Nun soll ich ja noch die Gleichung Lösen mit dem
> Erweitertem Algo. Kann ich da auch einfach den Euklid
> nehmen oder muss ich da was an den startbedingungen
> ändern. Da werden ja 4 Werte am Anfang gefestgelegt bei
> uns heißen sie. [mm]t_{-1}=0, t_{0}=1, s_{-1}=1, s_{0}=0.[/mm]
> Mit
> denen rechnet man ja dann muter rum. Allerdings bekomme ich
> am schluss in der Gleichnung nie den ggT raus.
>
> Es muss ja das u und v geben, dass hier fu + gv = ggT(f,g)
> = 1 oder ?
Berechne die gesuchte LK durch sukzessives Rückwärtseinsetzen aus den Gleichungen, die du mit dem Euklid. Algo. aufgestellt hast.
Beginne mit der vorletzten Zeile:
$1=(2x+2)-1(2x+1)=(2x+2)+2(2x+1)$
Nun eine Zeile höher und das 2x+1 ersetzen durch [mm] x^2+1)-2x(2x+2)...
[/mm]
Aber nicht alles ausmultiplizieren, du musst immer zusehen, dass du mit dem Rest eine Zeile höher ersetzen kannst.
Schließlich willst du ja [mm] 1=f\cdot{}u+g\cdot{}v [/mm] am Ende bekommen
Immer daran denken, die Koeffizienten mod 3 zu nehmen
Oder rechne erst wie gewohnt in [mm] \IZ [/mm] und reduziere am Ende ...
Gruß
schachuzipus
>
> Gruß
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:24 Fr 23.04.2010 | | Autor: | Freak84 |
Vielen Dank schonmal.
Habe die ganz sache jetzt einmal aufgeschrieben. Ich glaube ich habe total den überblick verloren aber hier mal meine Ergebnisse mit zwischenschritten. Habe erstmal den Mod weggelassen
1) $ [mm] x^5+1 [/mm] $ = $ [mm] x^2 [/mm] $ * $ [mm] (x^3+2) [/mm] $ rest $ [mm] x^2+1 [/mm] $
2) $ [mm] x^3+2 [/mm] $ = x * $ [mm] (x^2+1) [/mm] $ rest 2x+2
3) $ [mm] x^2+1 [/mm] $ = 2x * (2x+2) rest 2x+1
4) 2x+2 = 1 * (2x+1) rest 1
5) 2x + 1 = (2x+1) * 1 rest 0
4) (2x+2)-(2x+1) = 1
3) [mm] (x^2+1) [/mm] = 2x(2x+2) + (2x+1) [mm] \Rightarrow (x^2+1) [/mm] - 2x(2x+2) = (2x+1)
nun 3) in 4)
[mm] \Rightarrow [/mm] 5) (2x+2) - [mm] ((x^2+1) [/mm] - 2x(2x+2)) =1
2) [mm] x^3+2 [/mm] = x * [mm] (x^2+1) [/mm] + (2x+2) [mm] \Rightarrow (x^3+2) [/mm] - (x * [mm] (x^2+1)) [/mm] = (2x+2)
nun 2) in 5)
[mm] \Rightarrow [/mm] 6) (2x+2) - [mm] ((x^2+1) [/mm] - [mm] 2x((x^3+2) [/mm] - (x * [mm] (x^2+1)))) [/mm] =1
1) [mm] x^5+1 [/mm] = [mm] x^2 [/mm] * [mm] (x^3+2) [/mm] + [mm] (x^2+1) \Rightarrow (x^5+1) [/mm] - [mm] x^2 [/mm] * [mm] (x^3+2) [/mm] = [mm] (x^2+1)
[/mm]
nun 1) in 6)
[mm] \Rightarrow [/mm] (2x+2) - [mm] ((x^2+1) [/mm] - [mm] 2x((x^3+2) [/mm] - (x * [mm] ((x^5+1) [/mm] - [mm] x^2 [/mm] * [mm] (x^3+2))))) [/mm] =1
Dieses ist mein Entterm. Was mich schonmal Glücklich stimmt, ist dass f und f mit drin stecken. Habe aller total den Überblick verloren wie ich das jetzt auf die Form fu + gv = 1 bekommen soll.
Wäre super wenn du nochmal drüber schauen könntest ob das so richtig ist was ich da gemacht habe.
Gruß
|
|
|
| |
|
Hallo,
das ist sehr sehr unübersichtlich, mörderisch zu kontrolleiren.
Ich kann dir aber meinen Weg aufschreiben.
Mein Ergebnis stimmt wohl, ich habe die Probe gemacht!
> Vielen Dank schonmal.
> Habe die ganz sache jetzt einmal aufgeschrieben. Ich glaube
> ich habe total den überblick verloren aber hier mal meine
> Ergebnisse mit zwischenschritten. Habe erstmal den Mod
> weggelassen
>
> 1) [mm]x^5+1[/mm] = [mm]x^2[/mm] * [mm](x^3+2)[/mm] rest [mm]x^2+1[/mm]
> 2) [mm]x^3+2[/mm] = x * [mm](x^2+1)[/mm] rest 2x+2
> 3) [mm]x^2+1[/mm] = 2x * (2x+2) rest 2x+1
> 4) 2x+2 = 1 * (2x+1) rest 1
> 5) 2x + 1 = (2x+1) * 1 rest 0
>
> 4) (2x+2)-(2x+1) = 1
Schreibe hier besser [mm] $1=(2x+2)-1\cdot{}(2x+1)$ [/mm] ...
>
> 3) [mm](x^2+1)[/mm] = 2x(2x+2) + (2x+1) [mm]\Rightarrow (x^2+1)[/mm] -
> 2x(2x+2) = (2x+1)
Wo ist die 1 hin?
Die muss bis zum Schluss bleiben, du willst ja 1=fu+gv haben
Ich habe so eingesetzt:
[mm] $1=(2x+2)-1\cdot{}(2x+1)$
[/mm]
[mm] $=(2x+2)-1\cdot{}\left[(x^2+1)-2x(2x+2)\right]=(2x+1)(2x+2)-1\cdot{}(x^2+1)$
[/mm]
[mm] $=(2x+2)\left[(x^3+2)-x(x^2+1)\right]-1\cdot{}(x^2+1)=(2x+1)(x^3+2)+(-2x^2-x-1)(x^2+1)$
[/mm]
[mm] $=(2x+1)(x^3+2)+(-2x^2-x-1)\left[(x^5+1)-x^2(x^3+2)\right]$
[/mm]
[mm] $=(x^3+2)(2x+1+2x^4+x^3+x^2)+(x^5+1)(-2x^2-x-1)$
[/mm]
Noch reduzieren mod3
[mm] $\equiv \underbrace{(x^3+2)}_{f}\cdot{}\underbrace{(2x^4+x^3+x^2+2x+1)}_{u} [/mm] \ + \ [mm] \underbrace{(x^5+1)}_{g}\cdot{}\underbrace{(x^2+2x+2)}_{v} [/mm] \ [mm] \operatorname{mod}3$
[/mm]
Wenn du das wieder ausmultiplizierst, kommt tatsächlich 1 raus ...
Du kannst ja selbst vergleichen mit deinem Weg ...
>
> nun 3) in 4)
>
> [mm]\Rightarrow[/mm] 5) (2x+2) - [mm]((x^2+1)[/mm] - 2x(2x+2)) =1
>
> 2) [mm]x^3+2[/mm] = x * [mm](x^2+1)[/mm] + (2x+2) [mm]\Rightarrow (x^3+2)[/mm] -
> (x * [mm](x^2+1))[/mm] = (2x+2)
>
> nun 2) in 5)
>
> [mm]\Rightarrow[/mm] 6) (2x+2) - [mm]((x^2+1)[/mm] - [mm]2x((x^3+2)[/mm] - (x *
> [mm](x^2+1))))[/mm] =1
>
>
> 1) [mm]x^5+1[/mm] = [mm]x^2[/mm] * [mm](x^3+2)[/mm] + [mm](x^2+1) \Rightarrow (x^5+1)[/mm]
> - [mm]x^2[/mm] * [mm](x^3+2)[/mm] = [mm](x^2+1)[/mm]
>
>
> nun 1) in 6)
>
> [mm]\Rightarrow[/mm] (2x+2) - [mm]((x^2+1)[/mm] - [mm]2x((x^3+2)[/mm] - (x *
> [mm]((x^5+1)[/mm] - [mm]x^2[/mm] * [mm](x^3+2)))))[/mm] =1
>
> Dieses ist mein Entterm. Was mich schonmal Glücklich
> stimmt, ist dass f und f mit drin stecken.
Irgendwie aber nicht als Faktor ...
> Habe aller total
> den Überblick verloren wie ich das jetzt auf die Form fu +
> gv = 1 bekommen soll.
>
> Wäre super wenn du nochmal drüber schauen könntest ob
> das so richtig ist was ich da gemacht habe.
>
> Gruß
LG
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:31 Sa 24.04.2010 | | Autor: | Freak84 |
Vielen Dank für deine Mühe und Gedult.
Habe jetzt meinen Weg auch nochmal durchgeschaut und gemerkt, dass ich gleich am Anfang vereinfachen kann und die ganze Sache dann viel Übersichlicher wird.
nochmals vielen Dank
Gruß
|
|
|
|
