Subsections


5 Teilbarkeiten


5.1 Fk . n und Primzahlen

Das folgende Resultat ist zwar nicht ganz befriedigend, weil keine allgemeingültige Formel zur Berechnung von Fk . n hergeleitet wird; trotzdem verblüfft es durch seine Einfachheit.

Zunächst halten wir fest, daß F1 . n = Fn $ \equiv$ 0  ( modFn) immer erfüllt ist. Nun zeigen wir per Induktion über k, daß Fkn $ \equiv$ 0  ( modFn) gilt5:

F(k+1)n = Fkn+n = Fn+1Fkn + FnFkn-1 (nach 4.1.1)

Da Fn+1Fkn $ \equiv$ 0  ( modFn) wegen Fkn als Faktor (der nach Induktionsannahme durch Fn teilbar ist) und FnFkn-1 $ \equiv$ 0  ( modFn) wegen Fn als Faktor gilt, folgt damit auch F(k+1)n $ \equiv$ 0  ( modFn), womit der Induktionsbeweis bereits abgeschlossen ist.

Wenn wir berücksichtigen, daß F2 = 1 keine Primzahl ist, können wir das Resultat sogar noch (scheinbar) allgemeiner fassen.

Folgerung:

Sei n > 4 eine zusammengesetzte Zahl, dann ist auch Fn zusammengesetzt.

Umkehrschluß:

Wenn Fn eine Primzahl ist, dann ist auch n eine Primzahl oder n $ \leq$ 4.

5.2 L(2k+1)n

Für die Lucasfolge ergibt sich bei Betrachtung der ungeraden Faktoren im Index ein ähnliches Resultat. Die Induktion über k verhält sich ansonsten analog zum vorherigen Beweis:

k = 0 : L(2k+1)n = Ln $ \equiv$ 0  ( modLn)

Sei nun nach Induktionsannahme L(2k+1)n $ \equiv$ 0  ( modLn). Mit 4.1.1 erhalten wir für k + 1:

L(2(k+1)+1)n = L(2k+3)n = L(2k+1)n+2n

= F2n+1L(2k+1)n + F2nL(2k+1)n-1

= F2n+1L(2k+1)n + FnLnL(2k+1)n-1

Der erste Summand ist nach Induktionsannahme, der zweite wegen Ln als enthaltenem Faktor durch Ln ohne Rest teilbar. Die Teilbarkeit geht damit auf die Summe über.

5.3 Natürliche Zahlen als Teiler

Alle positiven natürlichen Zahlen kommen in der speziellen Fibonaccifolge unendlich oft als Teiler vor. Sei t eine beliebige positive natürliche Zahl, dann existiert eine Periode Pt mit der Maximallänge t2, für die gilt: Fk . Pt $ \equiv$ 0 ( mod t)

5.3.0.1 Beweis:

Die Existenz einer Periode Pt wird durch 2.2.2 gesichert. Zu zeigen bleibt, daß diese auch den Nullwert enthält.

Nehmen wir an, es gäbe eine Konstante c > 0, so daß die Periodizität erst ab diesem c erfüllt wäre und insbesondere gilt: Fc-1 $ \neq$ Fc-1+Pt ( mod t). (Wenn diese Konstante c nicht existiert, dann gilt Fk . Pt $ \equiv$ F0 . Pt $ \equiv$ F0 $ \equiv$ 0 ( mod t) und unsere Behauptung wäre bewiesen.)

Nach Definition der Fibonaccifolge gilt Fc-1 + Fc = Fc+1 und Fc-1+Pt + Fc+Pt = Fc+1+Pt, somit wegen der Periodizität auch Fc+1 - Fc $ \equiv$ Fc+1+Pt - Fc+Pt ( mod t). Das ist aber äquivalent zu Fc-1 $ \equiv$ Fc-1+Pt ( mod t), was unserer Annahme widerspricht. $ \square$

5.4 Fünf Kostbarkeiten


5.4.1 Primfaktoren an Primstellen

Jeder an einer Primstelle p auftauchende Primfaktor von Fp taucht dort das erste Mal auf.

5.4.1.1 Beweis:

Dies folgt beinahe unmittelbar aus 5.4.2: $ \prod_{{i=1}}^{{p-1}}$gcd(i, p) = 1   $ \Longrightarrow$  $ \prod_{{i=1}}^{{p-1}}$gcd(Fi, Fp) = 1.


5.4.2 Teilerfremde Indices

Sind zwei Indices teilerfremd, so auch deren Fibonaccizahlen: gcd(r, s) = 1 $ \Longrightarrow$ gcd(Fr, Fs) = 1.

5.4.2.1 Beweis:

Sei gcd(r, s) = 1 mit r, s > 1. Wegen Teilerfremdheit von r und s existieren m1, m2, so daß r . m1 +1 = s . m2 = : h erfüllt wird (vgl. Chinesischer Restsatz, z.B. [FrIs92]; setze beispielsweise m2 : = s-1 mod r und m1 : = $ {\frac{{s\cdot m_{2}-1}}{{r}}}$).

Mit 5.1 folgt daraus Fh-1 = Fr . m1 $ \equiv$ 0 ( mod Fr) sowie Fh = Fs . m2 $ \equiv$ 0 ( mod Fs). Für t : = gcd(Fr, Fs) gilt somit Fh-1 $ \equiv$ Fh $ \equiv$ 0 ( mod t). Mit 2.2.1 folgt die Teilbarkeit aller Fibonacciwerte durch t, insbesondere auch für F1 = 1. Aus 0 $ \equiv$ 1 ( mod t) folgt t = 1, womit der Beweis abgeschlossen wäre.

5.4.3 Fibonaccizahlen mit gemeinsamen Teiler

Haben zwei Fibonaccizahlen einen nichttrivialen gemeinsamen Teiler, so haben auch ihre Indices einen nichttrivialen gemeinsamen Teiler.

5.4.3.1 Beweis:

Dies folgt im Umkehrschluß aus dem vorigen Satz: a $ \Rightarrow$ b   $ \models$  ¬b $ \Rightarrow$ ¬a.

5.4.4 Indices mit gemeinsamen Teiler

Haben zwei Indices einen gemeinsamen Teiler größer als zwei, so haben die zugehörigen Fibonaccizahlen einen gemeinsamen Teiler größer als eins: gcd(r, s) > 2  $ \Longrightarrow$  gcd(Fr, Fs) > 1.

5.4.4.1 Beweis:

Für t : = gcd(r, s) > 2 gilt Ft > F2 = 1. Mit 5.1 folgt Fr $ \equiv$ 0 ( mod Ft) und Fs $ \equiv$ 0 ( mod Ft), mithin gcd(Fr, Fs) $ \geq$ Ft > 1. $ \square$

5.4.5 Teilerfremde Fibonaccizahlen

Sind zwei Fibonaccizahlen teilerfremd, so beträgt der größte gemeinsame Teiler der zugehörigen Indices höchstens zwei.

5.4.5.1 Beweis:

Dies folgt im Umkehrschluß aus dem vorigen Satz: a $ \Rightarrow$ b   $ \models$  ¬b $ \Rightarrow$ ¬a.

Thorsten Reinecke 2004-07-11