| Autor |
Beitrag |
    
Lars Weiser
| | Veröffentlicht am Mittwoch, den 14. Februar, 2001 - 12:41: | 
|
Wer kann dieses Problem beweisen ???
fib(0):=0
fib(1):=1
fib(n):=fib(n-1)+fib(n-2)
Zeige:
ggT(fib(n),fib(m)) = fib(ggT(n,m))
Ciao, Lars |
Hans (Birdsong)
| | Veröffentlicht am Mittwoch, den 14. Februar, 2001 - 15:11: |
|
Hallo :
Ich schreibe F(n) statt fib(n). Man geht aus von
der leicht beweisbaren Identitaet
(1) F(p + q) = F(p+1) F(q) + F(p) F(q-1)
fŸr beliebige ganzzahlige p,q. Ich denke mir dabei
F(n) nach "links" gemaess
F(-n) := (-1)^(n+1)*F(n)
fortgesetzt.
Damit zeigt man zunaechst durch Induktion bzgl. k:
(2) F(d) | F(k*d) fŸr k,d in N.
Der Induktionsschluss ergibt sich aus
F((k+1)d) = F(kd+1) F(d) + F(kd) F(d-1).
Nun sei d := ggt(m,n). Weil m und n Vielfache von
d sind, folgt aus (2) dass F(m), F(n) Vielfache
von F(d) sind, also
(3) F(d) | ggt(F(m),F(n))
Nach dem Hauptsatz Ÿber den ggt gilt ferner
(4) d = u*m + v*n mit u,v in Z
Mit (1) ergibt sich dann
F(d) = F(um+1) F(vn) + F(um) F(vn-1)
= x*F(n) + y*F(m) mit x,y in Z.
Jeder gemeinsame Teiler von F(m) und F(m) teilt
daher F(d), also gilt auch
(5) ggt(F(m),F(n)) | F(d)
Aus (3) und (5) folgt die Behauptung.
Gruss
Hans |
Lars Weiser
| | Veröffentlicht am Donnerstag, den 15. Februar, 2001 - 12:02: |
|
Danke Hans! |
|
