2 Zahlentheoretische Eigenschaften der Fibonacci-Zahlen

Bei einer Folge von natürlichen Zaheln interessiert man sich natürlich für die Primzahlzerlegungen. Also z.B.: Gibt es unter den Fibonacci-Zahlen unendlich viele Primzahlen? Kann man etwas über die Anzahl der Primteiler aussagen. Befinden sich Quadratzahlen, andere Potenzen etc. darunter?

2.1 Der ggT von Fibonacci-Zahlen

Ab jetzt bezeichne ggT(a,b) den größten gemeinsamen Teiler der Zahlen a und b, und kgV(a,b) ihren kleinsten gemeinsamen Vielfach. a|b bedeute, daß a ein Teiler von b ist ("a teilt b"). (Achtung: Der Vertikale Strich ist in der Browser-Darstellung häufig schlecht zu erkennen.)

Wie sieht ggT(Fn, Fm) aus? Die Antwort ist überraschend einfach:

2.1.1 Satz:
Für m,n in IN ist:

ggT(Fn, Fm)=FggT(m,n).

Beweis:

Zunächst zeigen, wir, daß Fn|Fkn (für k>0). Und zwar geht dies einfach durch Induktion über k. k=1 ist klar. Und nach der Additionsformel 1.2.4. ist

F(k+1)n=Fkn-1Fn+FknFn+1.

Nach Induktionsvorraussetzung ist dann Fn ein Teiler von Fkn.

Nun sei an den euklidischen Algorithmus erinnert. Den ggT(m,n) bekommt man wie folgt: Ist (oBdA) m>=n, so schreibt man

m = q0n +r1 mit r1<n
n = q1r1 +r2 mit r2<r1
r1 = q2r2 +r3 mit r3<r2
  ...     
rk-1= qkrk  

rk ist dann der ggT von m und n. Genauer gesagt ist

ggT(m,n)=ggT(n,r1)=ggT(r1,r2)= ggT(r2,r3)=...

Wendet man den euklidischen Algorithmus auf Fn und Fn-1 an, so ist stets qi=1 und die ri durchlaufen die Fibonacci-Zahlen nach unten: Fn und Fn-1 sind teilerfremd. Insbesondere sind dann auch Fn und Fkn-1 teilerfremd.

Sind nun ri und qiwie oben, so ist:

...

Auf diese Weise macht man weiter:

ggT(Fm,Fn)= ggT(Fn,Fr_1)= ggT(Fr_1,Fr_2)=...

Am Ende erhält man: ggT(Fm,Fn)=Fr_k= FggT(m,n).

Wir halten außerdem fest:

2.1.2 Korollar:
Es gilt:
(1)
n|m   =>   Fn|Fm.
(2)
Fn und Fn-1 sind teilerfremd.

Die Umkehrung von (1) gilt nicht, da F2=1 ist. So ist F2 ein Teiler von F3, obwohl 2 kein Teiler von 3 ist. Abgesehen von diesem Unfall mit der 2 gilt aber auch die Umkehrung.

2.1.3 Korollar:
(1)
Fn ist gerade   =>    3|n
(2)
3|Fn   =>   4|n
(3)
4|Fn   =>   6|n
(4)
5|Fn   =>   5|n
(5)
7|Fn   =>   8|n
2.1.4 Korollar:
Ist Fn eine Primzahl, so ist n=4, oder n ist selber eine Primzahl.

Die Umkehrung gilt nicht: 19 ist eine Primzahl, aber F19=4181=37·113 ist keine. Die Frage, ob unter den Fibonacci-Zahlen endlich oder unendlich viele Primzahlen sind, ist ungelöst.

2.1.5 Korollar:
Ist ggT(m,n)=1, so gilt:    Fn·Fm|Fmn.

2.2 Die Fibonacci-Folge modulo n

Die Periode der Fibonacci-Folge modulo n

Gibt es zu jeder Zahl n eine Fibonacci-Zahl Fk mit n|Fk? Die Antwort ist "Ja!". Um dies zu sehen, betrachten wir die Folge Fk mod n. Die Frage ist also, ob es außer k=0 noch ein anderes k mit Fk=0 mod n gibt.

2.2.6 Satz und Definition:

Die Fibonacci-Folge modulo n (Fk mod n) ist periodisch. Die Periode ist <=n2.

