Subsections


9 Weitere Formeln


9.1 F2n = $ \sum_{{i=0}}^{{n}}$$ \binom {n}{i}$Fi

Wir verwenden die Eigenschaft aus Abschnitt 8, dann erhalten wir einerseits

$\displaystyle \lambda^{{2n}}_{}$ = F2n$\displaystyle \lambda$ + F2n-1

und andererseits unter Verwendung des Binomischen Satzes9

$\displaystyle \lambda^{{2n}}_{}$ = ($\displaystyle \lambda^{{2}}_{}$)n = ($\displaystyle \lambda$ +1)n = $\displaystyle \sum_{{i=0}}^{{n}}$$\displaystyle \binom{n}{i}$$\displaystyle \lambda^{{i}}_{}$ = $\displaystyle \sum_{{i=0}}^{{n}}$$\displaystyle \binom{n}{i}$(Fi$\displaystyle \lambda$ + Fi-1) = $\displaystyle \left(\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i}}\right.$$\displaystyle \sum_{{i=0}}^{{n}}$$\displaystyle \binom{n}{i}$Fi$\displaystyle \left.\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i}}\right)$ . $\displaystyle \lambda$ + $\displaystyle \left(\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i-1}}\right.$$\displaystyle \sum_{{i=0}}^{{n}}$$\displaystyle \binom{n}{i}$Fi-1$\displaystyle \left.\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i-1}}\right)$

Da aber für $ \lambda^{{2n}}_{}$ keine andere Zerlegung als F2n$ \lambda$ + F2n-1 existieren kann, muß folglich gelten:

F2n = $\displaystyle \sum_{{i=0}}^{{n}}$$\displaystyle \binom{n}{i}$Fi

und außerdem auch

F2n-1 = $\displaystyle \sum_{{i=0}}^{{n}}$$\displaystyle \binom{n}{i}$Fi-1

Dies ist übrigens auch leicht einzusehen, wenn man alternativ $ \mu^{{2n}}_{}$ = F2n$ \mu$ + F2n-1 sowie ($ \mu^{{2}}_{}$)n = ($ \mu$ +1)n = $ \left(\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i}}\right.$$ \sum_{{i=0}}^{{n}}$$ \binom {n}{i}$Fi$ \left.\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i}}\right)$ . $ \mu$ + $ \left(\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i-1}}\right.$$ \sum_{{i=0}}^{{n}}$$ \binom {n}{i}$Fi-1$ \left.\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i-1}}\right)$ ausrechnet und die Terme in die Binetsche Formel einsetzt.

Abschließend für die Betrachtung des Terms $ \lambda^{{2n}}_{}$ sei der Vollständigkeit halber noch auf eine dritte Umformungsvariante hingewiesen:

$\displaystyle \lambda^{{2n}}_{}$ = ($\displaystyle \lambda^{{n}}_{}$)2 = (Fn$\displaystyle \lambda$ + Fn-1)2 = Fn2$\displaystyle \underbrace{{\lambda^{2}}}_{{\lambda+1}}^{}\,$ +2Fn$\displaystyle \lambda$Fn-1 + F2-12 = (Fn2 +2FnFn-1)$\displaystyle \lambda$ + Fn2 + Fn-12

Daraus ergibt sich F2n = Fn2 +2FnFn-1 sowie F2n-1 = Fn2 + Fn-12. Addiert man zur ersteren Gleichung auf beiden Seiten Fn-12, so erhält man F2n + Fn-12 = Fn2 +2FnFn-1 + Fn-12 = (Fn + Fn-1)2 = Fn+12, und dies ist äquivalent zu F2n = Fn+12 - Fn-12 = ($ \underbrace{{F_{n+1}+F_{n-1}}}_{{L_{n}}}^{}\,$) . ($ \underbrace{{F_{n+1}-F_{n-1}}}_{{F_{n}}}^{}\,$), doch diese Formel kennen wir mit anderer Herleitung bereits aus Abschnitt 4.3.

9.2 Fk . n = $ \sum_{{i=0}}^{{n}}$$ \binom {n}{i}$Fi . Fki . Fk-1n-i

Auch auf die Gefahr hin, nun vollkommen zu langweilen, wenden wir das obige Prinzip aus 9.1 erneut an, diesmal um eine Formel für Fk . n zu bestimmen:

