GGT zweier Polynome < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 23:19 So 27.07.2014 | | Autor: | Morgyr |
| Aufgabe | Ein größter gemeinsamer Teiler (ggT) von zwei Polynomen ist definiert
als ein Polynom von maximalem Grad, das beide Polynome teilt.
a) Berechne einen ggT der Polynome f(x) = x4-x3-x2-2x und g(x) = x3 +6x2 +
6x + 5 mit dem erweiterten Euklidischen Algorithmus.
b) Stelle den ggT als Linearkombination von f(x) und g(x) dar.
c) Zeige, dass der ggT nicht eindeutig ist. |
Moin,
a) Kurz und knapp:
ggT(f(x),g(x)) = [mm] 35x^2 [/mm] + 35x + 35
b) Hatte dazu hauptsächlich was gefunden, wo "Rückwärts gerechnet" wurde.
Nach der Definition des erweiterten-Euklid-Algorithmus berechnet dieser für alle m, n [mm] \in \IN, [/mm] n [mm] \ge [/mm] m ganze Zahlen x, y [mm] \in \IZ [/mm] mit ggT(m,n) = mx + ny.
(x,y) ist die Ausgabe.
Ist das übertragen auf Polynome, m=g(x) und n=f(x), nicht schon die lineare Kombination? Habe leider keine Definition dafür gefunden, bzw. nur für Zahlen.
c) Hier das gleiche: Was ist gemeint?
Ich habe praktisch zwei Möglichkeiten:
1. Der ggT hat einen niedrigeren Grad als f(x) und g(x) und ist somit nicht eindeutig.
2. Der ggT ist reduzierbar und somit nicht eindeutig. Das würde mich zwar wundern, weil man es dann ja auch gleich gT nennen könnte, aber dafür hatte ich wenigstens eine entsprechende Definition für Zahlen.
Möglichkeit 1 ist aus einem Beispiel geklaut, dass in etwa die gleiche Konstellation hat.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:32 So 27.07.2014 | | Autor: | Marcel |
Hallo,
> Ein größter gemeinsamer Teiler (ggT) von zwei Polynomen
> ist definiert
> als ein Polynom von maximalem Grad, das beide Polynome
> teilt.
> a) Berechne einen ggT der Polynome f(x) = x4-x3-x2-2x und
> g(x) = x3 +6x2 +
> 6x + 5 mit dem erweiterten Euklidischen Algorithmus.
> b) Stelle den ggT als Linearkombination von f(x) und g(x)
> dar.
> c) Zeige, dass der ggT nicht eindeutig ist.
> Moin,
>
> a) Kurz und knapp:
> ggT(f(x),g(x)) = [mm]35x^2[/mm] + 35x + 35
>
> b) Hatte dazu hauptsächlich was gefunden, wo "Rückwärts
> gerechnet" wurde.
> Nach der Definition des erweiterten-Euklid-Algorithmus
> berechnet dieser für alle m, n [mm]\in \IN,[/mm] n [mm]\ge[/mm] m ganze
> Zahlen x, y [mm]\in \IZ[/mm] mit ggT(m,n) = mx + ny.
> (x,y) ist die Ausgabe.
> Ist das übertragen auf Polynome, m=g(x) und n=f(x), nicht
> schon die lineare Kombination? Habe leider keine Definition
> dafür gefunden, bzw. nur für Zahlen.
>
> c) Hier das gleiche: Was ist gemeint?
> Ich habe praktisch zwei Möglichkeiten:
> 1. Der ggT hat einen niedrigeren Grad als f(x) und g(x)
> und ist somit nicht eindeutig.
> 2. Der ggT ist reduzierbar und somit nicht eindeutig. Das
> würde mich zwar wundern, weil man es dann ja auch gleich
> gT nennen könnte, aber dafür hatte ich wenigstens eine
> entsprechende Definition für Zahlen.
> Möglichkeit 1 ist aus einem Beispiel geklaut, dass in
> etwa die gleiche Konstellation hat.
vielleicht guckst Du einfach mal in
Müller-Stach/Piontkowski: Elementare Zahlentheorie und Algebra, 2. Auflage
Kapitel 3. Dort wird der Begriff des ggT in faktoriellen Ringen erläutert.
Bei den Übungsaufgaben (S.17) steht auch eine Aufgabe, wo man mit
Polynomen rechnen soll. Generell ist der ggT nur eindeutig bis auf eine
Einheit, sowas wird bei Dir oben sicher auch irgendwo benutzt werden
können.
(P.S. Schau' mal nach oder überlege Dir, welche Form hier die Polynome
haben, die eine Einheit sind.)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:26 Mo 28.07.2014 | | Autor: | Morgyr |
Hi,
das Buch oder etwas vergleichbares habe ich hier jetzt nicht.
Mir steht hier Steger - Diskrete Strukturen Band 1 in 2. Auflage und ein paar Beispiel dinA4 Seiten zur Verfügung.
In diesem Buch wird zwar so eine Aufgabe gestellt, aber da wird nichts zu erklärt. Im Prinzip gibt es nur einen kleinen Absatz der sagt, dass man den normalen Euklid-Algorithmus ja auch auf Polynome übertragen könne. Die Polynome in der Aufgabe sind recht ähnlich, die Lösung nennt aber praktisch nur den ggT und für die Frage, ob dieser eindeutig ist:
"Ein Polynom vom Grad 3, das beide Polynome teilt, gibt es nicht."
Das kann man jetzt interpretieren wie man will, aber ohne eine Definition bringt mir das nichts, was ich sicher verwenden kann.
Also gut, ich weiß zwar beim besten Willen nicht, wie das in meinen Vorlesungsstoff passt, aber naja, ist jetzt (fast) alles Wikipedia:
> Generell ist der ggT nur eindeutig bis auf eine Einheit.
a und b [mm] \in [/mm] R sind Einheiten wenn gilt a * b = b * a = 1
R ist ein (kommutativer) Ring mit 1.
Da wirds ja schon lustig. Mal ist R ein Ring mit 1 per Definition, und mal gibt es die Forderung, dass dieses R 1 sein soll, damit man überhaupt mit R[X], also dem Polynomring, weiterrechnen kann.
R ist also definiert als Ring mit 1. R[X] ist dann die Menge der Polynome mit den Koeffizienten aus R, und dieser kann somit nicht 1 sein.
Daher würde ich sagen, dass R = {35}.
35 * 35 ist natürlich nicht 1. Somit ist 35 keine Einheit, der Ring enthält keine Einheiten und das Polynom ist nicht eindeutig.
Jetzt mal weg von der oben gestellten Aufgabe:
Gegeben sei f(x)=1/2 [mm] x^2 [/mm] + 2 x + 2.
Entsprechend haben wir einen Ring R = {1/2, 2}
Es gibt also a,b [mm] \in [/mm] R mit a * b = b * a = 1
Somit sind a, b Einheiten und das Polynom ist nicht eindeutig, weil es 2 Einheiten gibt.
Und das heißt ja dann, dass nur ein Polynom wie bspw. [mm] x^2 [/mm] + x + 1 eindeutig sein kann, da im Ring nur 1 steht.
Aber, es gibt ja nur 1 Element, ist dieses Element sich selbst gegenüber eine Einheit?
Wenn dem wirklich so ist, kommt das dann der Aussage
"Das Polynom ist eindeutig, wenn es nicht reduzierbar ist" recht nahe, aber sicher nur hinreichend.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:36 Mo 28.07.2014 | | Autor: | M.Rex |
Hallo
> Hi,
>
> das Buch oder etwas vergleichbares habe ich hier jetzt
> nicht.
> Mir steht hier Steger - Diskrete Strukturen Band 1 in 2.
> Auflage und ein paar Beispiel dinA4 Seiten zur Verfügung.
> In diesem Buch wird zwar so eine Aufgabe gestellt, aber da
> wird nichts zu erklärt. Im Prinzip gibt es nur einen
> kleinen Absatz der sagt, dass man den normalen
> Euklid-Algorithmus ja auch auf Polynome übertragen könne.
Dann versuche das soch mal
> Die Polynome in der Aufgabe sind recht ähnlich, die
> Lösung nennt aber praktisch nur den ggT und für die
> Frage, ob dieser eindeutig ist:
> "Ein Polynom vom Grad 3, das beide Polynome teilt, gibt es
> nicht."
Was ist an der Aussage denn noch unklar?
> Das kann man jetzt interpretieren wie man will, aber ohne
> eine Definition bringt mir das nichts, was ich sicher
> verwenden kann.
Welcher Begriff ist dir denn unklar?
Du hast, wenn du f(x) und g(x) in reelle Linearfaktoren zerlegst:
[mm] f(x)=x^4-x^3-x^2-2x=x\cdot(x-2)\cdot(x^{2}+x+1)
[/mm]
und [mm] g(x)=x^3+6x^2+6x+5=(x+5)\cdot(x^{2}+x+1)
[/mm]
Nun bist du erstmal wieder dran.
Zum Verfahren schau auch mal unter:
![[]](/images/popup.gif) diesem Beispiel
Marius
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:38 Mo 28.07.2014 | | Autor: | Morgyr |
Hi,
> Was ist an der Aussage denn noch unklar?
Überhaupt die Analogie.
"Bestimmte Sie einen ggT der beiden Polynome a und b. Zeigen Sie, dass dieser nicht eindeutig ist."
Die Lösung des ganzen soll dann sein:
"Der ggT lautet blub. Ein Polynom vom Grad 3, das beide Polynome teilt, gibt es nicht."
Natürlich gibt es dieses Polynom nicht, dafür ja die Polynomdivision.
Oder soll das ein Beweis sein, dass der Euklid-Algorithmus auch für Polynome richtig ist?
Ansonsten heißt das: Wenn der ggT vom selben Grad wie das kleinere der beiden Polynome ist, ist er eindeutig.
Also ein ggT ist [mm] 35x^2 [/mm] + 35 x + 35. Über die reelle Linearfaktorisierung:
[mm] 35*(x^2 [/mm] + x + 1).
Damit ist ein irreduzibles Polynom mit Faktor 35 gegeben
Teilt man g(x) durch diesen ggT erhält man:
[mm] {35*(x^2 + x + 1) * (\bruch{1}{35}x + \bruch{1}{7}) = (x+5)*(x^2 + x + 1)}
[/mm]
Joa..daran sieht man, dass auch [mm] 1000x^2 [/mm] + 1000x + 1000 ggT ist...eine sehr einleuchtende Zeile :D
Da es um Polynome geht, und man ja "Größe" überhaupt erstmal umdefinieren musste, um das Verfahren zu nutzen, geht es hier definitiv nicht um irgendwelche Koeffizienten, sondern nur um den Grad.
Also ist der ggT tatsächlich
für a [mm] \in \IR [/mm] a * [mm] (x^2 [/mm] + x + 1)
Also ist er nicht eindeutig.
So in etwa?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:45 Mo 28.07.2014 | | Autor: | hippias |
> Hi,
>
> > Was ist an der Aussage denn noch unklar?
> Überhaupt die Analogie.
> "Bestimmte Sie einen ggT der beiden Polynome a und b.
> Zeigen Sie, dass dieser nicht eindeutig ist."
> Die Lösung des ganzen soll dann sein:
> "Der ggT lautet blub. Ein Polynom vom Grad 3, das beide
> Polynome teilt, gibt es nicht."
> Natürlich gibt es dieses Polynom nicht, dafür ja die
> Polynomdivision.
Das verstehe ich nicht.
> Oder soll das ein Beweis sein, dass der Euklid-Algorithmus
> auch für Polynome richtig ist?
Vermutungsweise ist das der Zweck der Uebung: dass man den Algorithmus auf Poylnome uebertragen kann.
> Ansonsten heißt das: Wenn der ggT vom selben Grad wie das
> kleinere der beiden Polynome ist, ist er eindeutig.
Nein, das kann man so nicht sagen.
>
>
>
> Also ein ggT ist [mm]35x^2[/mm] + 35 x + 35. Über die reelle
> Linearfaktorisierung:
> [mm]35*(x^2[/mm] + x + 1).
> Damit ist ein irreduzibles Polynom mit Faktor 35 gegeben
> Teilt man g(x) durch diesen ggT erhält man:
> [mm]{35*(x^2 + x + 1) * (\bruch{1}{35}x + \bruch{1}{7}) = (x+5)*(x^2 + x + 1)}[/mm]
>
> Joa..daran sieht man, dass auch [mm]1000x^2[/mm] + 1000x + 1000 ggT
> ist...eine sehr einleuchtende Zeile :D
Ist aber trotzdem genau das, worum es geht: ist $d$ ein ggT, so ist auch $ad$, $a$ invertierbar, ein ggT (wie Du unten auch geschrieben hast).
> Da es um Polynome geht, und man ja "Größe" überhaupt
> erstmal umdefinieren musste, um das Verfahren zu nutzen,
> geht es hier definitiv nicht um irgendwelche Koeffizienten,
> sondern nur um den Grad.
Das ist sogar eine, meiner Meinung nach, wichtige Beobachtung: wenn man den Begriff "Groesse" auf des wesentliche reduziert, offenbaren sich ploetzlich viele neue Einsichten und Anwendungen. Ringe, bei denen das funktioniert, werden Euklidische Ringe genannt.
> Also ist der ggT tatsächlich
> für a [mm]\in \IR[/mm] a * [mm](x^2[/mm] + x + 1)
> Also ist er nicht eindeutig.
>
> So in etwa?
Ja. Aber ich habe nicht nachgerechnet, ob das Polynom stimmt. Es ist doch vielleicht ganz erfreulich, dass die Loesung des Problems gar nicht so kompliziert ist, wenn man sich ersteinmal an die Ausdrucksweise der Mathematik gewoehnt hat.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:36 Mo 28.07.2014 | | Autor: | Morgyr |
Lesen und Schreiben müsste man könne, dann erscheint das alles wirklich deutlich einfacher. Und bevor man über irgendwas nachdenkt, erstmal hinschreiben. Oft kommen die Steine dann schon ins Rollen.
Diese Erkenntnisse heute :D Da wünscht man sich schon fast, man hätte mehr als 3 Tage bis zur Klausur.
Gut, dann ist das für mich soweit zufriedenstellend. Vor allem nun auch eine Lösung ohne die Ringe. Die werden in meinem Buch nur in einem kleinen Satz im letzten Thema erwähnt, insofern wäre das, meines Erachtens nach, hier auch nicht anders gewollt.
Vielen Dank euch drei.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:48 Mo 28.07.2014 | | Autor: | Marcel |
Hallo Mogyr,
Dein Problem hat sich ja gelöst. Aber mal ein paar Sachen:
$a [mm] \in [/mm] R$ heißt Einheit, wenn es ein $b [mm] \in [/mm] R$ mit [mm] $a*b=b*a=1\,$ [/mm] gibt. Wenn Du
natürlich $a,b [mm] \in [/mm] R$ mit [mm] $a*b=b*a=1\,$ [/mm] findest, folgt daraus sofort, dass sowohl
[mm] $a\,$ [/mm] als auch [mm] $b\,$ [/mm] Einheiten sind. Einheiten sind hier die invertierbaren
Elemente. Was Du oben mit [mm] $R=1\,$ [/mm] sagen wolltest, verstehe ich nicht.
Was den [mm] $\text{ggT}$ [/mm] zweier Polynome betrifft: Hier sind die Einheiten die konstanten
Funktionen ungleich [mm] $0\,.$ [/mm] Wenn also
[mm] $d\,$ [/mm] der [mm] $\ggT$ [/mm] von zwei Polynomen ist,
dann auch
$c*d$ mit einem konstanten Polynom [mm] $c\not=0\,.$
[/mm]
Das ganze ist wenig verwunderlich:
Betrachte mal [mm] $f(x)=x^2-1$ [/mm] und [mm] $g(x)=x-1\,.$ [/mm] Dann ist
[mm] $\ggT(f,g)$ [/mm] ein Teiler sowohl von [mm] $f\,$ [/mm] als auch von [mm] $g\,,$ [/mm] der zudem erfüllt:
Ist das Polynom [mm] $t\,$ [/mm] auch ein Teiler von [mm] $f\,$ [/mm] und [mm] $g\,,$ [/mm] dann ist [mm] $t\,$ [/mm] auch ein Teiler von [mm] $\ggT(f,g)\,.$ [/mm]
Jedes Polynom $c*g$ mit $c [mm] \not=0$ [/mm] erfüllt aber das Gewünschte.
Und klar: Im Raum der Polynome ist die Funktion, die konstant den Wert 1
annimmt, die multiplikative [mm] $1\,.$ [/mm] Damit bekommt man direkt raus, was die
Einheiten sind.
P.S. Ich habe nie Algebra gehört, daher bin ich sicher in manchen Notationen
nicht so fit. Wenn man also irgendwo strenggenommen hier von
Polynomfunktionen sprechen müßte oder man anstatt nur [mm] $f\,$ [/mm] eigentlich
[mm] $f(x)\,$ [/mm] schreiben müsste, dann sehe man es mir nach und schreibe es einfach
korrigiert in einer Mitteilung. Ich denke aber, inhaltlich ist das klar, was ich
meine.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:51 Di 29.07.2014 | | Autor: | Morgyr |
Hi.
Mir fehlt nach wie vor das Verständnis was überhaupt im Ring steht.
Habe hier jetzt erstmal noch bisschen was zu Algorithmen zu tun, dann komme ich noch zu Gruppen und endlichen Körper. Entsprechend werde ich die Ringe bestimmt noch grob anschneiden, und dann nochmal hier nachfragen, wenn dann noch was unklar ist.
Vielen Dank soweit.
|
|
|
|
