ggT bestimmen

25.07.2011, 22:57

Fetterchefkoch

ggT bestimmen

ggT bestimmen von Zahlen ist einfach mit Euklidischem Algorithmus...
Jedoch wüsste ich gerne wie man einen ggT von 2 Funktionen bestimmt? Ich kann mir auch nicht Vorstellen was ein ggT von 2 Funktionen darstellen soll.

Ich habe jedenfalls ein Beispiel: Funktion 1: $\begin{eqnarray*} y^2+x^2y+x \end{eqnarray*}$ , Funktion 2: $\begin{eqnarray*} y^2+xy+x^2 \end{eqnarray*}$ . Ich wende jetzt also den EEA an:
$\begin{eqnarray*} \begin{tabular}{c|c|c}$y^2+x^2y+y$&1&0\\\hline$y^2+xy+x^2$&0&1\\\hline$(x^2+x)y+(x^2+x$)&1&1\\\end{tabular} \end{eqnarray*}$

Was ich also probiert habe: ich habe in der 2. Funktion $\begin{eqnarray*} y^2 \end{eqnarray*}$ ersetzt durch den Rest von der 1. Funktion. Was mir im moment irgendwie überhaupt nicht einleichtet wieso ich das gemacht habe.

Was ich eigentlich für logischer halten würde wäre: $\begin{eqnarray*} (x-x^2)+(x^2-x)|-1|1 \end{eqnarray*}$

Wäre froh, falls mir da jemand helfen könnte smile

.

P.S. hoffe ist in der richtigen Kategorie

26.07.2011, 16:13

Fetterchefkoch

Auf diesen Beitrag antworten »

RE: ggT bestimmen

Zitat:

$\begin{eqnarray*} \begin{tabular}{c|c|c}$y^2+x^2y+x$&1&0\\\hline$y^2+xy+x^2$&0&1\\\hline$(x^2+x)y+(x^2+x$)&1&1\\\end{tabular} \end{eqnarray*}$

habe natürlich falsch abgeschrieben.

Bin immernoch dran dieses Problem irgendwie zu lösen.
Habe dann auch mal was anderes probiert. Der Euklid'sche Algorithmus besagt: $\begin{eqnarray*} ggT(a,b)=s\cdot a+t\cdot b \end{eqnarray*}$
Also habe ich probiert eine Polynomdivision durchzuführen. Also $\begin{eqnarray*} \frac{y^2+x^2y+x}{y^2+xy+x^2}=1+(x^2-x)y+(x-x^2) \end{eqnarray*}$ . Aber auch nach dieser Polynomdivison weiss ich nicht wie ich Fortfahren muss.

Wäre wirklich um jede Hilfe froh smile

26.07.2011, 20:04

Dopap

Auf diesen Beitrag antworten »

RE: ggT bestimmen
wenn keiner "ran" will, dann versuch ich's 'mal

Zitat:

Original von Fetterchefkoch
Der Euklid'sche Algorithmus besagt: $\begin{eqnarray*} ggT(a,b)=s\cdot a+t\cdot b \end{eqnarray*}$

im normalen Fall ist der $\begin{eqnarray*} gT(f(x),g(x)) \end{eqnarray*}$ eine Funktion Q(x) für die gilt:

$\begin{eqnarray*} f(x)=Q(x)f_1(x) \land g(x)=Q(x)g_1(x) \end{eqnarray*}$

soweit klar, was dann aber das "grösste" Q(x) sein soll ist noch unklar. Es sei denn, man definiert eine solche Norm.
------------------------------------------------------------------
Deine Tabellen sind wohl Spezialbezeichner zur Polynomdivision.
Die erste Division sehe ich so:

$\begin{eqnarray*} \frac {f(x)}{g(x)}=1 \end{eqnarray*}$ der Rest $\begin{eqnarray*} R_1=y(x^2-x)+(x-x^2) \end{eqnarray*}$

oder $\begin{eqnarray*} R_1=y(x^2-x)-(x^2-x)=(y-1)(x^2-x) \end{eqnarray*}$

dieser Rest müsste nun wieder durch g(x) geteilt werden.
Wenn das nicht zufällig "aufgeht" seh ich schwarz, denn was wir hier machen ist doch gar keine Polynomdivision eher die Division zweier quadratischer Formen, also Relationen deren Graphen Kegelschnitte sind.

26.07.2011, 21:36

lgrizu

Auf diesen Beitrag antworten »

RE: ggT bestimmen

Zitat:

Original von Dopap

Wenn das nicht zufällig "aufgeht" seh ich schwarz, denn was wir hier machen ist doch gar keine Polynomdivision eher die Division zweier quadratischer Formen, also Relationen deren Graphen Kegelschnitte sind.

Das stimmt so nicht ganz, in der Algebra kann man ohne weiteres auch den Ring der Polynome in zwei Unbekannten betrachten.

26.07.2011, 22:26

Dopap

Auf diesen Beitrag antworten »

danke "Igrizu", dass du mein Bemühen um eine vorläufige Antwort respektiert hast.
Insgesamt hat jetzt "fetterchefkoch" doch 2 gestaffelte Antworten zur Verfügung.
Es war meine Intention, die Sache voranzubringen.

26.07.2011, 22:48

Fetterchefkoch

Auf diesen Beitrag antworten »

ok...
Also "Polynomdivision" funktioniert gar nicht... hab was schlimmeres herausbekommen als ich am anfang angefangen habe und zwar: $\begin{eqnarray*} 1+\frac{x^2y+2xy+x+y^2}{x^2-x^2y-xy+x} \end{eqnarray*}$ und irgendwie habe ich das Gefühl das ich auf keinen grünen Zweig komme wenn ich so weiter mache.