Ab jetzt bezeichne $\lambda(n)$ die Periode der Fibonacci-Folge modulo n. $\lambda(n)$ heißt auch manchmal "Wall-Zahl" (nach D.D. Wall; s. [Wall]).

Beweis:

Zunächst beachte man, daß die Fibonacci-Folge durch jedes Paar (Fn,Fn+1) eindeutig festgelegt ist. Nun gibt es aber nur n2 Möglichkeiten für (Fn,Fn+1) Daraus folgt die Behauptung.

Wegen F0=0 mod n gibt es unendlich viele k mit Fk=0 mod n.

Die Perioden kann man auch so sehen: Man betrachtet die Matrizen $\pmatrix{1 & 1\cr 1 & 0}$ in Z/nZ. Da die ersten beiden Vektoren (1,0) und (0,1) linear unabhängig sind, ist $\lambda(n)$ genau die kleinste Zahl >1, für die gilt:

\pmatrix{1 & 1\cr 1 & 0}^{\lambda(n)}=
\pmatrix{1 & 0 \cr 0 & 1}.

Was kann man über die Perioden $\lambda(n)$ sonst noch aussagen? In diesem Kapitel werden wir uns mit den Perioden beschäftigen, für den Fall, daß n eine zusammengesetzte Zahl ist.

2.2.7 Lemma:
Es seien m,n>1, dann gilt:

m|n   =>    $\lambda(m)$|$\lambda(n)$.

Beweis:
Folgt sofort aus der Definition des $\lambda(n)$ mit den Matrizen.
2.2.8 Lemma:
Sind m und n teilerfremd, so gilt:

$\lambda(mn)$    =     kgV($\lambda(m)$,$\lambda(n)$).

Beweis:

Nach obigem Lemma 2.2.7. gilt kgV($\lambda(m)$,$\lambda(n)$)|$\lambda(mn)$

Umgekehrt ist $F_{{\rm kgV}(\lambda(m),\lambda(n))}$=0 mod m und auch mod n. Und ebenso $F_{{\rmkgV}(\lambda(m),\lambda(n))+1}$=1 mod m und auch mod n. Nach dem chinesischen Restsatz (Referenz?) gibt es aber, da m und n teilerfremd sind, in Z/nmZ nur genau eine Restklasse [x]=0 mod m und mod n, und genau eine =1 m und mod n. $F_{{\rm kgV}(\lambda(m),\lambda(n))}$ und $F_{{\rm kgV}(\lambda(m),\lambda(n))+1}$ müssen diese beiden Restklassen sein. Es gilt also sogar:

$F_{{\rm kgV}(\lambda(m),\lambda(n))}$=0 mod mn    und     $F_{{\rm kgV}(\lambda(m),\lambda(n))+1}$=1 mod mn

Dies bedeutet: $\lambda(mn)$|kgV($\lambda(m)$,$\lambda(n)$).

2.2.9 Lemma:
p sei eine Primzahl, und k>1, dann gilt entweder

\lambda(p^k)=\lambda(p^{k-1})   oder   \lambda(p^k)=p\lambda(p^{k-1}).

Beweis:

Wir rechnen hier, ohne es dazuzuschreiben, modulo pk. Nach Definition ist

\pmatrix{1 & 1 \cr 1 & 0}^{\lambda(p^{k-1})}\pmatrix{1\cr 0}=
p^{k-1}\pmatrix{a\cr b}+\pmatrix{1\cr 0}

mit a,b in {0,1,...,p-1}. Ist a=b=0, so ist $\lambda(p^k)=\lambda{p^{k-1}}$ und wir sind fertig. Ansonsten zeigt man durch wiederholtes Multiplizieren mit $\pmatrix{1 & 1\cr 1 & 0}^{\lambda{p^{k-1}}}$ für l in IN:

\pmatrix{1 & 1 \cr 1 & 0}^{l\lambda(p^{k-1})}\pmatrix{1\cr 0}=
lp^{k-1}\pmatrix{a\cr b}+\pmatrix{1\cr 0}.

Die Frage ist nun, für welches l der erste Summand zum ersten mal verschwindet. Wenn nicht a=b=0 ist, so ist dies, da p eine Primzahl ist, zum ersten genau mal für l=p der Fall.

