www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Algebra" - GGT zweier Polynome
GGT zweier Polynome < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Algebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

GGT zweier Polynome: Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
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.

        
Bezug
GGT zweier Polynome: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                
Bezug
GGT zweier Polynome: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

Bezug
                        
Bezug
GGT zweier Polynome: Antwort
Status: (Antwort) fertig Status 
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:
[]diesem Beispiel

Marius

Bezug
                                
Bezug
GGT zweier Polynome: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                                        
Bezug
GGT zweier Polynome: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                                                
Bezug
GGT zweier Polynome: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                                                        
Bezug
GGT zweier Polynome: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                                                
Bezug
GGT zweier Polynome: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                                                                        
Bezug
GGT zweier Polynome: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:15 Di 29.07.2014
Autor: Marcel

Hallo,

> Hi.
>
> Mir fehlt nach wie vor das Verständnis was überhaupt im
> Ring steht.

den Ring gibt es nicht. Du brauchst auch mehr, Du brauchst []faktorielle
Ringe
. In dem erwähnten Buch steht im Anhang, was genau man unter
Ringen versteht bzw. welche Begriffe er wie verwendet. Vielleicht kannst
Du ja auch

   []hierauf

zugreifen?

Aber ich denke, auch ohne absolut *alles im Detail* zu wissen, kannst Du
doch mit Blick auf die Definitionen - und vermutlich analog zu dem Wissen,
was Du aus anderen Bereichen erworben hast, das von mir Gesagte
nachvollziehen?
Und natürlich: Du teilst Dir Deine Zeit selbst und nach eigener Priorität ein,
das ist doch klar. :-)

Gruß,
  Marcel

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Algebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de