5 Teilbarkeiten

5.1 F_{k ^. n} und Primzahlen

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

Zunächst halten wir fest, daß F_{1 ^. n} = F_n $\equiv$ 0  ( modF_n) immer erfüllt ist. Nun zeigen wir per Induktion über k, daß F_kn $\equiv$ 0  ( modF_n) gilt⁵:

F_(k+1)n = F_kn+n = F_n+1F_kn + F_nF_kn-1 (nach 4.1.1)

Da F_n+1F_kn $\equiv$ 0  ( modF_n) wegen F_kn als Faktor (der nach Induktionsannahme durch F_n teilbar ist) und F_nF_kn-1 $\equiv$ 0  ( modF_n) wegen F_n als Faktor gilt, folgt damit auch F_(k+1)n $\equiv$ 0  ( modF_n), womit der Induktionsbeweis bereits abgeschlossen ist.

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

Folgerung:

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

Umkehrschluß:

Wenn F_n 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 = L_n $\equiv$ 0  ( modL_n)

Sei nun nach Induktionsannahme L_(2k+1)n $\equiv$ 0  ( modL_n). 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

= F_2n+1L_(2k+1)n + F_2nL_(2k+1)n-1

= F_2n+1L_(2k+1)n + F_nL_nL_(2k+1)n-1

Der erste Summand ist nach Induktionsannahme, der zweite wegen L_n als enthaltenem Faktor durch L_n 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 P_t mit der Maximallänge t², für die gilt: F_{k ^. Pt} $\equiv$ 0 ( mod t)

5.3.0.1 Beweis:

Die Existenz einer Periode P_t 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: F_c-1 $\neq$ F_c-1+Pt ( mod t). (Wenn diese Konstante c nicht existiert, dann gilt F_{k ^. Pt} $\equiv$ F_{0 ^. Pt} $\equiv$ F₀ $\equiv$ 0 ( mod t) und unsere Behauptung wäre bewiesen.)

Nach Definition der Fibonaccifolge gilt F_c-1 + F_c = F_c+1 und F_c-1+Pt + F_c+Pt = F_c+1+Pt, somit wegen der Periodizität auch F_c+1 - F_c $\equiv$ F_c+1+Pt - F_c+Pt ( mod t). Das ist aber äquivalent zu F_c-1 $\equiv$ F_c-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 F_p 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(F_i, F_p) = 1.

5.4.2 Teilerfremde Indices

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

5.4.2.1 Beweis:

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

Mit 5.1 folgt daraus F_h-1 = F_{r ^. m1} $\equiv$ 0 ( mod F_r) sowie F_h = F_{s ^. m2} $\equiv$ 0 ( mod F_s). Für t : = gcd(F_r, F_s) gilt somit F_h-1 $\equiv$ F_h $\equiv$ 0 ( mod t). Mit 2.2.1 folgt die Teilbarkeit aller Fibonacciwerte durch t, insbesondere auch für F₁ = 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(F_r, F_s) > 1.

5.4.4.1 Beweis:

Für t : = gcd(r, s) > 2 gilt F_t > F₂ = 1. Mit 5.1 folgt F_r $\equiv$ 0 ( mod F_t) und F_s $\equiv$ 0 ( mod F_t), mithin gcd(F_r, F_s) $\geq$ F_t > 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.