$\displaystyle \lambda^{{k\cdot n}}_{}$ = ($\displaystyle \lambda^{{k}}_{}$)n = (Fk . $\displaystyle \lambda$ + Fk-1)n = $\displaystyle \sum_{{i=0}}^{{n}}$$\displaystyle \binom{n}{i}$Fki . $\displaystyle \lambda^{{i}}_{}$ . Fk-1n-i = $\displaystyle \sum_{{i=0}}^{{n}}$$\displaystyle \binom{n}{i}$Fki . (Fi . $\displaystyle \lambda$ + Fi-1) . Fk-1n-i

= $\displaystyle \sum_{{i=0}}^{{n}}$$\displaystyle \binom{n}{i}$Fki . Fi . Fk-1n-i . $\displaystyle \lambda$ + Fki . Fi-1 . Fk-1n-i = $\displaystyle \left(\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i}\cdot F_{k}^{i}\cdot F_{k-1}^{n-i}}\right.$$\displaystyle \sum_{{i=0}}^{{n}}$$\displaystyle \binom{n}{i}$Fi . Fki . Fk-1n-i$\displaystyle \left.\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i}\cdot F_{k}^{i}\cdot F_{k-1}^{n-i}}\right)$ . $\displaystyle \lambda$ + $\displaystyle \left(\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i-1}\cdot F_{k}^{i}\cdot F_{k-1}^{n-i}}\right.$$\displaystyle \sum_{{i=0}}^{{n}}$$\displaystyle \binom{n}{i}$Fi-1 . Fki . Fk-1n-i$\displaystyle \left.\vphantom{\sum_{i=0}^{n}\binom{n}{i}F_{i-1}\cdot F_{k}^{i}\cdot F_{k-1}^{n-i}}\right)$

Daraus folgt dann analog zu oben:

Fk . n = $\displaystyle \sum_{{i=0}}^{{n}}$$\displaystyle \binom{n}{i}$Fi . Fki . Fk-1n-i

sowie

Fk . n-1 = $\displaystyle \sum_{{i=0}}^{{n}}$$\displaystyle \binom{n}{i}$Fi-1 . Fki . Fk-1n-i

Die beiden Formeln sind übrigens auch für k = 1 korrekt, wenn wir 00 : = 1 verlangen, da in beiden Formeln der Teilfaktor Fk-1n-i = F0n-i = 0n-i dann alle Summanden bis auf den Term $ \binom{n}{n}$Fn . F1n . F0n-n = Fn (bzw. für Fk . n-1 bis auf den Term $ \binom{n}{n}$Fn-1 . F1n . F0n-n = Fn-1) auf null setzt. (n sollte aber in allen Fällen eine positive natürliche Zahl sein.)

Als möglicherweise noch recht interessantes Beispiel der Anwendung obiger Formel können wir F3n betrachten. Es ergibt sich zum einen

F3n = $\displaystyle \sum_{{i=0}}^{{n}}$$\displaystyle \binom{n}{i}$Fi . F3i . F2n-i = $\displaystyle \sum_{{i=0}}^{{n}}$$\displaystyle \binom{n}{i}$Fi . 2i

und da wir wegen der Kommutativität der Multiplikation auch noch k und n vertauschen dürfen, auch:

F3n = Fn . 3 = $\displaystyle \sum_{{i=0}}^{{3}}$$\displaystyle \binom{3}{i}$Fi . Fni . Fn-13-i = 0 + 3F1 . Fn1 . Fn-12 +3 . F2 . Fn2 . Fn-11 +1 . F3 . Fn3 . Fn-10

= 3FnFn-12 +3Fn2Fn-1 +2Fn3 = Fn . (3Fn-12 +3FnFn-1 +2Fn2)


9.3 Fn-$\scriptstyle \Delta$ . Fn+$\scriptstyle \Delta$

Fn2 - (- 1)n+$\scriptstyle \Delta$ . F$\scriptstyle \Delta$2 = Fn-$\scriptstyle \Delta$ . Fn+$\scriptstyle \Delta$ = $\displaystyle {\frac{{F_{n}^{2}L_{\Delta}^{2}-F_{\Delta}^{2}L_{n}^{2}}}{{4\cdot(-1)^{\Delta}}}}$

9.3.0.1 Beweis:

Wir verwenden die geschlossene Form. Somit ergibt sich einerseits

