Fibonacci-Zahlen und ggT

08.11.2019, 17:47	AhmadMiri	Auf diesen Beitrag antworten »
Fibonacci-Zahlen und ggT Meine Frage: Wir haben heute in der Schule im Mathe Lk folgende Aufgabe bekommen. Alle anderen habe ich verstanden, nur die nicht. Ich würde gerne wissen, wie ihr die lösen würdet, da mir diese Aufgabe große Kopfschmerzen bereitet. Meine Ideen: Zeigen Sie, dass $\begin{eqnarray} ggT(f_{k},f_{p})=f_{ggT(k,p)} \end{eqnarray}$ für $\begin{eqnarray} k,p \in \mathbb{N} \end{eqnarray}$
08.11.2019, 17:55	HAL 9000	Auf diesen Beitrag antworten »
Das ist nicht gerade trivial - hilfreich wären als Vorarbeit einige Eigenschaften der Fibonacci-Folge, z.B. sowas wie $\begin{eqnarray} f_{m+n+1} = f_{m+1}f_{n+1} + f_mf_n \end{eqnarray}$ Wäre daher gut, wenn du mal auflistest, was du in der Hinsicht schon im "Werkzeugkasten" hast, damit wir nicht bei Null anfangen müssen...
08.11.2019, 18:41	AhmadMiri	Auf diesen Beitrag antworten »
@HAL 9000 Sry habe ich vergessen
08.11.2019, 19:08	HAL 9000	Auf diesen Beitrag antworten »
Tja, damit sind schon mal ca. 80% der Arbeit erledigt... Es reicht die Behauptung für o.B.d.A. $\begin{eqnarray} k\leq p \end{eqnarray}$ nachzuweisen. Für $\begin{eqnarray} k=0 \end{eqnarray}$ und auch für $\begin{eqnarray} k=p \end{eqnarray}$ ist das ganze trivialerweise erfüllt. Im Restfall $\begin{eqnarray} 0<k<p \end{eqnarray}$ rechnen wir $\begin{eqnarray} \operatorname{ggT}\left(f_k,f_p\right) \stackrel{(1)}{=} \operatorname{ggT}\left(f_k,f_{k-1}f_{p-k}+f_kf_{p-k+1}\right) = \operatorname{ggT}\left(f_k,f_{p-k}f_{k-1}\right) \stackrel{(2)}{=} \operatorname{ggT}\left(f_k,f_{p-k}\right)\qquad () \end{eqnarray}$ Bei (1) wird die Eigenschaft $\begin{eqnarray} f_{n+m}=f_{n-1}f_m+f_nf_{m+1} \end{eqnarray}$ für $\begin{eqnarray} m=p-k,n=k \end{eqnarray}$ genutzt, bei (2) dann $\begin{eqnarray} \operatorname{ggT}\left(f_k,f_{k-1}\right) = 1 \end{eqnarray}$ , was man leicht per Vollständiger Induktion nachweisen kann. Mit Vorarbeit () kann man die eigentliche Behauptung dann indirekt beweisen: Angenommen, die Behauptung ist falsch, dann gibt es unter allen Paaren $\begin{eqnarray} (k,p) \end{eqnarray}$ mit $\begin{eqnarray} 0<k<p \end{eqnarray}$ , für die die Behauptung nicht erfüllt ist, mindestens eins mit minimalen $\begin{eqnarray} p \end{eqnarray}$ , nennen wir es $\begin{eqnarray} (k^,p^) \end{eqnarray}$ . Wegen $\begin{eqnarray} k^<p^* \end{eqnarray}$ sowie $\begin{eqnarray} p^-k^<p^* \end{eqnarray}$ ist die Behauptung dann aber wegen dieser Minimalitätseigenschaft für das Paar $\begin{eqnarray} \left(k^,p^-k^\right) \end{eqnarray}$ erfüllt! Mit () folgt dann via $\begin{eqnarray} f_{\operatorname{ggT}\left(k^,p^\right)} \neq \operatorname{ggT}\left(f_{k^},f_{p^}\right) \stackrel{()}{=} \operatorname{ggT}\left(f_{k^},f_{p^-k^}\right) = f_{\operatorname{ggT}\left(k^,p^-k^\right)} = f_{\operatorname{ggT}\left(k^,p^*\right)} \end{eqnarray}$ ein Widerspruch. EDIT (14.11.): Interesse verloren, oder so mit der Antwort zufrieden, dass man sich nicht mehr blicken lässt? Wie so oft bleibt das wohl im Dunkeln.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »