Euklidischer Algorithmus < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:59 Mi 14.05.2008 | | Autor: | Tommylee |
| Aufgabe | Es seien Polynome p,q uber dem Körper [mm] \IK [/mm] und q/not= 0. Wir setzen [mm] r_{0}:=p [/mm] und [mm] r_{1}:=q. [/mm] Nach Satz 15 der Vorlesung existieren 2 Polynome
[mm] r_{2},s_{1} [/mm] mit Grad [mm] r_{2} [/mm] < [mm] r_{1} [/mm] und
[mm] r_{0} [/mm] = [mm] s_{1} [/mm] * [mm] r_{1} [/mm] + [mm] r_{2}
[/mm]
wenn dann [mm] r_{2} \not= [/mm] 0 ist , existieren [mm] r_{3},s_{2} \in \IK[x] [/mm] mit Grad
[mm] r_{3}< [/mm] Grad [mm] r_{2} [/mm] und
[mm] r_{1} [/mm] = [mm] s_{2} [/mm] * [mm] r_{2} [/mm] + [mm] r_{3} [/mm] usw.
zeigen Sie :
a) Es gibt ein n [mm] \in \IN [/mm] mit [mm] r_{n+1} [/mm] = 0
b) [mm] r_{n} [/mm] ist dann eine Teiler von p und q
c) [mm] r_{n} [/mm] ist ggT von p und q, d.h.. wenn d [mm] \in \IK[x] [/mm] die Polynome p und q teilt so teilt d ebenfalls [mm] r_{n}
[/mm]
|
Hallo,
nur zu a (erstmal):
Grad [mm] r_{1} [/mm] > Grad [mm] r_{2} [/mm] > Grad [mm] r_{3}............> [/mm] Grad [mm] r_{n}
[/mm]
[mm] \Rightarrow \exists [/mm] Grad [mm] r_{n} [/mm] = 0
Grad [mm] r_{n} [/mm] = 0
[mm] \Rightarrow r_{n-2} [/mm] = [mm] s_{n-1} [/mm] * [mm] r_{n-1} [/mm] + [mm] r_{n} (r_{n} [/mm] ist Skalar)
[mm] \Rightarrow r_{n} [/mm] | [mm] r_{n-1}
[/mm]
[mm] \Rightarrow r_{n-1} [/mm] = [mm] s_{n} [/mm] * [mm] r_{n} [/mm] +0
[mm] r_{n-1} [/mm] = [mm] s_{n} [/mm] * [mm] r_{n} [/mm] + [mm] r_{n+1}
[/mm]
[mm] \Rightarrow r_{n+1} [/mm] = 0
[mm] \Rightarrow \exists [/mm] n [mm] \in \IN [/mm] mit [mm] r_{n+1} [/mm] = 0
ist das richtig , oder wenn es richtig ist , hab ich das geforderterte damit auch gezeigt oder nur eine Wahrheit ausgedrückt ?
Habt Dank für Rat
lg
Thomas
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 04:25 Mi 14.05.2008 | | Autor: | Tommylee |
Hallo ,
habe die Aufgabebstellung korrigiert ,
bin beim abtippen in einer Zeile verrutscht
lg
Thomas
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:19 Mi 14.05.2008 | | Autor: | Tommylee |
Hallo ,
ich habe aufgabenteil b gelöst durch
(Teilerrückfürung) (mir viel kein brsseres Wort ein).
~~~~~~~~~~~
Also beutzt hab ich die Zusammenhänge zunutze gemacht :
A | B und B | C [mm] \Rightarrow [/mm] A | C
A | (B + C) und A | B [mm] \Rightarrow [/mm] A | C
A | (B - C) und A | B [mm] \Rightarrow [/mm] A | C
A | (B - C) und A | C [mm] \Rightarrow [/mm] A | B
also :
ich nehme jetzt mal [mm] r_{n} [/mm] = [mm] r_{4} r_{n+1} [/mm] = [mm] r_{5} [/mm] = 0
und zeige das [mm] (r_{4}) (r_{0}) [/mm] = p und [mm] (r_{1}) [/mm] = q teilt :
Vorab die Durchführung der Euklidischen Algorithmus :
[mm] r_{0} [/mm] = [mm] s_{1} [/mm] * [mm] r_{1} [/mm] + [mm] r_{2}
[/mm]
[mm] r_{1} [/mm] = [mm] s_{2} [/mm] * [mm] r_{2} [/mm] + [mm] r_{2}
[/mm]
[mm] r_{2} [/mm] = [mm] s_{3} [/mm] * [mm] r_{3} [/mm] + [mm] r_{3}
[/mm]
[mm] r_{3} [/mm] = [mm] s_{4} [/mm] * [mm] r_{4} [/mm] + [mm] r_{4}
[/mm]
[mm] r_{4} [/mm] = [mm] s_{5} [/mm] * [mm] r_{5} [/mm] + [mm] r_{5}
[/mm]
Zusammenhänge :
[mm] r_{5} [/mm] | [mm] r_{4}
[/mm]
[mm] r_{4} [/mm] | [mm] (r_{3} [/mm] - [mm] r_{5})
[/mm]
[mm] r_{3} [/mm] | [mm] (r_{2} [/mm] - [mm] r_{4})
[/mm]
[mm] r_{2} [/mm] | [mm] (r_{1} [/mm] - [mm] r_{3})
[/mm]
[mm] r_{1} [/mm] | [mm] (r_{0} [/mm] - [mm] r_{2})
[/mm]
[mm] \Rightarrow
[/mm]
[mm] r_{4} [/mm] | [mm] r_{3} [/mm] - [mm] r_{5}
[/mm]
[mm] r_{5} [/mm] | [mm] r_{4} \Rightarrow r_{5} [/mm] | [mm] r_{4}
[/mm]
[mm] r_{3} [/mm] | [mm] r_{2} [/mm] - [mm] r_{4} \Rightarrow r_{5} [/mm] | [mm] r_{2} [/mm] - [mm] r_{4}
[/mm]
[mm] \Rightarrow r_{5} [/mm] | [mm] r_{1} [/mm] - 2* [mm] r_{3} [/mm] + [mm] r_{5}
[/mm]
[mm] \Rightarrow r_{5}| r_{1} [/mm] - 2* [mm] r_{3}
[/mm]
[mm] \Rightarrow r_{5}| r_{0} [/mm] - [mm] r_{2} [/mm] - 2* [mm] r_{3}
[/mm]
[mm] \Rightarrow [/mm]
[mm] r_{5} [/mm] | [mm] r_{4}
[/mm]
[mm] r_{5}| r_{2} [/mm] - [mm] r_{4} \Rightarrow r_{1} [/mm] | [mm] r_{0} (r_{0} [/mm] = p)
[mm] r_{5}| r_{1} [/mm] - 2 * [mm] r_{4}
[/mm]
[mm] r_{5}| r_{3} \Rightarrow r_{5}| r_{1} (r_{0}= [/mm] p)
[mm] r_{n}| r_{p} \wedge r_{n}| r_{q} [/mm] qed.
lg Thomas
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:41 Mi 14.05.2008 | | Autor: | Tommylee |
Hallo , Bei meiner vorletzten Frage habe ich bis zur Überfälligkeit keine Antwort bekkommen. Nach der Überfälligkeit antwortete mir Somebody
und vor seinem Lösungsweg schrieb er mir dies.
Ich antworte nur, weil Deine Frage als überfällig markiert ist: denn mir ist Deine ganze Überlegung einfach zu kompliziert. Ich denke, dies muss sich einfacher zeigen lassen.
Ich stehe noch ziemlich am Anfang und fahre noch öfter über Hamburg nach München. Auch wenn es Euch zu kompliziert erscheint habe ich eine dankend gemeinte Bitte an Euch . Dass Ihr Euch die Zeit nimmt und mein
kompliziertes wirrwar durchdenkt ist für mich keinesfalls selbstverständlich
sondert es verdient hohe Achtung. Worum ich Euch lieb bitten möchte : schreibt mir doch einfach ein :
zu kompliziert , denk mal einfacher
Dann warte ich nicht so lange
vielen vielen vielen Dank
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 04:07 Do 15.05.2008 | | Autor: | felixf |
Hallo Thomas,
ich wuerde es so machen: zeige per Induktion Rueckwaerts nach $i$ (also erst fuer $i = n$, dann fuer $i = n-1$, dann fuer $i = n-2$ ...), dass [mm] $r_n$ [/mm] ein Teiler von [mm] $r_{i-1}$ [/mm] und [mm] $r_{i-2}$ [/mm] ist.
Fuer den Induktionsanfang hast du ja, dass [mm] $r_{n+1} [/mm] = 0$ ist, d.h. dass [mm] $r_n$ [/mm] ein Teiler von [mm] $r_{n-1}$ [/mm] ist. Was kannst du jetzt ueber [mm] $r_{n-2}$ [/mm] sagen?
(Das ist im Prinzip denke ich das gleiche was du gemacht hast, nur wesentlich kuerzer.)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:24 Mi 14.05.2008 | | Autor: | Tommylee |
Hallo ,
auch eine Antwort wie : Du bist völlig auf dem Holzweg würde mir ein bischen weiterhelfen. Ich scheine noch weit unter einem akzeptablen Niveau zu sein . Sollte ich die Lösung komplett anders angehen ,
ja und nein sind auch schon Hilfen
es geht um meine Frage um den euklidischen Algorithmus
Vielen Dank
Habt DAnk für Rat
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:16 Mi 14.05.2008 | | Autor: | Merle23 |
Auf was beziehst du dich?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:21 Mi 14.05.2008 | | Autor: | Tommylee |
HALLO,
ich beziehe mich auf meine Frage bei lineare algebra
Thema EUKLIDISCHER Algorithmus
lg
Thomas
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:31 Mi 14.05.2008 | | Autor: | Merle23 |
Ich mach ma nen Link dahin. Solltest du in Zukunft auch machen. Ausserdem steht dein anderer Thread doch noch auf 'unbeantwortet'.... da brauchst du nicht nen zweiten aufmachen, nur um auf den anderen zu verweisen!
Link
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 00:17 Do 15.05.2008 | | Autor: | Tommylee |
Hallo ,
könnte mir jemand sagen ob ich a und b richtig gelöst habe ??
Dabke
lg
Thomas
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 04:02 Do 15.05.2008 | | Autor: | felixf |
Hallo Thomas
> Es seien Polynome p,q uber dem Körper [mm]\IK[/mm] und q/not= 0. Wir
> setzen [mm]r_{0}:=p[/mm] und [mm]r_{1}:=q.[/mm] Nach Satz 15 der Vorlesung
> existieren 2 Polynome
> [mm]r_{2},s_{1}[/mm] mit Grad [mm]r_{2}[/mm] < [mm]r_{1}[/mm] und
>
> [mm]r_{0}[/mm] = [mm]s_{1}[/mm] * [mm]r_{1}[/mm] + [mm]r_{2}[/mm]
>
> wenn dann [mm]r_{2} \not=[/mm] 0 ist , existieren [mm]r_{3},s_{2} \in \IK[x][/mm]
> mit Grad
> [mm]r_{3}<[/mm] Grad [mm]r_{2}[/mm] und
>
> [mm]r_{1}[/mm] = [mm]s_{2}[/mm] * [mm]r_{2}[/mm] + [mm]r_{3}[/mm] usw.
>
> zeigen Sie :
> a) Es gibt ein n [mm]\in \IN[/mm] mit [mm]r_{n+1}[/mm] = 0
>
> b) [mm]r_{n}[/mm] ist dann eine Teiler von p und q
Hier soll wohl $n$ so gemeint sein, dass $n$ der groesste Index ist mit [mm] $r_n \neq [/mm] 0$. Wenn [mm] $r_n [/mm] = 0$ ist, dann stimmt das nur, wenn $p = 0 = q$ ist, im Widerspruch zur Voraussetzung.
> c) [mm]r_{n}[/mm] ist ggT von p und q, d.h.. wenn d [mm]\in \IK[x][/mm] die
> Polynome p und q teilt so teilt d ebenfalls [mm]r_{n}[/mm]
>
>
> Hallo,
>
> nur zu a (erstmal):
>
> Grad [mm]r_{1}[/mm] > Grad [mm]r_{2}[/mm] > Grad [mm]r_{3}............>[/mm] Grad
> [mm]r_{n}[/mm]
>
> [mm]\Rightarrow \exists[/mm] Grad [mm]r_{n}[/mm] = 0
Erstens: du meinst wohl eher: [mm] $\Rightarrow \exists [/mm] n [mm] \in \IN [/mm] : [mm] \mathop{Grad} r_n [/mm] = 0$.
Wenn du Aussagen aufschreibst, dann lies sie doch mal laut vor; wenn es sich wie ein sinnvoller Satz anhoert, ist die Wahrschienlichkeit, dass sie richtig formuliert sind, schon wesentlich hoeher. Bei dem was du geschrieben hast wuerd ich Daraus folgt: es gibt ein Grad [mm] $r_n [/mm] = 0$ lesen -- und das macht keimen Sinn. Das was ich aufgeschrieben hat liest sich so: Daraus folgt: es gibt ein $n [mm] \in \IN$ [/mm] mit Grad [mm] $r_n [/mm] = 0$. Das liest sich doch gleich viel besser, oder?
Zweitens: Die Aussage stimmt (auch in meiner korrigierten Form) nicht. Nimm z.B. die Polynome $p = q = [mm] x^2$. [/mm] Dann ist [mm] $r_2 [/mm] = 0$ und [mm] $r_3 [/mm] = 0$ und ..., und [mm] $r_1 [/mm] = [mm] r_0 [/mm] = [mm] x^2$. [/mm] Es stimmt also [mm] $\mathop{Grad} r_1 [/mm] > [mm] \mathop{Grad} r_2$, [/mm] jedoch folgt daraus nicht die Existenz eines Indices $n [mm] \in \IN$ [/mm] mit [mm] $\mathop{Grad} r_n [/mm] = 0$.
Das brauchst du aber auch ueberhaupt nicht.
Argumentier doch lieber andersherum, das ist eleganter: angenommen, [mm] $q_n \neq [/mm] 0$ fuer alle $n [mm] \in \IN$. [/mm] Dann gilt [mm] $\mathop{Grad} r_1 \ge \mathop{Grad} r_2 [/mm] + 1 [mm] \ge \mathop{Grad} r_3 [/mm] + 2 [mm] \ge [/mm] ... [mm] \ge \mathop{Grad} r_n [/mm] + (n - 1)$.
Wenn also [mm] $\mathop{Grad} r_1 [/mm] = n$ ist, dann ist $n = [mm] \mathop{Grad} r_1 \ge \mathop{Grad} r_{n+2} [/mm] + (n + 2 - 1)$, also [mm] $\mathop{Grad} r_n \le [/mm] n - n - 1 = -1$. Dies kann nur der Fall sein, wenn [mm] $\mathop{Grad} r_n [/mm] = [mm] -\infty$ [/mm] ist, also [mm] $r_n [/mm] = 0$.
LG Felix
|
|
|
|