Eine etwas genauere Analyse zeigt, daß gilt:

\lambda(p^k)=p\lambda(p^{k-1}) =>
\forall l \ge k: \lambda(p^l)=p\lambda(p^{l-1}).

Außerdem ist klar, daß es mindestens ein k gibt, für das dies gilt. Man vermutet, daß dies für alle k in IN gilt:

\lambda(p^k)=p^{k-1}\lambda(p).

Dies ist allerdings bis heute nicht bewiesen.

Mit Hilfe dieser drei Lemmas können wir, wenn wir mal von der eben angesprochenen ungelösten Frage absehen, $\lambda(n)$ in Termen der lambda der Primfaktoren von n ausrechnen. Im nächsten Abschnitt werden wir uns der ungleich schwierigeren Frage zuwenden, wie die Perioden $\lambda(p)$ für Primzahlen p aussehen.

Die Periode der Fibonacci-Folge modulo p

Bevor wir anfangen, ein Lemma:

2.2.10 Lemma:
Ist p eine Primzahl, so gilt:

5^{\frac{p-1}{2}}=\cases{+1 mod p & falls $p=\pm 1 ,mod 5$,\cr
-1 mod p & falls $p=\pm 2 mod 5$.}

Beweis:

Man sehe in einem Buch für Zahlentheorie (Referenz?) nach, wie man mit den Legendre-Symbolen $\left(\frac{p}{q}\right)$ rechnet. Und zwar gilt:

\left(\frac{p}{q}\right)\cdot\left(\frac{q}{p}\right)=
(-1)^{\frac{p-1}{2}\frac{q-1}{2}}.

Für q=5 ergibt sich letztendlich:

\left(\frac{5}{p}\right)}={\left(\...
...$p=\pm 1{\rm\,mod\,}5$,\cr -1 & falls $p=\pm 2{\rm\,mod\,}5$.}

Denn ±1 sind quadratische Reste modulo 5 und ±2 sind keine quadratischen Reste. Außerdem beachte man 5p-1=1 mod p (kleiner Satz von Fermat).

2.2.11 Satz:

p sei eine Primzahl. Dann kann man die Werte von Fp-1, Fp, Fp+1 in folgender Tabelle ablesen.

  Fp-1 mod p Fp mod p Fp+1 mod p
p=2 1 1 0
p=5 3 0 3
p=±1 mod 5 0 1 1
p=±2 mod 5 1 -1 0
Beweis:

Der Beweis erfolgt durch nachrechnen: Man multipliziere die Formel von Binet (1.3.9.) für n=p und n=p+1 mit Hilfe des Binomialgesetzes aus. Alle Terme mit sqrt(5) müssen sich gegenseitig wegheben.

Da p eine Primzahl ist, sind fast alle Binomialkoeffizienten, wenn man modulo p rechnet, Null. Man bekommt auf diese Weise Ausdrücke mit $5^{\frac{p-1}{2}}$. Fp-1 kann man dann aus Fp und Fp+1 ausrechnen.

Als Korollar erhalten wir:

2.2.12 Satz:
Es sei p verschieden von 2 und 5, dann gilt:
p=±1 mod 5 => \lambda(p)|(p-1)
p=±2 mod 5 => \lambda(p)|2(p+1)

Im zweiten Fall kann \lambda(p) nicht schon ein Teiler von p+1 sein.

Außerdem ist \lambda(2)=3 und \lambda(5)=20.

Beweis:
Kann man sofort aus der Tabelle in 2.2.11. ablesen. Für p=5 muß man das halt nachrechnen.

Weitere Resultate zu bekommen, ist ziemlich schwierig. In [Götsch] wird gezeigt:

2.2.13 Satz:
Es gilt:

zwei komplizierte Formeln

Außerdem gilt:

noch eine komplizierte Formel

Die Verteilung der Fibonacci-Zahlen modulo n

Tauchen in der Fibonacci-Folge Fk mod n alle Zahlen 0,...,n-1 gleichoft auf? In diesem Abschnitt werden wir die Frage beantworten. Die Frage läßt sich auch ganz allgemein für Folgen definieren:

2.2.14 Definition:

(ak)k in IN sei eine Folge ganzer Zahlen, n in IN und AN(j) sei die Anzahl der Folgenglieder ak mit k<=N und ak=j mod n.

Dann heißt die Folge (ak) "uniform verteilt modulo n", falls für alle j=0,...,n-1 gilt:

lim_{N\to\infty}\frac{A_N(j)}{N}=\frac{1}{n}.

Im Falle der Fibonacci-Zahlen ist dies relativ einfach nachzuprüfen, da sie periodisch modulo n sind. Sie sind uniform verteilt, falls innerhalb einer Periode alle Zahlen 0,...,n-1 gleichoft vorkommen.

2.2.15 Satz:

Die Fibonacci-Zahlen sind genau dann uniform verteilt modulo n, falls n eine 5er-Potenz ist: n=5k.

Beweis:

Wir zeigen nur die eine Richtung.

n enthalte einen Primfaktor p verschieden von 5, und wir nehmen an, Fn ist uniform verteilt modulo n. j sei die Anzahl der durch p teilbaren Fibonacci-Zahlen mit Index y<$\lambda(p)$. Wegen $\lambda(p)$|$\lambda(n)$ ist die Anzahl der durch p teilbaren Fibonacci-Zahlen mit Index y$\lambda(n)$ dann genau

k\frac{\lambda(n)}{\lambda(p)}=\frac{\lambda(n)}{p}.

Also: kp=$\lambda(p)$. Wir wissen aber (Satz 2.2.12.), daß das für p verschieden von 5 nicht sein kann.

Für den Beweis, daß Fn uniform verteilt modulo 5k ist, s. [Kuipers] und [Niederreiter].

Summen von Fibonacci-Zahlen modulo n

In diesem Abschnitt werden wir die Summen von Fibonacci-Zahlen modulo n ausrechnen, wobei die Summe genau über eine Periode genommen wird. Zwar können wir solche Summen sogar in Z ausrechnen (s. 1.2.5., 1.2.6. und 1.3.11.), aber hier wird alles noch einfacher, weil wir eine Translationsinvarianz haben:

\sum_{k=0}^{\lambda(n)-1}F_k=
\sum_{k=N}^{N+\lambda(n)-1}F_k\quad({\rm\,mod\,}n).

Die Ergebnisse sind wie folgt:

2.2.16 Satz:

Es sei n in IN. Werden die folgenden Summen genau über eine Periode und modulo n ausgerechnet, so gilt:

viele komische Summenformeln

In den Fällen (d), (g), (l) sei dabei n eine Primzahl verschieden von 5, im Fall (h) eine Primzahl verschieden von 3, im Fall (i) und (j) eine Primzahl verschieden von 11. Für welche Zahlen (k) (und damit (l)) gilt, ist nicht nicht klar.

Beweis:
Wir zeigen nicht alles.

(a) ist einfach: $\sum F_k=\sum(F_{k-1}+F_{k-2})=2\sum
F_k$.

Für (b) beobachte, daß Fk mit Hilfe seiner Rekursionsformel auch für k<0 definiert ist, und (modulo n) auch dort periodisch ist. Und zwar sieht man schnell, daß F-k=Fk(-1)k+1. Daraus folgt (b).

Für (c) rechnen wir:

\sum F_k^2=\sum (F_{k-1}+F_{k-2})^2=2\sum F_k^2+2\sum F_kF_{k-1},

und ebenso

\sum F_k^2=\sum F_{k-2}^2=
\sum (F_k-F_{k-1})^2=2\sum F_k^2-2\sum F_kF_{k-1}.

Addition ergibt die Behauptung.

(e) beweist man so ähnlich, nur ein wenig komplizierter, wie (c). Und (f) folgt aus (e) genau wie (b) aus (a).

Für (d), (g) und (l) s. [Aydin1]. (h), (i), (j) und (k) gehen so ähnlich wie (e) und (c) nur sehr viel komplizierter; s. [Aydin2].

2.3 Primitive Teiler

Wir haben schon gesehen, daß es zu jeder Zahl n eine Fibonacci-Zahl gibt, die durch n teilbar ist, nämlich $F_{\lambda(n)}$. Es wird aber im Allgemeinen durchaus schon eine kleinere Fibonacci-Zahl durch n teilbar sein.

2.3.17 Definition:
n heißt "primitiver Teiler" von Fk, falls gilt:
(a)
n|Fk
(b)
Für j<k gilt: n teilt nicht Fj.

Ist p eine Primzahl und ein primitiver Teiler von Fk, so heißt sie "primitiver Primteiler". Die höchste Potenz von p, die Fk in diesem Fall teilt, heißt "primitive Primteilerpotenz" ("ppp") pe.

Außerdem definieren wir gleich das Produkt aller solchen primitiven Primteilerpotenzen:

P(F_k):=\prod\limits_{p^e\mbox{ \scriptsize ppp}}p^e.

Hat Fk keine primitiven Primteiler, so sei P(Fk):=1.

Man beachte, daß, wenn pe ein primitiver Teiler Fk ist, pe noch lange keine primitive Primteilerpotenz sein muß, denn p muß kein primitiver Primteiler sein.

Natürlich hat jede Fibonacci-Zahl mindestens einen primitiven Teiler, nämlich sich selbst. Aber hat jede Fibonacci-Zahl einen primitiven Primteiler? Die Antwort ist natürlich "Nein", denn F6=8, aber bereits F3=2 ist durch 2 teilbar.

Es stellt sich aber heraus, daß alle Fibonacci-Zahlen bis auf endlich viele primitive Primteiler haben. Und zwar gilt:

2.3.18 Satz:

\sum\limits_{k\le x}\ln P(F_k)=
\frac{3}{\pi^2}\ln({\textstyle\frac{1+\sqrt{5}}{2}})\cdot x^2+O(x\ln x).

Beweis:
Der Beweis ist, wie der Leser sich denken kann, nicht elementar. Er findet sich in [Kiss], und benutzt diverse zahlentheoretische Funktionen wie z.B. die Möbius-Funktion.

Sonderlich überraschend ist dies allerdings nicht, da die Fibonacci-Zahlen ja viel schneller wachsen, als die Primzahlen. Überraschend ist eher, daß man so etwas beweisen kann.

2.3.19 Korollar:
Es gibt ein N in IN, so daß für alle k>=N die Fibonacci-Zahl Fk primitive Primteiler hat.

Die rechte Seite obiger Formel hat folgende Bedeutung: Ist wieder $\zeta=\frac{1+\sqrt{5}}{2}$ und $\eta=\frac{1-\sqrt{5}}{2}$, so ist nach der Formel von Binet 1.3.9.:

\ln\prod_{k=1}^x F_k\sim\ln\prod_{k=1}^x\zeta^k
\sim\frac{x^2}{2}\ln\frac{1+\sqrt{5}}{2}.

Aus diesem Grund ist folgende Formel stark verwandt mit obiger (man kann glaube ich zeigen, daß sie sogar daraus folgt):

2.3.20 Satz:

\lim_{x\to\infty}
   \frac{\ln(F_1\cdot\ldots\cdot F_x)}{\ln{\rm kgV}(F_1,\ldots, F_x)}
= \frac{\pi^2}{6}.

Beweis:
s. [Matiyasevich].

2.4 Fibonomial-Koeffizienten

Definition

2.4.21 Definition:
Ist (an) (n in IN) eine Folge reeller Zahlen verschieden von 0, so definieren wir

[n]!_{(a_n)}:=a_1\cdot a_2\cdot\ldots\cdot a_n  und 
...ray}\right]_{(a_n)}:=\frac{[n]!_{a_n}}{[k]!_{a_n}[n-k]!_{a_n}}.