Habe aber grad vorher noch irgendwo gelesen, dass man beide Funktionen so multiplizieren soll, damit man auf das selbe kommt. Weiss einfach noch nicht wie ich das machen soll xD.

P.S. hab grad noch gesehen, dass es auf $\begin{eqnarray*} GF(8) \end{eqnarray*}$ ist. Ich weiss nicht ob diese Information wichtig bzw. nützlich ist, da ich nicht weiss was $\begin{eqnarray*} GF(8) \end{eqnarray*}$ ist xD

27.07.2011, 10:49

lgrizu

Auf diesen Beitrag antworten »

Wir betrachten einmal, wie in meinem letzte Post schon erwähnt, den Ring der Polynome in zwei Unbekannten, dieser ist R[x,y]=R[x][y].

Wir haben also zwei Polynome des Typs ay²+by+c, wobei a,b,c keine Elemente aus R sind, sondern ihrereseits wieder Elemente aus R[x], also Polynome in einer Unbekannten.
Wir können das ganze also genau so behandeln, wie ein Polynom in einer Unbekannten über einem Polynomring.

Die erste Polynomdivision ist richtig, bei der zweiten sollte dir Dopaps Umformung helfen:

$\begin{eqnarray*} \frac{y^2+xy+x^2}{(x^2-x) \cdot (y-1)}=\frac{1}{(x^2-x)} \cdot \frac{y^2+xy+x^2}{ (y-1)} \end{eqnarray*}$

Diese Polynomdivision sollte durchführbar sein, der verbleibende Rest ist ein Polynom in nur noch einer Unbekannten.

Wie gesagt, wir fassen das so auf, als handele es sich um R[y], wobei R seinerseits wieder ein Polynomring ist, die Elemente aus R "schleppen" wir einfach so mit.

28.07.2011, 10:41

Fetterchefkoch

Auf diesen Beitrag antworten »

Wie du mir geraten hast, habe ich die Polynomdivision durchgeführt von $\begin{eqnarray*} \frac{y^2+xy+x^2}{ (y-1)} \end{eqnarray*}$ , als Resultat habe ich bekommen $\begin{eqnarray*} y+1+x+\frac{x^2+1+x}{y-1} \end{eqnarray*}$ . Wie muss ich jetzt dies wieder mit $\begin{eqnarray*} \frac{1}{x^2-x} \end{eqnarray*}$ zusammensetzten?

Was also meine Idee zur Fortfahrung wäre ist, dass ich den Rest den ich bekommen habe durch $\begin{eqnarray*} \frac{1}{x^2-x} \end{eqnarray*}$ teile. Also, dass ich dann wieder eine Polynomdivison durchführe mit $\begin{eqnarray*} \frac{x^2+x+1}{x^2-x} \end{eqnarray*}$ . Das Resultat davon wäre dann $\begin{eqnarray*} 1+\frac{2}{x}+\frac{3}{x^2-x} \end{eqnarray*}$ .

Mein Problem im moment ist, dass ich nicht weiss wie ich die 2 Formeln zusammensetzen muss/kann/sinnvoll ist.

Gruss Fetter

28.07.2011, 13:27

lgrizu

Auf diesen Beitrag antworten »

Also ich verstehe deine Frage nicht....

Wir haben mit Euklid:

$\begin{eqnarray*} y^2+x^2+y+x=1 \cdot (y^2+xy+x^2) + ((x^2-x) \cdot (y-1) \end{eqnarray*}$

$\begin{eqnarray*} y^2+xy+x^2=(y+(x+1)) \cdot ((y-1)(x^2-x))+((x^2+x+1)(x^2-x)) \end{eqnarray*}$

Der letzte verbleibende Rest enthält kein y mehr, also sind wir fertig, da wir ja den Ring R[y] betrachten, wobei R selbst der Polynomring in einer Variablen ist.

28.07.2011, 13:51

Fetterchefkoch

Auf diesen Beitrag antworten »

Ich muss zeigen, ob diese beiden Funktionen teilerfremd (also ggT = 1) haben.

Da ich die Musterlösung habe, weiss ich, dass die beiden Funktionen Teilerfremd sind. Leider erklärt die Musterlösung nicht, wie sie vor gehen.

Oder hab ich einfach was verpasst und wir haben schon bewiesen, dass die Funktionen ggT=1 haben?

Falls du möchtest kann ich die Tabelle mal hier reinschreiben und du könntest mir dann vielleicht erklären wies funktioniert. :P

28.07.2011, 14:29

lgrizu

Auf diesen Beitrag antworten »

Das letzte Element hängt nicht mehr von y ab.

Sei R der Ring der Polynome, dann betarchten wir den Ring R[y], wir haben also mit Euklid:

$\begin{eqnarray*} f_1(y)=1 \cdot f_2(y) + r_1 \end{eqnarray*}$

$\begin{eqnarray*} f_2(y)=(y+x+1) r_1 + r_2 \end{eqnarray*}$

Nun ist $\begin{eqnarray*} r_2 \in R \end{eqnarray*}$ ......

Edit: Ich muss jetzt los und bin ab morgen imn Urlaub, ich hoffe, es findet sich noch jemand, der das hier zu Ende führt.

28.07.2011, 15:34

Fetterchefkoch

Auf diesen Beitrag antworten »

Ich muss an dieser Stelle leider zugeben, dass ich keine Ahnung von Ringen habe :P. Von dem her weiss ich nicht wie ich die Aufgabe jetzt lösen soll.

Neue Frage »

Antworten »

ggT bestimmen

Verwandte Themen