Fn2 - (- 1)n+$\scriptstyle \Delta$ . F$\scriptstyle \Delta$2 = ($\displaystyle {\frac{{\lambda^{n}-\mu^{n}}}{{\lambda-\mu}}}$)2 - (- 1)n+$\scriptstyle \Delta$ . ($\displaystyle {\frac{{\lambda^{\Delta}-\mu^{\Delta}}}{{\lambda-\mu}}}$)2

= $\displaystyle {\frac{{(\lambda^{2n}-2(\lambda\mu)^{n}+\mu^{2n})-(-1)^{n+\Delta}...
...\lambda^{2\Delta}-2(\lambda\mu)^{\Delta}+\mu^{2\Delta})}}{{(\lambda-\mu)^{2}}}}$ = *

( Hinweis: $ \lambda$ . $ \mu$ = $ {\frac{{1+\sqrt{5}}}{{2}}}$ . $ {\frac{{1-\sqrt{5}}}{{2}}}$ = $ {\frac{{1^{2}-5}}{{2^{2}}}}$ = $ {\frac{{-4}}{{4}}}$ = - 1 )

* = $\displaystyle {\frac{{(\lambda^{2n}-2\cdot(-1)^{n}+\mu^{2n})-(-1)^{n+\Delta}(\lambda^{2\Delta}-2\cdot(-1)^{\Delta}+\mu^{2\Delta})}}{{(\lambda-\mu)^{2}}}}$

= $\displaystyle {\frac{{\lambda^{2n}+\mu^{2n}-2\cdot(-1)^{n}+2\cdot(-1)^{n+\Delta...
...\lambda}{\mu})^{\Delta}+(\frac{\mu}{\lambda})^{\Delta})}}{{(\lambda-\mu)^{2}}}}$

= $\displaystyle {\frac{{\lambda^{2n}+\mu^{2n}+2\cdot0-(-1)^{n+2\Delta}((\frac{\lambda}{\mu})^{\Delta}+(\frac{\mu}{\lambda})^{\Delta})}}{{(\lambda-\mu)^{2}}}}$ = $\displaystyle {\frac{{\lambda^{2n}+\mu^{2n}-(-1)^{n}((\frac{\lambda}{\mu})^{\Delta}+(\frac{\mu}{\lambda})^{\Delta})}}{{(\lambda-\mu)^{2}}}}$ = : h

und andererseits

Fn-$\scriptstyle \Delta$ . Fn+$\scriptstyle \Delta$ = $\displaystyle {\frac{{\lambda^{n-\Delta}-\mu^{n-\Delta}}}{{\lambda-\mu}}}$ . $\displaystyle {\frac{{\lambda^{n+\Delta}-\mu^{n+\Delta}}}{{\lambda-\mu}}}$ = $\displaystyle {\frac{{\lambda^{2n}-\lambda^{n-\Delta}\mu^{n+\Delta}-\lambda^{n+\Delta}\mu^{n-\Delta}+\mu^{2n}}}{{(\lambda-\mu)^{2}}}}$

= $\displaystyle {\frac{{\lambda^{2n}+\mu^{2n}-(\lambda\mu)^{n}((\frac{\mu}{\lambda})^{\Delta}+(\frac{\lambda}{\mu})^{\Delta})}}{{(\lambda-\mu)^{2}}}}$ = $\displaystyle {\frac{{\lambda^{2n}+\mu^{2n}-(-1)^{n}((\frac{\lambda}{\mu})^{\Delta}+(\frac{\mu}{\lambda})^{\Delta})}}{{(\lambda-\mu)^{2}}}}$ = h

Da beide Terme gleich sind, ist der erste Teil der Formel korrekt. Für den letzten Teil ergibt sich mit 3.6.8 und 3.6.9:

Fn+$\scriptstyle \Delta$ . Fn-$\scriptstyle \Delta$ = $\displaystyle {\frac{{F_{n}L_{\Delta}+F_{\Delta}L_{n}}}{{2}}}$ . $\displaystyle {\frac{{F_{n}L_{\Delta}-F_{\Delta}L_{n}}}{{2\cdot(-1)^{\Delta}}}}$ = $\displaystyle {\frac{{F_{n}^{2}L_{\Delta}^{2}-F_{\Delta}^{2}L_{n}^{2}}}{{4\cdot(-1)^{\Delta}}}}$

$ \square$

