Fibonacci

Eine besondere Eigenschaft

Wir werden eine besondere Eigenschaft der Fibonaccireihe ableiten.
Wenn a und b positive ganze Zahlen sind dann notieren wir die größte Zahl die sowohl a als auch b teilt mit (a,b) (der grösste gemeinsame Teiler (g.g.T.) von a und b).
Dann gilt für die Fibonaccireihe:
F_(n,m) = (F_n,F_m).
Um diesen Satz zu beweisen brauchen wir einige Hilfsformel.
Formel 1
F_m+n = F_m L_n - (-1)ⁿ F_m-n
Beweis: (für die Definition von r und s sieh hier )
(r-s) F_m L_n =
(r^m - s^m) (rⁿ + sⁿ) =
r^m+n - s^m+n + r^msⁿ - rⁿs^m =
(r-s) F_m+n + (rs)ⁿ(r^m-n - s^m-n) =
(r-s) F_m+n + (-1)ⁿ (r-s) F_m-n
Also haben wir gezeigt dass (r-s) F_m L_n = (r-s) F_m+n + (-1)ⁿ (r-s) F_m-n
und also dass F_m+n = F_m L_n - (-1)ⁿ F_m-n.

Wähle für k eine feste (positive ganze) Zahl. Mit Hilfe der Formel 1 werden wir zeigen dass (für jedes n) F_kn durch F_k geteilt werden kann:
Die Behauptung ist richtig für n=1 (trivial).
Bemerke dass (wähle n=m=k in Formel 1) F_2k = F_kL_k, also ist die Behauptung auch korrekt für n=2.
Wir müssen jetzt zeigen dass die Behauptung richtig ist für n=3, und danach für n=4, und dann für n=5, usw.
Mit anderen Worten, wenn ich die Richtigkeit der Behauptung für n<=N schon sichergestellt habe, wie zeige ich dann die Richtigkeit für n=N+1? Wohlan, weil wir schon als Bewiesen voraussetzen dass F_Nk und F_(N-1)k geteilt werden können durch F_k
ist das rechte Glied der Gleichung F_(N+1)k = F_Nk L_k - (-1)^k F_(N-1)k teilbar durch F_k und also auch das linke Glied. Aber das ist was wir zeigen wollten.
Offensichtlich ist die Behauptung für jedes n richtig.

Der g.g.T. (n,m) ist ein Teiler von sowohl n als auch m, also schliessen wir dass F_(n,m) sowohl ein Teiler von F_n ist, als auch von F_m, und infolgedessen von (F_n,F_m).
Wir müssen noch zeigen dass (n,m) der grösste aller Teiler von (F_n,F_m) ist.
Dazu brauchen wir die nächste Formel:
Formel 2
F_m L_n - F_n L_m = 2 (-1)ⁿF_m-n
Beweis:
(r-s)(F_m L_n - F_n L_m) =
(r^m - s^m)(rⁿ + sⁿ) - (rⁿ - sⁿ)(r^m + s^m) =
r^m+n + r^msⁿ - rⁿs^m - s^m+n - r^m+n - rⁿs^m + r^msⁿ + s^m+n =
2(r^msⁿ - rⁿs^m) =
2(rs)ⁿ(r^n-m - s^n-m) =
(r-s) 2(-1)ⁿF_n-m

Wir wissen dass F_(n,m) Teiler von F_n ist und auch von F_m.
Wir beantworten zuerst die Frage ob ein gemeinsaner Teiler von F_n und F_m gerade sein kann.
Die Antwort ist leicht zu geben, denn in der Fibonaccifolge und der Lucasfolge volgt nach jeder (g)eraden Zahl 2 (u)ngeraden Zahlen. Diese Zahlenfolgen zeigen das Muster u,u,g,u,u,g,u,u,g,... Von der Richtigkeit dieses Musters lässt man sich leicht überzeugen.
Folgerung: Ein gemeinsamer Teiler kann nur gerade sein wenn die Indizen m und n beiden durch 3 geteilt werden können.
Setze einstweilen voraus dass dies nicht der Fall ist. Gesetzt, X sei ein Teiler von F_n und auch von F_m. Dann ist X ungerade.
Wir müssen zeigen dass X <= F_(n,m).
Es gibt positive Zahlen p und q so dass (m,n) = p.m - q.n oder so dass (m,n) = q.n - p.m. (sieh für einen Beweis unten auf dieser Seite).
Formel 2 sagt uns dass für (zum Beispiel) (m,n) = p.m - q.n: F_pm L_qn - F_qn L_pm = 2 (-1)ⁿF_(m,n)
X ist ein Teiler von F_n und von F_m und ist deswegen auch ein Teiler von F_qn und von F_pm und teilt deshalb das linke Glied. Aber das bedeutet dass X auch ein Teiler ist von 2F_(m,n) und deshalb (da X ungerade ist) von F_(m,n). Damit ist bewiesen (wenn (m,n) nicht teilbar ist durch 3) dass F_(m,n) der größte gemeinsame Teiler ist von F_n und F_m.

Wir hatten vorausgesetzt dass (m,n) nicht teilbar ist durch 3. Ist dies doch der Fall, dann ersetzen wir Formel 2 durch F_m L_n/2 - F_n L_m/2 = (-1)ⁿF_m-n. Bemerke dass L_n/2 und L_m/2 nun ganze Zahlen sind.
Der Beweis dafür verläuft entsprechend dem vorangehenden.

Zum Schluss beweisen wir noch:
Wenn (m,n)=1 dann gibt es Zahlen p und q so dass pm+qn=1.
(Daraus lässt sich sofort schliessen: wenn (m,n)=d dann gibt es Zahlen p und q so dass pm+qn=d).
Die Sammlung V = {um+vn | u,v ganz} hat ein kleinstes positives Element, sage b.
Dann ist {kb | k ganz} eine Teilmenge von V.
Gesetzt, ym+zn sei ein Element von V und es gibt keine ganze Zahl k so dass ym+zn = kb.
Dann gibt es eine ganze Zahl k₁ so dass k₁b < ym+zn < (k₁+1)b.
Dann ist 0 < ym+zn - k₁b < b.
Da b das kleinste positive Element von V ist würde hieraus folgen dass ym+zn - k₁b kein Element von V sein würde; aber das ist falsch.
Also ist b ein Teiler von ym+zn für jedes y,z. Folglich sind m (=1.m+0.n) und n teilbar durch b. Schlussfolgerung: b = 1 und es gibt Zahlen u und v so dass 1 = um+vn.