Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » erw. Euklidischer Algorithmus, Induktionsbeweis

erw. Euklidischer Algorithmus, Induktionsbeweis

Universität / Fachhochschule

Teilbarkeit

Tags: Teilbarkeit

Tormes aktiv_icon

23:36 Uhr, 18.12.2011

Hallo Leute, ich komme leider bei einer Aufgabe nicht weiter und würde mich wieder sehr um eure Antwort freuen. Dieses mal soll ich eine Eigenschaft vom erweiterten euklidischen Algorithmus zeigen.

= =

Aufgabe

= =

Betrachten Sie den so genannten Erweiterten Euklidischen Algorithmus:
Eingabe: Zwei natüurliche Zahlen

a, b

mit

a \geq b

Ausgabe:

d =

ggT(a,b) sowie

x, y \in ℤ

mit

d = x \cdot a + y \cdot b

.

1. Setze

i = 0, r_{- 1} = a, r_{0} = b, x_{- 1} = 1, y_{- 1} = 0, x_{0} = 0, y_{0} = 1

(Startbelegungen)

2. Berechne

i \leftarrow i + 1

3. Berechne

q_{i} \leftarrow [\frac{r_{i - 2}}{r_{i - 1}}]

(Gaußklammer)

4. Berechne

r_{i} \leftarrow r_{i - 2} - q_{i} \cdot r_{i - 1}

5. Berechne

x_{i} \leftarrow x_{i - 2} - q_{i} \cdot x_{i - 1}

und

y_{i} \leftarrow y_{i - 2} - q_{i} \cdot y_{i - 1}

6. ist

r_{i} \neq 0

,so gehe zu Schritt

2,

ansonsten fahre mit Schritt 7 fort.

7. Gebe aus:

d = r_{i - 1}, x = x_{i - 1}

und

y = y_{i - 1}

Aufgabe: Zeigen Sie, dass die Berechnung der

x

und

y

korrekt ist, dass heißt, dass
für alle

i \in ℕ

gilt, dass:

r_{i} = x_{i} \cdot a + y_{i} \cdot b

Hinweis: Dieser Beweis ist am einfachsten mit einer vollstandigen Induktion über

i

zu führen. Das der Algorithmus terminiert und den korrekten ggT ausgibt ist nicht
mehr zu zeigen,

= =

mein Problem

= =

Ich habe mir mal eine Tabelle angelegt und dadurch verstanden wie der Algorithmus funktioniert, aber
ich weiss gar nicht wie ich die Induktion ansetzen soll um auf ein ordentliches Ergebnis zu kommen. Ich habe schon die Berechnungsformeln für

r_{i}, x_{i}

und

y_{i}

eingestzt und dann den Index erhöht...das hat mir aber mal gar nichts gebracht.
Tipps würden erstmal reichen, aber ich nehme auch gerne den vollständigen Induktionsschritt und -schluss.

Ich bedanke mich schonmal für Antworten :-)

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."