9.4 Fn-$\scriptstyle \Delta$ . Fn-1+$\scriptstyle \Delta$

Bevor wir die eigentliche Formel vorstellen und mit dem Induktionsbeweis beginnen, folgt zunächst ein kleiner Hilfssatz.

9.4.1 Lemma

Fn-1-$\scriptstyle \Delta$Fn+$\scriptstyle \Delta$ + Fn-$\scriptstyle \Delta$Fn-1+$\scriptstyle \Delta$ = 2FnFn-1 + (- 1)n+$\scriptstyle \Delta$F$\scriptstyle \Delta$2

Beweis

(i) aus ($ \lambda^{{n}}_{}$)2 = (Fn2 +2FnFn-1)$ \lambda$ + Fn2 + Fn-12 folgt F2n = Fn2 +2FnFn-1

(ii) aus $ \lambda^{{2n}}_{}$ = $ \lambda^{{n-\Delta}}_{}$ . $ \lambda^{{n+\Delta}}_{}$ folgt F2n = Fn-$\scriptstyle \Delta$Fn+$\scriptstyle \Delta$ + Fn-$\scriptstyle \Delta$Fn-1+$\scriptstyle \Delta$ + Fn-1-$\scriptstyle \Delta$Fn+$\scriptstyle \Delta$

Aus (i) und (ii) in Verbindung mit Formel 9.3 folgt

Fn2 +2FnFn-1 = Fn2 - (- 1)n+$\scriptstyle \Delta$F$\scriptstyle \Delta$2 + Fn-$\scriptstyle \Delta$Fn-1+$\scriptstyle \Delta$ + Fn-1-$\scriptstyle \Delta$Fn+$\scriptstyle \Delta$

und daraus folgt die obige Gleichung.

9.4.2 Formel und zugehöriger Induktionsbeweis

Nach dieser Vorarbeit kommen wir nun zu unserer Formel

FnFn-1 = Fn-$\scriptstyle \Delta$Fn-1+$\scriptstyle \Delta$ + (- 1)n+$\scriptstyle \Delta$F$\scriptstyle \Delta$F$\scriptstyle \Delta$-1

die wir per Induktion über $ \Delta$ beweisen wollen.

Der Induktionsanker $ \Delta$ = 0 ergibt FnFn-1 = FnFn-1 + (- 1)n . 0 und ist daher erfüllt. Sei nun die Behauptung für $ \Delta$ wahr. Zu zeigen bleibt die Korrektheit der Behauptung für $ \Delta$ + 1:

Fn-($\scriptstyle \Delta$+1)Fn-1+($\scriptstyle \Delta$+1) + (- 1)n+($\scriptstyle \Delta$+1)F$\scriptstyle \Delta$+1F($\scriptstyle \Delta$+1)-1    
= Fn-1-$\scriptstyle \Delta$Fn+$\scriptstyle \Delta$ + (- 1)n+$\scriptstyle \Delta$+1$\displaystyle \underbrace{{F_{\Delta+1}}}_{{F_{\Delta}+F_{\Delta-1}}}^{}\,$F$\scriptstyle \Delta$    
= Fn-1-$\scriptstyle \Delta$Fn+$\scriptstyle \Delta$ - $\displaystyle \underbrace{{(-1)^{n+\Delta}F_{\Delta-1}F_{\Delta}}}_{{F_{n}F_{n-1}-F_{n-\Delta}F_{n-1+\Delta}\textnormal{ nach Induktionsannahme}}}^{}\,$ - (- 1)n+$\scriptstyle \Delta$F$\scriptstyle \Delta$2    
= $\displaystyle \underbrace{{F_{n-1-\Delta}F_{n+\Delta}+F_{n-\Delta}F_{n-1+\Delta}}}_{{\textnormal{Lemma!}}}^{}\,$ - FnFn-1 - (- 1)n+$\scriptstyle \Delta$F$\scriptstyle \Delta$2    
= 2FnFn-1 + (- 1)n+$\scriptstyle \Delta$F$\scriptstyle \Delta$2 - FnFn-1 - (- 1)n+$\scriptstyle \Delta$F$\scriptstyle \Delta$2    
= FnFn-1    

q.e.d.

9.5 Nochmalige Betrachtung von Periodizität und Teilbarkeit

