Euklid. Algorithmus Poly.ring < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 23:49 Mi 29.11.2006 | | Autor: | VHN |
| Aufgabe | Sei K ein Körper.
(i) Beweise den Euklidischen Algorithmus für den Polynomring K[X], d.h. zeige, dass zu f,g [mm] \in [/mm] K[X] mit f [mm] \not= [/mm] 0 Polynome r,s [mm] \in [/mm] K[X] mit deg s < deg f existieren, so dass
g = rf + s
gilt.
(ii) Zeige, dass die zwei Polynome r, s durch f und g eindeutig bestimmt sind.
|
Hallo zusammen!
In der Vorlesung haben wir folgendes definiert:
K[X] = { [mm] \summe_{n=0}^{\infty} a_{n}X^{n} [/mm] | [mm] \exists n_{0} \in \IN [/mm] : [mm] a_{n} [/mm] = 0 [mm] \forall [/mm] n [mm] \ge n_{0} [/mm] }.
bei der (i) muss ich den euklid. algorithmus für den polynomring zeigen. das habe wie folgt gezeigt:
diese gleichung g=rf+s ist ja der ansatz zur berechung des größten gemeinsamen teilers zweier polynome in dem fall.
wenn g=rf+s gilt, muss daraus doch auch folgen, dass es ein t [mm] \in [/mm] K[X] gibt, so dass gilt:
t|f und t|g gilt genau dann, wenn t|f und t|s gilt.
(t|f heißt, t teilt f.)
diese aussage beweise ich nun:
Sei f,g,r,s wie in der angabe.
[mm] \Rightarrow
[/mm]
Ich nehme an, dass t|f und t|g gilt.
zu zeigen ist also t|f und t|s.
da t|f laut annahme gilt, reicht es t|s zu zeigen.
Da t|f gilt, gibt es ein [mm] t_{f} [/mm] mit [mm] f=t_{f}t.
[/mm]
Da t|g gilt, gibt es ein [mm] t_{g} [/mm] mit [mm] g=t_{g}t.
[/mm]
Wegen g=rf+s gilt:
[mm] g=t_{g}t=fr+s=t_{f}tr+s
[/mm]
daraus folgt: [mm] s=t_{g}t-t_{f}tr=t(t_{g}-t_{f}r)
[/mm]
Also ist t ein teiler von s. es gilt t|s.
[mm] \Leftarrow
[/mm]
ich nehme an, dass t|f und t|s gilt.
zu zeigen ist also t|f und t|g.
t|f gilt nach annahme.
zu zeigen bleibt t|g.
es gibt ein [mm] t_{f} [/mm] mit [mm] f=t_{f}t [/mm] sowie ein [mm] t_{s} [/mm] mit [mm] s=t_{s}t.
[/mm]
Ich setze wieder in g=rf+s ein.
[mm] g=rt_{f}t [/mm] + [mm] t_{s}t [/mm] = [mm] t(rt_{f}+t_{s}).
[/mm]
daraus folgt, dass t ein teiler von g ist, also t|g.
jetzt bin ich mir nicht ganz sicher.
ich habe doch gerade die aussage "t|f und t|g gilt genau dann, wenn t|f und t|s gilt" bewiesen, falls g=rf+s gilt. kann ich jetzt daraus schließen, dass die Polynome r,s [mm] \in [/mm] K[X] existieren, so dass g=rf+s gilt. oder kann man das so garnicht sagen?
müsste in meinem beweis eigentlich irgendwo die aussage degs<degf auftauchen?
ich hoffe, ihr könnt mir da weiterhelfen. ich weiß nicht genau, ob ich die aussage (i) damit bewiesen habe.
zur (ii):
hier muss ich zeigen, dass die Polynome r,s durch f und eindeutig bestimmt sind.
Ich glaube, dass man hier mit mit dem grad der polynome arbeiten muss. aber ich weiß nicht genau wie.
der grad deg h eines polynoms h = [mm] \summe_{n=0}^{m} a_{n}X^{n} \in [/mm] K[X] ist doch die größte Zahl 0 [mm] \le [/mm] j [mm] \le [/mm] m sein, so dass [mm] a_{j} \not= [/mm] 0 gilt, oder auch [mm] -\infty, [/mm] wenn h=0.
ich habe meinen beweis anders versucht.
Seien r,s,r*,s* [mm] \in [/mm] K[X] mit degs<degf und degs*<degf so gewählt, dass
g=rf+s und g=r*f+s* gilt.
dann gilt also rf+s=r*f+s*.
s-s*=f(r-r*)
[mm] f=\bruch{s-s*}{r-r*}
[/mm]
da [mm] f\not= [/mm] 0 gilt:
deg f = [mm] deg(\bruch{s-s*}{r-r*}) [/mm] = z (*)
irgendwie bringt mich dieser ansatz nicht weiter. was kann ich denn aus (*) nun schließen?
könnt ihr mich verbessern bzw. mir einen tipp geben, wie ich die eindeutigkeit von r und s zeigen kann?
Vielen, vielen dank!
VH
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:16 Do 30.11.2006 | | Autor: | felixf |
Hallo,
ohne mir das durchgelesen zu haben: Warum machst du nicht einen konstruktiven Beweis (Induktion nach Grad von $g$), in dem du die bekannte Polynomdivision (wie du sie in der Praxis durchfuehren wuerdest, geht genauso wie in der Schule) nachbildest? So wird der Satz auch normalerweise gezeigt.
Zu (ii): Schau dir die Differenz von zwei solchen Darstellungen an, d.h. fuehre es auf den Fall $g = 0$ zurueck. Dann brauchst du nur noch etwas mit den Graden der Polynome rumzuspielen...
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:08 Sa 02.12.2006 | | Autor: | VHN |
Hallo felixf!
Vielen dank für deine antwort!
ich habe nun versucht, es so wie du mithilfe von induktion über deg(g)zu machen.
(i) g=rf+s
Es gilt doch:
deg(g) = deg(rf+s) = max{deg(rf);deg(s)} = max{deg(r)+deg(f);deg(s)}
Wegen deg(s)<deg(f) gilt also max{deg(r)+deg(f);deg(s)} = deg(r)+deg(f) = deg(rf)
Also: deg(g) = deg (rf)
es sei g = [mm] \summe_{i=0}^{m} a_{i}X^{i} [/mm] und deg(g) = x die größte Zahl 0 [mm] \le [/mm] x [mm] \le [/mm] m, so dass [mm] a_{x} \not= [/mm] 0 gilt.
weiter sei f = [mm] \summe_{i=0}^{n} b_{i}X^{i}.
[/mm]
Induktion über deg(g):
IA: deg(g) = [mm] -\infty [/mm] wenn g=0.
IV: deg(g) = deg (rf)= x
IS: deg(g) = x+1 wobei hier g = [mm] \summe_{i=0}^{m+1} a_{i}X^{i} [/mm] mit deg(g)=x+1=y die größte Zahl 0 [mm] \le [/mm] y [mm] \le [/mm] m, so dass [mm] a_{y} \not= [/mm] 0 gilt.
deg(g) = x+1 = deg(rf)+1 = (deg(r)+1)+deg(f)
Das ist klar, da falls g [mm] \summe_{i=0}^{m+1} a_{i}X^{i} [/mm] mit deg(g) = x+1 und f = [mm] \summe_{i=0}^{n} b_{i}X^{i} [/mm] ist, gilt:
[mm] \bruch{g}{f}=r*+s* [/mm] wobei deg(r*)=deg(r)+1 ist.
Ist mein beweis so richtig? Ich bin mir aber nicht sicher. Ich hoffe, ihr könnt mich verbessern und mir sagen, wo mein fehler ist. Vielen Dank.
(ii) Seien g=rf+s und g=r*f+s* zwei solche darstellungen, die den euklid. Algorithmus erfüllen.
es gilt: deg(g)=deg(rf) sowie deg(g)=deg(r*f)
Subtraktion der zweiten gleichung von der ersten ergibt:
deg(g)-deg(g) = 0 = deg(rf)-deg(r*f)
= deg(r)+deg(f)-deg(r*)-deg(f) = deg(r)-deg(r*)
also: deg(r)=deg(r*).
Daraus folgt, dass r=r*.
Dementsprechend folgt ebenso, dass s=s* gelten muss.
damit sind r und s eindeutig bestimmt.
stimmt mein beweis so? Ich bin dankbar für jede hilfe!
vielen dank!
VHN
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:54 So 03.12.2006 | | Autor: | Binie |
Hi VHN
Also nur mal schnell: bei dir ist irgendwie der Wurm drin:
Wenn deg(g) < deg(f) dann wähle einfach r = 0 und s=g dann gilt g = r*f + s = 0*f + g und deg(s)=deg(g) < deg(f). Damit ist dieser Fall schon mal fertig. Nun zum interessanteren Fall:
Wenn deg(g)>deg(f) musst du induktion machen, aber du hast ganz falsch begonnen: sei g= [mm] \summe_{i=1}^{n} a_i*X^{i} [/mm] und f = [mm] \summe_{j=1}^{m} b_j*X^{j}
[/mm]
Wenn du Induktion über deg(g)=n machst, beginnst du mit
Ind.Anfang: deg (g) = 0 also g konstant d.h. [mm] g=a_0, [/mm] dann aber auch f konstant (da ja deg(f)<deg(g)) d.h. [mm] f=b_0 [/mm] . Also wähle r= [mm] \bruch{a_0}{b_0} [/mm] und s=0
Ind.Vorauss.: die Beh gelte für alle Polynome mit Grad <n
Ind.Schritt: deg(g) = n+1, definiere ein h mit h= [mm] g-\bruch{b_{n+1}}{a_m}*f*X^{n-m+1} [/mm] es gilt deg(h)<deg(g) (weils den ersten Summanden raushaut) also nach Ind.Vor existieren p,q [mm] \in [/mm] K[X] mit h = q*f + p mit deg(p)< deg(f)
d.h. [mm] g-\bruch{b_{n+1}}{a_m}*f*X^{n-m+1} [/mm] = q*f + p also g = q*f + [mm] \bruch{b_{n+1}}{a_m}*f*X^{n-m+1} [/mm] + p = f*(q + [mm] \bruch{b_{n+1}}{a_m}*X^{n-m+1}) [/mm] + p
setze also r = q + [mm] \bruch{b_{n+1}}{a_m}*X^{n-m+1} [/mm] und s=p dann gilt
g=r*f+s und deg(s)<deg(f)
Und wegen der Eindeutigkeit (ii) weiß ich bei deiner Lösung auch nicht so recht, ich habs so gemacht:
Annahme es gebe g = [mm] r_1*f+s_1 [/mm] und g = [mm] r_2*f+s_2 [/mm] mit [mm] deg(s_1)
dann gilt klar [mm] r_1*f+s_1 [/mm] = [mm] r_2*f+s_2 [/mm] also [mm] s_2-s_1 [/mm] = [mm] (r_1-r_2)*f
[/mm]
nun ist also [mm] s_2-s_1 [/mm] ein vielfaches von f aber deg [mm] (s_2-s_1) \le deg(s_2)< [/mm] deg(f) also muss [mm] s_2-s_1=0 [/mm] sein. Also [mm] s_1=s_2 [/mm] und dann auch [mm] r_1=r_2 [/mm] und fertig.
Bin total müde, hoffe ich hab mich jetzt nicht vertippt, les morgen nochmal zur Kontrolle drüber, aber so in etwa geht es. Du hast gleich zu Beginn die Induktion schon falsch gemacht.
LG Binie
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:18 So 03.12.2006 | | Autor: | VHN |
Hallo Binie!
Vielen dank erstmal für deine hilfe.
Mein induktionsbeweis war ja anscheinend von vornerein falsch.
ich habe allerdings noch einige fragen zu paar dingen in deinem beweis, die ich nicht ganz nachvollziehen kann.
1) Wie kommst du auf diese darstellung von h im induktionsschritt?
und wie meinst du das mit "weils den ersten summanden raushaut"? Ich kann die indices von [mm] a_{m} [/mm] und [mm] b_{n+1} [/mm] sowie den exponenten von [mm] X^{n-m+1} [/mm] nicht nachvollziehen.
ich hoffe, du kannst es mir erklären.
2) die zweite frage wäre, wie du bei (ii) von [mm] deg(s_{2}-s_{1}) [/mm] < [mm] deg(s_{2}) [/mm] < deg(f) auf [mm] s_{2}-s_{1} [/mm] = 0 schließen kannst. ich verstehe da nicht richtig den zusammenhang.
Ich hoffe, du kannst mir das nochmal erklären. vielen dank!
VHN
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:05 Mo 04.12.2006 | | Autor: | Binie |
Hi VHN
Hab grad kaum Zeit nur schnell so viel:
auf das h bin ich gekommen, indem ich g durch f geteilt habe und dann ein wenig herumprobiert habe, dieses [mm] b_n+1 [/mm] und [mm] a_m [/mm] und so weiter kommt alles zustande wenn du einfach mal eine allgemeine Polynomdiv von g und f machst. Wie auch immer, dass mit dem "ersten Summanden raushauen" habe ich gesagt, als Erklärung, das deg h < deg g. Und was ich damit gemeint habe siehst du sofort, wenn du einfach mal f als die Summe (mit der ichs def habe) einsetzt in die Def von h. dann hauts einige Summanden weg und man sieht gleich, dass deg h < deg g
muss jetzt leider weg bis dann binie
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 19:36 Mo 04.12.2006 | | Autor: | VHN |
Hallo Binie!
danke für deine antwort!
Sorry, aber ich habe nicht ganz verstanden, was du mir erklärt hast.
ich habe versucht die polynomdivision zu machen, komme aber nicht auf dieses h wie bei dir.
Kannst du es mir vllt bitte nochmal erklären, wenn du mehr zeit hast?
kannst du mir vllt noch meine Frage zu der (ii) beantworten?
vielen vielen dank!
VHN
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:16 Mo 04.12.2006 | | Autor: | Binie |
Hi VHN
Bin mal wieder in Eile, habe aber grad gesehen, dass ich mich beim h tatsächlich vertippt habe, da müssen a und b vertauscht werden, also h = g - [mm] \bruch{a_{n+1}}{b_m}*f*X^{n-m+1}
[/mm]
wenn du nun f einsetzt kommt raus h = g - [mm] \bruch{a_{n+1}}{b_m}*(b_m*X^m+b_{m-1}*X^{m-1}+...)*X^{n-m+1} [/mm] also h = g - [mm] a_{n+1}*X^{n+1}+... [/mm] also weil ja g = [mm] a_{n+1}*X^{n+1}+... [/mm] fällt eben genau der erste Summand bei h weg und deg h < deg g.
Und auf dieses h bin ich gekommen indem ich [mm] a_{n+1}*X^{n+1}+a_n*X^n+.... [/mm] geteilt habe durch [mm] b_m*X^m+b_{m-1}*X^{m-1}+...) [/mm] mit Polynomdivision
Jetzt klarer? Sorry muss los. Hoff du siehst was ich gemacht hab.
LG Binie
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:20 Do 07.12.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