Ist klar, welche Folge (an) gemeint ist, so lassen wir den Index weg. Insbesondere ergeben sich für an=n die (normalen) Binomial-Koeffizienten. Für an=Fn ergeben sich die "Fibonomial-Koeffizienten". Im folgenden betrachten wir nur diese.

Auf analoge Weise kann man auch verallgemeinerte Multinomial-Koeffizienten definieren.

Die Fibonomial-Koeffizienten sind bisher lediglich rationale Zahlen. Wir wollen natürlich als erstes wissen, ob sie auch ganz sind. Leider kann man das nicht so einfach zeigen, wie bei den Binomial-Koeffizienten, denn deren Rekursionsformel wird hier zu:

Formeln wie bei Binomialkoeffizienten, aber mit Faktor
\frac{F_n}{F_k+F_{n-k}}

Und der Bruch Fn/(Fk+Fn-k) ist nicht immer ganzzahlig. Trotzdem gilt:

2.4.22 Proposition:
Die Fibonomial-Koeffizienten sind positive ganze Zahlen.
Beweis:

Und zwar folgt dies alleine z.B. aus der Eigenschaft FggT(m,n)=ggT(Fm,Fn) (s. [Ward]).

Es sei p eine Primzahl. Welche Potenz von p ist noch ein Teiler von [n]!? Ist s gegeben und $\rho_s$ die kleinste Zahl, für die $p^s\vert F_{\rho_s}$, so sind alle Fibonacci-Zahlen, die durch ps geteilt werden können von der Form $F_{k\rho_s}$. Daraus folgt (nach einigem Nachdenken), daß die höchste Potenz von p, die noch ein Teiler von [n]! ist, gegeben ist durch