Erinnern wir uns einerseits noch einmal an die Binetsche Formel Fn = $ {\frac{{\lambda^{n}-\mu^{n}}}{{\lambda-\mu}}}$ aus Abschnitt 6. Dabei wurde $ \lambda$ : = $ {\frac{{1+\sqrt{5}}}{{2}}}$ und $ \mu$ : = $ {\frac{{1-\sqrt{5}}}{{2}}}$ gesetzt. Erinnern wir uns andererseits daran, daß es für Periodizitätsbetrachtungen häufig sinnvoll ist, in Restklassen zu rechnen. - Nun können wir die berechtigte Frage stellen: Ist es möglich, die geschlossene Form innerhalb einer Restklassenbetrachtung zu verwenden?

Diese Frage führt uns unmittelbar zu dem Problem, ob der Ausdruck $ \sqrt{{5}}$ in den Restklassen, die wir betrachten wollen, auf sinnvolle Weise definiert werden kann.

Für die nachfolgende Betrachtung benötigen wir Wissen aus der Zahlentheorie, das z.B. bei [FrIs92] nachgeschlagen werden kann. Zum einen benötigen wir den sogenannten kleinen Fermatschen Satz, der für Primzahlen p und teilerfremde Basen a die Folgerung ap-1 $ \equiv$ 1 ( mod p) aufstellt. Zum anderen benötigen wir einige zentrale Eigenschaften über quadratische Reste.

9.5.1 Die Fälle ($ {\frac{{5}}{{p}}}$) = 1

Betrachten wir Primzahlen p > 5 und die Primkörper $ \mathbb {F}$p, d.h. die Körper, die bei den Restklassenbetrachtungen modulo Primzahlen p entstehen. Die unter Abschnitt 6 hergeleitete geschlossene Form bleibt in solchen Primkörpern gültig, wenn 5 ein quadratischer Rest modulo p ist, mit Hilfe des Legendresymbols ausgedrückt also ($ {\frac{{5}}{{p}}}$) = 1 gilt; nur dann ist Kongruenz x2 $ \equiv$ 5 ( mod p) in $ \mathbb {\mathbb{F}}$p erfüllbar und wir können für unsere Betrachtung z.B. $ \sqrt{{5}}$ als die »größere« und - $ \sqrt{{5}}$ als die »kleinere« Lösung dieser Kongruenz definieren.

Für Primzahlen p mit ($ {\frac{{5}}{{p}}}$) = 1 gilt somit aufgrund des kleinen Fermatschen Satzes

Fp-1 = $\displaystyle {\frac{{\lambda^{p-1}-\mu^{p-1}}}{{\lambda-\mu}}}$ $\displaystyle \equiv$ $\displaystyle {\frac{{1-1}}{{\sqrt{5}}}}$ $\displaystyle \equiv$ 0 ( mod p)

sowie

Fp = $\displaystyle {\frac{{\lambda^{p}-\mu^{p}}}{{\lambda-\mu}}}$ $\displaystyle \equiv$ $\displaystyle {\frac{{\lambda-\mu}}{{\lambda-\mu}}}$ $\displaystyle \equiv$ $\displaystyle {\frac{{\sqrt{5}}}{{\sqrt{5}}}}$ $\displaystyle \equiv$ 1 ( mod p)

Damit gilt (Fp-1, Fp) $ \equiv$ (0, 1) $ \equiv$ (F0, F1), mithin gilt die Periodizität Fk . (p-1)+$\scriptstyle \Delta$ $ \equiv$ F$\scriptstyle \Delta$ ( mod p) für Primzahlen der obengenannten Form.

Insbesondere sind für diese Primzahlen die Fibonacciwerte Fp-1 sowie die Terme Fp-2 - 1, Fp - 1 und Fp+1 - 1 durch p teilbar.

Wegen des quadratischen Reziprozitätsgesetzes gilt für ungerade p

($\displaystyle {\frac{{p}}{{5}}}$) = ($\displaystyle {\frac{{5}}{{p}}}$) . (- 1)$\scriptstyle {\frac{{5-1}}{{2}}}$ . $\scriptstyle {\frac{{p-1}}{{2}}}$ = ($\displaystyle {\frac{{5}}{{p}}}$) . 1 = ($\displaystyle {\frac{{5}}{{p}}}$)

