Euklidischer Algorithmus < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:44 So 20.10.2013 | | Autor: | Franhu |
| Aufgabe | Seien a,b positive natürliche Zahlen mit a > b. Mit dem Euklid-Algorithmus erhalten wir natürliche Zahlen
[mm] r_{0} [/mm] = a > [mm] r_{1} [/mm] = b > ... > [mm] r_{k} [/mm] > [mm] r_{k+1} [/mm] = 0 und [mm] q_{0}, [/mm] ... , [mm] q_{k-1},
[/mm]
so dass gilt [mm] r_{i+2} [/mm] = [mm] r_{i}-q_{i}*r_{i+1} [/mm] und gcd(a,b) = [mm] r_{k}. [/mm] Wir definieren jetzt ganze Zahlen [mm] x_{0}, [/mm] ... [mm] ,x_{k}, y_{0}, [/mm] ... , [mm] y_{k} [/mm] wie folgt:
[mm] x_{0} [/mm] = 1, [mm] x_{1} [/mm] = 0, [mm] x_{i+2} [/mm] = [mm] x_{i}-q_{i}*x_{i+1} [/mm] für 0 [mm] \le [/mm] i [mm] \le [/mm] k-2
[mm] y_{0} [/mm] = 0, [mm] y_{1} [/mm] = 1, [mm] y_{i+2} [/mm] = [mm] y_{i}-q_{i}*y_{i+1} [/mm] für 0 [mm] \le [/mm] i [mm] \le [/mm] k-2
Zeige dass gilt:
[mm] r_{i+2} [/mm] = [mm] x_{i+2}*a [/mm] + [mm] y_{i+2}*b [/mm] |
Hallo Zusammen
Ich habe hier schon Probleme mit der Definition der ganzen Zahlen, also für [mm] x_{0},.... [/mm] und [mm] y_{0}...
[/mm]
[mm] x_{0} [/mm] = 1, [mm] x_{1} [/mm] = 0,
[mm] x_{2} [/mm] = [mm] x_{0}-q_{0}*x_{1} [/mm] = 1 - [mm] q_{0} [/mm] * 0 = 1
[mm] x_{3} [/mm] = [mm] x_{1}-q_{1}*x_{2} [/mm] = 0 - [mm] q_{1} [/mm] * 1 = ? was ist nun [mm] q_{1}?
[/mm]
irgendwie verstehe ich diese Definition nicht! Könnt ihr mir weiterhelfen?
Wie soll ich dann mit dem Beweis beginnen wenn ich nicht einmal verstehe was hier passiert...
Danke und Gruss
Franhu
|
|
| |
|
Hallo Franhu,
es gibt doch noch eine dritte Rekursionsgleichung, die Du bisher nicht berücksichtigt hast, nämlich die zu [mm] r_{i+2}=\cdots.
[/mm]
Ansonsten lies mal ein bisschen zum ![[]](/images/popup.gif) erweiterten euklidischen Algorithmus und zum Lemma von Bézout. Darum gehts hier nämlich eigentlich...
Die Rekursion zu [mm] r_{i+2} [/mm] ist vor allem deswegen wichtig, weil ja sonst $a$ und $b$ gar nicht vorkommen.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:00 So 20.10.2013 | | Autor: | Franhu |
Hallo reverend
Danke für deine Antwort. Ich verstehe den Euklidischen Algorithmus und die Bezogt-Identität wenn es um konkrete Zahlen geht. Aber wie ich das hier nun muss beweisen kapier ich nicht.
Das einzig gemeinsame zwischen der definition von [mm] x_{0}...y_{0} [/mm] und dem Algorithmus von [mm] r_{i+2}= [/mm] ... ist ja das q.
Muss ich etwa nach q umformen und dann einsetzen um den Beweis zu erbringen?
Gruss Franhu
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:10 Di 22.10.2013 | | Autor: | tobit09 |
Hallo Franhu!
> Das einzig gemeinsame zwischen der definition von
> [mm]x_{0}...y_{0}[/mm] und dem Algorithmus von [mm]r_{i+2}=[/mm] ... ist ja
> das q.
>
> Muss ich etwa nach q umformen und dann einsetzen um den
> Beweis zu erbringen?
Das ist nicht nötig.
Zeige per Induktion nach $i$, dass für alle [mm] $i\in\{0,1,\ldots,k-2\}$ [/mm] die zu zeigende Gleichung gilt.
Rechne dazu die Gleichung für $i=0$ und (im Falle [mm] $k\ge3$) [/mm] für $i=1$ separat nach.
Zeige dann für [mm] $i\in\{2,\ldots,k-2\}$, [/mm] dass aus der Gültigkeit der Gleichheit für alle $i'< i$ die Gültigkeit der Gleichheit für $i$ folgt.
Immer wenn du dabei die zu zeigende Gleichheit für irgendwelche $i$ nachrechnen willst, kannst du wie folgt vorgehen:
Rechne nacheinander von beiden Seiten der zu zeigenden Gleichheit los und setze zunächst die Definitionen von [mm] $r_{i+2}$, $x_{i+2}$ [/mm] und [mm] $y_{i+2}$ [/mm] ein.
Viele Grüße
Tobias
|
|
|
|
