Benachbarte Fibonacci-Zahlen teilerfremd

15.07.2022, 14:06

_Bastii

Benachbarte Fibonacci-Zahlen teilerfremd

Hallo,

ich komme bei dem Beweis nicht weiter, dass für zwei Fibonacci-Zahlen $\begin{eqnarray*} f_{n+1} \end{eqnarray*}$ und $\begin{eqnarray*} f_n \end{eqnarray*}$ gilt:
$\begin{eqnarray*} ggT(f_{n+1}, f_n) = 1 \end{eqnarray*}$

Ich habe es mit den Rechenregeln für den ggT versucht aber ich habe das Gefühl, dass ich mich im Kreis drehe.

$\begin{eqnarray*} ggT(f_{n+1}, f_n) = ggT(f_n + f_{n-1}, f_n) = ggT((f_n + f_{n-1}) + (-1) * f_n, f_n) = ggT(f_{n-1}, f_n) = ggT(f_{n-1}, f_{n-1} + f_{n-2}) = ... \end{eqnarray*}$

Ich weiß einfach nicht wie ich irgendwann auf die Form $\begin{eqnarray*} ggT(..., 1) \end{eqnarray*}$ kommen soll.

15.07.2022, 14:50

Huggy

Auf diesen Beitrag antworten »

RE: Benachbarte Fibonacci-Zahlen teilerfremd
Da hilft Fermats Methode des unendlichen Abstiegs.

15.07.2022, 15:14

_Bastii

Auf diesen Beitrag antworten »

Das sagt mir leider nichts.
Zum jetzigen Zeitpunkt hatten wir in der Vorlesung nur die Teilbarkeit, Division mit Rest, ggT, kgV, Teilerfremdheit und den Anfang zum Thema Primzahlen.

15.07.2022, 15:41

Huggy

Auf diesen Beitrag antworten »

Mehr brauchst du auch nicht. Zeige, wenn $\begin{eqnarray*} f_n \end{eqnarray*}$ und $\begin{eqnarray*} f_{n+1} \end{eqnarray*}$ einen gemeinsamen Teiler $\begin{eqnarray*} q > 1 \end{eqnarray*}$ hätten, dann würde $\begin{eqnarray*} q \end{eqnarray*}$ auch $\begin{eqnarray*} f_{n-1} \end{eqnarray*}$ teilen. Dann hätten aber auch $\begin{eqnarray*} f_{n-1} \end{eqnarray*}$ und $\begin{eqnarray*} f_n \end{eqnarray*}$ einen gemeinsamen Teiler und nach demselben Schema dann $\begin{eqnarray*} f_{n-2} \end{eqnarray*}$ und $\begin{eqnarray*} f_{n-1} \end{eqnarray*}$ . Man steigt so bei dem Index der Fibonaccizahlen immer weiter ab. Unendlich ist dieser Abstieg nicht wirklich. Man kommt zum Schluss, dass auch $\begin{eqnarray*} f_1 \end{eqnarray*}$ und $\begin{eqnarray*} f_2 \end{eqnarray*}$ den gemeinsamen Teiler $\begin{eqnarray*} q \end{eqnarray*}$ haben müssten. Da das nicht der Fall ist, muss die Annahme, es gäbe zwei aufeinanderfolgende Fibonaccizahlen mit gemeinsamem Teiler falsch sein.

https://de.wikipedia.org/wiki/Unendlicher_Abstieg

15.07.2022, 17:49

teilo

Auf diesen Beitrag antworten »

Alternativ auch per Induktion, siehe z.B. hier :

matheboard.de/archive/15404/thread.html

15.07.2022, 18:31

_Bastii

Auf diesen Beitrag antworten »

Ah okay, danke.

Ich habe den Ansatz per Induktion nochmal selbst versucht:

Induktionsanfang:
$\begin{eqnarray*} ggT(f_1, f_2)=ggT(1,1)=1 \end{eqnarray*}$

Induktionsvoraussetzung:
$\begin{eqnarray*} ggT(f_{k+1},f_k)=1 \end{eqnarray*}$

Induktionsbehauptung:
$\begin{eqnarray*} ggT(f_{(k+1)+1}, f_{k+1})=1 \end{eqnarray*}$

$\begin{eqnarray*} ggT(f_{k+2},f_{k+1})=ggT(f_{k+1}+f_k, f_{k+1})=ggT(f_k+1*f_{k+1}, f_{k+1})=ggT(f_k, f_{k+1}=ggT(f_{k+1}, f_k)=1 \end{eqnarray*}$

Im letzten Schritt verwende ich einfach die Induktionsvoraussetzung und die Regel $\begin{eqnarray*} ggT(b,b')=ggT(b + k * b', b') \end{eqnarray*}$ hatten wir in der Vorlesung gegeben.

15.07.2022, 19:10

HAL 9000

Auf diesen Beitrag antworten »

Allgemeiner gilt sogar $\begin{eqnarray*} \operatorname{ggT}\left(f_n,f_m\right) = f_{\operatorname{ggT}\left(n,m\right)} \end{eqnarray*}$ .

15.07.2022, 22:45

teilo

Auf diesen Beitrag antworten »

Zitat:

...und die Regel ggT(b,b')=ggT(b+k*b' , b') hatten wir in der Vorlesung gegeben

Da passt für k=1 ja dann optimal zur Aufgabe und wird wohl für den Lösungsweg auch gewollt für den Einsatz sein.

Zitat:

$\begin{eqnarray*} ggT(f_{k+2},f_{k+1})=ggT(f_{k+1}+f_k, f_{k+1})=ggT(f_k+1*f_{k+1}, f_{k+1})=ggT(f_k, f_{k+1}=ggT(f_{k+1}, f_k)=1 \end{eqnarray*}$

Ich verstehe nur nicht ganz, warum du nicht direkt nur $\begin{eqnarray*} ggT(f_{k+2},f_{k+1})=ggT(f_{k+1}+f_k, f_{k+1})\underbrace{=}_{Skript}ggT(f_k,f_{k+1})\underbrace{=}_{IV}1 \end{eqnarray*}$ geschrieben hast.

Neue Frage »

Antworten »

Benachbarte Fibonacci-Zahlen teilerfremd

Verwandte Themen