Hallo!
vielleicht kann mir jmd bei folgendem Beweis helfen:
F_0 und F_1… seien Fibonaccizahlen.
man soll folgendes mit dem euklidischen Algo. zeigen: 1=ggT(F_j,F_(j+2)
grüße
hi,
F_0 und F_1… seien Fibonaccizahlen.
man soll folgendes mit dem euklidischen Algo. zeigen:
1=ggT(F_j,F_(j+2)
für die fibonaccis gilt allgemein:
F_j+2 = F_j + F_j+1
und man kann zeigen:
F_j+2 = 2 . F_j + F_j-1
beweis skizzenhaft:
wenn du also den euklidischen algorithmus aus F_j+2 und F_j loslässt, entsteht als erster rest F_j-1
der zweite schritt im algorithmus ist dann auf F_j und F_j-1 anzuwenden; da entsteht als rest F_j-2
dann auf F_j-1 und F_j-2 angewendet … liefert F_j-3
usw. bis nur mehr 1 bleibt.
q.e.d. (so ungefähr)
hth
m.