\sum_{s=1}^\infty[\frac{n}{\rho_s}]  wobei [.] die Gaußklammer ist.}

Die Summe ist dabei in Wirklichkeit endlich. Da für beliebige natürliche Zahlen n,m, rho gilt:

[\frac{n+m}{\rho}]\ge[\frac{n}{\rho}]+[\frac{m}{\rho}],

folgt:

\sum_{s=1}^\infty[\frac{n}{\rho_s}]\ge
\sum_{s=1}^\infty[\frac{n-k}{\rho_s}]+
\sum_{s=1}^\infty[\frac{k}{\rho_s}].

Im Zähler ist also eine mindestens so große Potenz von p enthalten wie im Nenner. Der Koeffizient ist ganz.

Stern-Konfigurationen mit ggT-Eigenschaft

Die Fibonomial-Koeffizienten kann man genau wie die Binomial-Koeffizienten in einer Art Pascalschem Dreieck anordnen. Wir betrachten zunächst sieben Fibonomial-Koeffizienten (oder Binomial-Koeffizienten) A,A1,A2,...,A6, die im Dreieck wie folgt angeordnet sind:

A_6 A_5 oben, A_1 A A_4 darunter, A_2 A_3 darunter.

Diese Anordnung heißt "Hoggatt-Hansell-Hexagon" (engl. "Hoggatt-Hansell Perfect Square Hexagon") nach den beiden Mathematikern, die sie zuerst untersucht haben ([Hoggat2]).

Man sieht, indem man alle Produkte hinschreibt und wegkürzt, leicht daß:

2.4.23 Fakt:

A1A3A5= A2A4A6

Aber das ist nicht alles.

2.4.24 Proposition:
Es gilt:

ggT(A1,A3,A5)= ggT(A2,A4,A6).

Beweis:
s. [Hillman].

Wegen der Auswahl der je drei Punkte heißt dieser Satz auch manchmal "Davids-Stern-Theorem". Die entsprechende Gleichung für den kgV gilt dagegen nicht. Ersetzt man allerdings

Der Fibonomial-K. [n k] bekommt einen Faktor F_{n+1} davor, der
Binomial-K (n k) einen Faktor (n+1)

so gilt die entsprechende Identität mit dem kgV, allerdings nicht mehr mit dem ggT. Die Produktidentität (2.4.23.) gilt ebenfalls noch. (Für einen Bew. s. [Ando1] oder [Sato].)

Man kann sich nun fragen, ob es noch andere Anordnungen gibt, die solche Eigenschaften haben. Die Antwort ist natürlich "Ja!", denn wegen solchen Formeln wie ggT(ggT(a,b),ggT(c,d))=ggT(a,b,c,d) kann man aus kleineren Anordnungen größere zusammenbasteln.

eine Stern-Anordnung

Diese Konfiguration nennt sich "Tokyo-Bogen". Sie besteht aus drei annähernd gestutzt kegelförmigen Anordnungen, die durch Drehungen ineinander übergehen. Diese Unterstrukturen heißen "Fujiyama", da sie an den gleichnamigen Berg in der Nähe von Tokyo erinnern sollen.

Es gilt:

2.4.25 Proposition:

$\{\bullet\}$, $\{\circ\}$ und $\{\cdot\}$ bezeichnen die dem Tokyo-Bogen entsprechenden Zahlen im Pascalschen Dreieck aus Fibonomial-Koeffizienten (oder normalen Binomial-Koeffizienten). Dann gilt:

