Diese Formel liefert die Fibonaccizahl Nummer n!

Wenn man die Fibonaccizahlen durchnummeriert:

Nummer | Fibonaccizahl
1 | 1
2 | 1
3 | 2
4 | 3
5 | 5
6 | 8
7 | 13
8 | 21
9 | 34
... | ...

Es sei m die Nummer der zu zerlegenden Fibonaccizahl!
Es sei n die Nummer einer beliebigen Fibonaccizahl!
Wenn Nummer n Nummer m teilt, so hat die Fibonaccizahl Nummer n die Fibonaccizahl Nummer m.

Als Formel:

n|m => f(n)|f(m)

Beispiel:
n=4
m=8
m:n=2 => n teilt m => f(n) teilt f(m) => f(m)=f(n)*k -> k ist das Produkt der restlichen Primfaktoren!
=>f(m)=3*k => f(m):3=k => Man muss nur noch die Primfaktorenzerlegung von k finden. Das ist einfacher als die Primfaktorenzerlegung von f(m) zu finden, da k<f(m)
f(m)=21 => k=21:3=7

Das nächste wird ein bisschen komplizierter

Erstmal die Formel:

ggT{f(n);f(m)}=f(ggT{n;m})
Wer das versteht, bekommt nen Keks!
Der größte gemeinsame Teiler der Fibonaccizahlen Nummer n und m ist gleich der Fibonaccizahl mit der Nummer q [=f(q)].
Es gilt: q ist der größte gemeinsame Teiler von n und m
Also gilt: f(m)=f(q)*k -> k ist das Produkt der restlichen Primfaktoren!

Beispiel:
m=18
n=12
ggT{n;m}=6 => f(6) teilt f(m) => f(m=18)=f(6)*k
=> f(18):f(6)=k => k=323=17*19


Man kann übrigens mehrere Primfaktoren herausfinden, wenn man beide Ansätze miteinander kombiniert!

Beispiel:
m=18
n1=12
[nach: siehe 2.Ansatz] f(m=18)=f(6)*k
f(6)=8=2*2*2 => 2^3 teilt f(18)
[nach: siehe 1.Ansatz] f(m=18)=f(9)*i -> i ist das Produkt der restlichen Primfaktoren! Es gilt: i ungleich f(6) und f(9) ungleich k
f(9)=34=2*17 => 17*2 teilt f(18)
Achtung! Es folgt nicht: 17*2^4 teilt f(18), da die "2" von "17*2" einer der Primfaktoren aus "2^3" sein kann (und im Beispiel auch ist. ).

460835978753503578226215883073872246385764472086797082873203188542544616448248343576 | 2^3 * 269 * 4021 * 116849 * 1429913 * 24994118449 * 2686039424221 * 940094299967491 * 5050260704396247169315999021 | 10^11 * 100001101 * 111110110101 * 11100100001110001 * 101011101000110011001 *
10111010001110000111111101100110001 * 100111000101100100011011001111110011011101 *
11010101110000001011000010110011100001000000000011 * 100000101000101111010010011010101110111000001001100110100111111100001110101011000110100101101