Anstatt alle Fälle für ($ {\frac{{5}}{{p}}}$) = 1 zu untersuchen, können wir uns also auf die Fälle ($ {\frac{{p}}{{5}}}$) = 1 beschränken. Eine Restklassenbetrachtung auf $ \mathbb {F}$5 (vgl. Tabelle 9) zeigt uns, daß nur Zahlen der Form 5n, 5n + 1 und 5n + 4 (bzw. 5n - 1) quadratische Reste modulo 5 sind. Da Primzahlen größer als 5 weder durch 5 noch durch 2 teilbar sind, können wir folgern: Primzahlen mit der Eigenschaft ($ {\frac{{5}}{{p}}}$) = 1 und p > 5 haben die Form p = 10 . n±1. (Diese Form enthält diejenigen quadratischen Reste modulo 10, die zu 10 teilerfremd sind.)


Table 9: Quadratische Reste modulo 5 bzw. 10

Table 9: Quadratische Reste modulo 5 bzw. 10
x 0 1 2 3 4
x2 mod 5 0 1 4 4 1

Table 9: Quadratische Reste modulo 5 bzw. 10
x 0 1 2 3 4 5 6 7 8 9
x2 mod 10 0 1 4 9 6 5 6 9 4 1


9.5.1.1 Zusammenfassung dieser Ergebnisse

Für Primzahlen der Form p = 10 . n±1 sind die Terme Fp-2 - 1, Fp-1, Fp - 1 und Fp+1 - 1 durch p ohne Rest teilbar.

9.5.1.1.1 Beispiel: F909 -1 $ \equiv$ F910 $ \equiv$ F911 -1 $ \equiv$ F912 -1 $ \equiv$ 0 ( mod 911)

9.5.2 Die Fälle ($ {\frac{{5}}{{p}}}$) = - 1

Die nicht-quadratischen Reste modulo 10, die zu 10 teilerfremd sind, haben die Form 10 . n±3. Für Primzahlen dieser Form gilt: Die Periode Pp (für Fk . Pp+$\scriptstyle \Delta$ $ \equiv$ F$\scriptstyle \Delta$ ( mod p)) ist ein Vielfaches von p + 1 und es gilt Fp+1 $ \equiv$ 0 ( mod p).

9.5.2.1 Beweis:

Ich habe leider keinen Beweis gefunden, der ohne fortgeschrittene Konzepte aus der Zahlentheorie auskommt. Für die erforderlichen zahlentheoretischen Grundlagen sei daher auf [HaRi94], Appendix 4 (The Arithmetic of Quadratic Fields) verwiesen, ohne die der nachfolgende Beweis unverständlich sein dürfte.

Wir betrachten den Körper $ \mathbb {Q}$($ \sqrt{{5}}$) und setzen a : = 2 . $ \lambda$ = 1 + $ \sqrt{{5}}$, dann gilt $ \bar{{a}}$ = 1 - $ \sqrt{{5}}$ = 2 . $ \mu$. Wegen a2 -2a - 4 = (12 +2 . $ \sqrt{{5}}$ +5) - (2 + 2 . $ \sqrt{{5}}$) - 4 = 6 - 2 - 4 = 0 sind sowohl a als auch $ \bar{{a}}$ Elemente dieses Körpers.

Mit der Erweiterung des kleinen Fermatschen Satzes auf solche Körper gilt ap $ \equiv$ $ \bar{{a}}$ ( mod p) für ($ {\frac{{5}}{{p}}}$) = - 1. Somit folgt

Fp+1 = $\displaystyle {\frac{{\lambda^{p+1}-\mu^{p+1}}}{{\lambda-\mu}}}$ = $\displaystyle {\frac{{(a^{p+1}-\bar{a}^{p+1})\cdot2^{-p-1}}}{{(a-\bar{a})\cdot2^{-1}}}}$ = $\displaystyle {\frac{{a\cdot a^{p}-\bar{a}\cdot\bar{a}^{p}}}{{a-\bar{a}}}}$ . 2-p

$\displaystyle \equiv$ $\displaystyle {\frac{{a\bar{a}-\bar{a}a}}{{a-\bar{a}}}}$ . 2-1 = $\displaystyle {\frac{{a\bar{a}-a\bar{a}}}{{(a-\bar{a})\cdot2}}}$ = $\displaystyle {\frac{{0}}{{(a-\bar{a})\cdot2}}}$ = 0 ( mod p)

$ \square$

Thorsten Reinecke 2004-07-11