diverse ggT und kgV-Formeln

Beweis:
s. [Ando2].

Dort gibt es noch eine weitere (größere) Konfiguration namens "Julias Schneeflocke", und außerdem einen "Nordstern". Eine weitere Formation, ein größeres Hexagon, findet sich in [Long1].

2.5 Fibonacci-Zahlen als Quadrat- und Kubikzahlen

Gibt es unter den Fibonacci-Zahlen unendlich viele Quadratzahlen? Kubikzahlen? Solchen Fragen lassen sich beliebig abwandeln: Welche Fibonacci-Zahlen haben die Form px2±1, wo p eine Primzahl ist? Wieviele darunter haben einen geraden Index? Ich erwähne hier nur die zwei einfachsten Ergebnisse:

2.5.26 Satz:

Abgesehen von F0=0 und F1=F2=1 ist F12=144 die einzige Quadratzahl unter den Fibonacci-Zahlen. Weitere Kubikzahlen gibt es nicht.

Beweis:
Für die Quadratzahlen s. [Cohn], für die Kubikzahlen [Lagarias].

Einen Überblick über ähnliche Ergebnisse gibt [Robbins]. In [Luo] wird gezeigt, daß die einzigen Fibonacci-Zahlen, die Dreieckeszahlen, d.h. solche von der Form n(n+1)/2 sind, F1=F2=1 F8=21 und F10=55 sind.

2.6 Die Fibonacci-Zahlen als diophantische Menge

In der Theorie der diophantischen Gleichungen beschäftigt man sich mit der Frage, ob eine Gleichung der Form P(x1,...,xn)=0, wo P ein Polynom mit ganzzahligen Koeffizienten ist, Lösungen in den ganzen (oder natürlichen) Zahlen hat. Berühmtestes Beispiel ist sicherlich der Große Satz von Fermat. Die Frage nach der Lösbarkeit ist im allgemeinen sehr schwer zu beantworten.

Umgekehrt kann man sich auch fragen, ob es zu einer vorgegebenen Teilmenge A von IN ein Polynom P gibt, so daß die Elemente aus A genau die (ganzen oder natürlichen) Nullstellen von P sind. Etwas präziser definieren wir:

2.6.27 Definition:

Eine Teilmenge A von IN heißt "diophantisch", falls ein Polynom P in k+n Variablen mit ganzzahligen Koeffizienten existiert, so daß

fuer (a_1,...,a_k)\in A^k existieren (x_1,...,x_n) in N^n mit
P(a_1,...,a_k,x_1,...,x_n)=0.

Interessant ist diese Eigenschaft natürlich nur für unendliche Mengen A.

2.6.28 Beispiel:

Die Menge der durch p teilbaren Zahlen ist diophantisch, sie ist nämlich genau gegeben durch

\{a\in{I\!\!N}\mid \exists x\in{I\!\!N}: a-px=0\}.

Wir werden in diesem Abschnitt die Frage behandeln, ob die Menge F der Fibonacci-Zahlen und ihr Komplement IN-F diophantisch sind. Und zwar betrachten wir das "Lucas-Polynom"

L(x,y) = x2-xy-y2.

Nun gilt die dazu sehr ähnliche Identität Fn+12-Fn-1Fn- Fn2=(-1)n. In [Jones1] wird gezeigt:

L(x,y)=1  <=>  y=F2n und x=F2n+1
L(x,y)=-1  <=>  y=F2n-1 und x=F2n

Also:

x\in F\quad\Leftrightarrow\exists y\in{I\!\!N}:\,L(y,x)\in\{\pm 1\}.

Damit haben wir schon einmal das Polynom für die Fibonacci-Zahlen. Jede Nicht-Fibonacci-Zahl liegt zwischen zwei Fibonacci-Zahlen:

z\not\in F\Leftrightarrow\exists x,y\in{I\!\!N}:\,
L(y,x)\in\{\pm 1\}\mbox{ und }(x-z)(z-y)>0.

Wir bekommen:

2.6.29 Proposition:
Die Mengen F und IN-F sind diophantisch. Und zwar gilt:

Hier werden zwei Polynome angegen.

nach [Jones2].

by Michael Becker, 5/2003. Letzte Änderung: 5/2003.