Fibonacci-Folge, Beweis von ggT |
| 08.04.2005, 12:37 | knoten | Auf diesen Beitrag antworten » | ||
| Fibonacci-Folge, Beweis von ggT |
||||
| 08.04.2005, 12:55 | Tobias | Auf diesen Beitrag antworten » | ||
Nun, es sei die Fibanacci-Folge. Nimm zwei beliebige Elemente heraus und betrachte dann benutze die Rekursionsvorschrift und schaue, ob du den ggT so reduzieren kannst. Zuletzt wird man auf einer Form von landen wollen. |
||||
| 08.04.2005, 15:24 | flixgott | Auf diesen Beitrag antworten » | ||
ich würde sagen, dass sich das mit vollständiger induktion lösen lassen müßte, ein anfang währe folgender: IA: ggt(1,1)=1 (klar) IV: ggt(Fi,Fi+1)=1 IB: ggt(Fi+1,Fi+2)=1 ggt(Fi+1,Fi+2)=ggt(Fi+2,Fi+1)=ggt(Fi+1 + Fi,Fi+1) ich glaube (kann aber noch nicht beweisen), dass für b<a folgende aussage gilt: ggt(a+b,a)=ggt(b,a). wenn das gezeigt ist dann würde gelten: ggt(Fi+1 + Fi,Fi+1)=ggt(Fi,Fi+1)=1 |
||||
| 08.04.2005, 15:42 | AD | Auf diesen Beitrag antworten » | ||
Gilt sogar für alle ganzen Zahlen a,b . Der Beweis ist sehr einfach, wenn man weiß, wie der ggt definiert ist. |
||||
| 08.04.2005, 15:44 | flixgott | Auf diesen Beitrag antworten » | ||
ich weiss intuitiv wie es definiert ist.. dann war aber die ganze aufgabe mehr als einfach! |
||||
| 08.04.2005, 15:51 | AD | Auf diesen Beitrag antworten » | ||
Ok, ich schreib den "Dreizeiler" mal spaßeshalber auf, obwohl die Mühe kaum lohnt: 
Sei u=ggt(a,b) --> u|a und u|b --> u|a und u|(a+b) --> u|ggt(a,a+b) . Sei v=ggt(a,a+b) --> v|a und v|(a+b) --> v|a und v|(a+b-a), also v|b --> v|ggt(a,b) . Aus ggt(a,b)|ggt(a,a+b) und ggt(a,a+b)|ggt(a,b) folgt ggt(a,a+b)=ggt(a,b) . |
||||
| Anzeige | ||||
|
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
