ggT(a k und a k-1)

Neue Frage »

11.11.2004, 23:11	freeangle	Auf diesen Beitrag antworten »
ggT(a k und a k-1) Also die Aufgabe lautet: Es seien $\begin{eqnarray} a_{2}=2 \end{eqnarray}$ und $\begin{eqnarray} a_{2}=2 \end{eqnarray}$ und $\begin{eqnarray} a_{k}= a_{k-1}+a_{k-2} \end{eqnarray}$ für $\begin{eqnarray} k\geq2 \end{eqnarray}$ . Zeigen sie mittels vollständiger Induktion für alle $\begin{eqnarray} k\geq2 \end{eqnarray}$ , dass 1 der grösste gemeinsame Teiler von $\begin{eqnarray} a_{k} \end{eqnarray}$ und $\begin{eqnarray} a_{k-1} \end{eqnarray}$ ist und dass der Euklidische Algorithmus für diese Zahlen in der (k-1)-ten Iteration abbricht. Ich hab da irgendwie überhaupt keinen Plan und weiß auch nicht wo ich anfangen soll ... Bitte helft mir..
11.11.2004, 23:44	freeangle	Auf diesen Beitrag antworten »
ich verzweifel hier echt bitte bitte helft mir doch jemand
12.11.2004, 00:00	Tobias	Auf diesen Beitrag antworten »
Du hast zweimal den Startwert für $\begin{eqnarray} a_2 \end{eqnarray}$ angegeben. Ich setze jetzt voraus, dass $\begin{eqnarray} a_1 = 1 \end{eqnarray}$ . Induktionsanfang: $\begin{eqnarray} k = 2 \end{eqnarray}$ $\begin{eqnarray} \text{ggT}(1,2) = 1 \end{eqnarray}$ Induktionsvoraussetung: $\begin{eqnarray} \text{Sei } k \in \mathbb{N}_{\geq 2}, \text{ so gilt } \text{ggT}(a_k, a_{k-1}) = 1 \; . \end{eqnarray}$ Induktionsschluss: $\begin{eqnarray} \text{ggT}(a_{k+1}, a_{k}) = \text{ggT}(a_{k-1} + a_{k}, a_{k}) = ... \end{eqnarray}$ Vielleicht bringt dich das weiter.
12.11.2004, 00:14	freeangle	Auf diesen Beitrag antworten »
wie kommst du denn auf $\begin{eqnarray} ggT(a_{k+1},a_{k})=ggT[a_{k-1}+a_{k}, a{k} \end{eqnarray}$ ? Also das erste ist mir ja noch klar auf das andere?
12.11.2004, 00:18	Tobias	Auf diesen Beitrag antworten »
Das hast du doch selber aufgeschrieben: $\begin{eqnarray} a_{k}= a_{k-1}+a_{k-2} \end{eqnarray}$
12.11.2004, 00:21	freeangle	Auf diesen Beitrag antworten »
JA stimmt das ist einleuchtend... ich weiß aber irgendwie trotzdem nicht wie ich weitermachen sollte...muss ich dann für $\begin{eqnarray} a_{k} \end{eqnarray}$ $\begin{eqnarray} a_{k-1} + a_{k-2} \end{eqnarray}$ einsetzen?
Anzeige

12.11.2004, 00:32	freeangle	Auf diesen Beitrag antworten »
Oh man ich hab überhaupt keinen blassen schimmer....oh man was soll das nur werden mit mir...
12.11.2004, 00:34	Tobias	Auf diesen Beitrag antworten »
Der Trick ist, sich zu überlegen was der ggT von $\begin{eqnarray} a_{k} + a_{k-1} \end{eqnarray}$ und $\begin{eqnarray} a_k \end{eqnarray}$ bedeutet. Der ggT ist eine ganze Zahl $\begin{eqnarray} z \end{eqnarray}$ , die sowohl $\begin{eqnarray} a_{k} + a_{k-1} \end{eqnarray}$ als auch $\begin{eqnarray} a_k \end{eqnarray}$ teilt, so dass sich ein ganzzahliger Quotient ergibt. Für jedes y, dass größer ist als z sind die Quotienten dann nichtmehr ganzzahlig. Also: Sei $\begin{eqnarray} z = \text{ggT}(a_k + a_{k-1}, a_k) \end{eqnarray}$ $\begin{eqnarray} \frac{a_k}{z} \end{eqnarray}$ ist ganzzahlig. $\begin{eqnarray} \frac{a_k + a_{k-1}}{z} \end{eqnarray}$ ist ganzzahlig. $\begin{eqnarray} \frac{a_k + a_{k-1}}{z} = \frac{a_k}{z} + \frac{a_{k-1}}{z} \end{eqnarray}$ Jetzt kann man eine Teilbarkeits-Aussage von $\begin{eqnarray} a_{k-1} \end{eqnarray}$ bezüglich z machen.
12.11.2004, 00:41	freeangle	Auf diesen Beitrag antworten »
kann man??? na dann müsste doch eigentlich $\begin{eqnarray} a_{k} + a_{k-1} =1 \end{eqnarray}$ nach Induktionsvorraussetzung... oder? denn das ist doch die Induktionvosrraussetzung
12.11.2004, 00:48	freeangle	Auf diesen Beitrag antworten »
Achso na dann dürfte doch $\begin{eqnarray} a_{k-1} \end{eqnarray}$ ein vielfaches von $\begin{eqnarray} a_{k} \end{eqnarray}$ sein.... also müsste $\begin{eqnarray} a_{k-1} \end{eqnarray}$ teibar sein durch $\begin{eqnarray} a_{k} \end{eqnarray}$
12.11.2004, 00:51	freeangle	Auf diesen Beitrag antworten »
Nee das kann ja auch nicht hinhauen
12.11.2004, 00:52	Tobias	Auf diesen Beitrag antworten »
neee, die Induktionsvoraussetzung ist, dass der ggT von beiden 1 ist, nicht die Summe. Schau her: $\begin{eqnarray} q := \frac{a_k}{z} \end{eqnarray}$ ganzzahlig, d.h. $\begin{eqnarray} q \in \mathbb{Z} \end{eqnarray}$ . Da aber z der ggT ist (hab ich ja so definiert) gilt auch: $\begin{eqnarray} \frac{a_k + a_{k-1}}{z} = q + \frac{a_{k-1}}{z} \end{eqnarray}$ ganzzahlig. Da q ganzzahlig ist, muss auch $\begin{eqnarray} \frac{a_{k-1}}{z} \end{eqnarray}$ ganzzahlig sein. Daraus schließen wir sofort, dass z sowohl $\begin{eqnarray} a_k \end{eqnarray}$ als auch $\begin{eqnarray} a_{k-1} \end{eqnarray}$ teilt. Außerdem ist z die größtmögliche Zahl, die $\begin{eqnarray} a_k \end{eqnarray}$ und $\begin{eqnarray} a_{k-1} \end{eqnarray}$ teilt. Nach Induktionsvoraussetzung ist $\begin{eqnarray} z = \text{ggT}(a_k, a_{k-1}) = 1 \end{eqnarray}$ und das war zu beweisen.
12.11.2004, 00:55	freeangle	Auf diesen Beitrag antworten »
Und warum bricht der Algorithmus nach dem (k-1) Iteration ab?
12.11.2004, 01:04	Tobias	Auf diesen Beitrag antworten »
Wir betrachten den Euklidischen Algorithmus für $\begin{eqnarray} (a_k, a_{k-1}) \end{eqnarray}$ . Zuerst setzen wir die Definition ein: $\begin{eqnarray} (a_{k-1} + a_{k-2}, a_{k-1}) \end{eqnarray}$ Der Euklidische Algo nimmt sich nun die kleinere der beiden Zahlen raus und teilt sie durch die größere. Wenn sich kein Rest ergibt hat man den ggT gefunden. Findet man einen Rest, so wird dieser gespeichert. Die kleinere Zahl ist hier $\begin{eqnarray} a_{k-1} \end{eqnarray}$ . $\begin{eqnarray} a_{k-1} \end{eqnarray}$ teilt natürlich $\begin{eqnarray} a_{k-1} + a_{k-2} \end{eqnarray}$ nicht (das haben wir ja gerade in der Induktion bewiesen). Der Rest ist $\begin{eqnarray} a_{k-2} \end{eqnarray}$ . Nun wird der Algorithmus von vorne gestartet mit den Argumenten $\begin{eqnarray} (a_{k-1}, a_{k-2}) \end{eqnarray}$ . Wenn du das verstanden hast kannst du das jetzt auch problemlos weiterführen.
12.11.2004, 01:11	freeangle	Auf diesen Beitrag antworten »
na die kleinere Zahl ist diesmal $\begin{eqnarray} a_{k-1} \end{eqnarray}$ aber $\begin{eqnarray} a_{k-1} \end{eqnarray}$ teilt nicht $\begin{eqnarray} a_{k-2} \end{eqnarray}$ und da müsste eigentlich dann als Rest $\begin{eqnarray} a_{k-1} \end{eqnarray}$ sein... und dann hätte man ja $\begin{eqnarray} ggT (a_{k-1},a_{k-1} \end{eqnarray}$ und da ist der Rest 0 d.h Abbruch
12.11.2004, 01:27	Tobias	Auf diesen Beitrag antworten »
Schade..offensichtlich hast dus doch nicht verstanden. Warum ist denn $\begin{eqnarray} a_{k-1} \end{eqnarray}$ kleiner als $\begin{eqnarray} a_{k-2} \end{eqnarray}$ ? Warum verwendest du die Definition nicht? Warum sollte ein Rest von $\begin{eqnarray} a_{k-1} \end{eqnarray}$ bleiben, wenn du durch eben diese Zahl dividierst? Evt. versuchst du die ganze Aufgabe nochmal strukturiert von vorne zu durchdenken.
12.11.2004, 09:31	freeangle	Auf diesen Beitrag antworten »
Ich plan das einfach nicht und ich muss das heute abgeben... hatte also keine Zeit mehr so lange dran zu grübeln... dabei saß ich schon den ganzen Tag dran... ICh bin einfach zu blond dazu... werde wohl mein Studium abbrechen... check das ehe alles nicht

Neue Frage »

Antworten »

ggT(a k und a k-1)

Verwandte Themen