Fibonacci teilbarkeit < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:26 Mi 20.04.2011 | | Autor: | kushkush |
| Aufgabe | Seien [mm] $f_{0}=0$, $f_{1}=1$, $f_{n}=f_{n-1}+f_{n-2}$ [/mm] $(n=2,3...)$.
i) Man zeige, dass [mm] $f_{n}-4$ [/mm] nie durch 8 teilbar ist.
ii) Man zeige, dass es unendlich viele n gibt, mit [mm] $f_{n} [/mm] durch 8000 teilbar. |
Hallo,
i) Ich betrachte die Restklassen
und die wiederholen sich nach je 12 Klassen [mm] $\tilde{f_{n}-4}\backslash 8\b{Z}$ [/mm] : [mm] \{ -4,-5,-5,-6,7,7,5,1,1,2,3,3\} [/mm]
Also hat es nur 12 Restklassen und keine davon ist 0 daher nicht teilbar durch 8.
ii) hier ist eine Wiederholung der Klassen nach unendlich vielen Ziffern? Kann man sagen dass sich die Klassen nach unendlich vielen Ziffern wiederholen und deswegen reicht es wenn ich in der ersten Abfolge eines finde, welches durch 8000 teilbar ist ohne Rest?
Danke und Gruss
kushkush
|
|
| |
|
Hallo kushkush,
da stimmt noch was nicht, wahrscheinlich in der Aufgabenstellung.
> Seien [mm]f_{0}=0[/mm], [mm]f_{1}=1[/mm], [mm]f_{n}=f_{n-1}+f_{n-2}[/mm] [mm](n=2,3...)[/mm].
Ok, Standard-Fibonacci.
> i) Man zeige, dass [mm]f_{n-4}[/mm] nie durch 8 teilbar ist.
Das kann so nicht stimmen, z.B. für n=10 und n=16.
Ich nehme an, es handelt sich nur um einen Tippfehler, und man soll zeigen, dass [mm] f_n-4 [/mm] nie durch 8 teilbar ist. Oder?
> ii) Man zeige, dass es unendlich viele n gibt, mit [mm]$f_{n}[/mm]
> durch 8000 teilbar.
>
> Hallo,
>
> i) Ich betrachte die Restklassen
>
> und die wiederholen sich nach je 12 Klassen
> [mm]\tilde{f_{n}-4}\backslash 8\b{Z}[/mm] : [mm]\{ -4,-5,-5,-6,7,7,5,1,1,2,3,3\}[/mm]
Da habe ich andere Werte, aber die Periode von 12 stimmt jedenfalls. Vielleicht verstehe ich auch nur nicht, was Du da genau notierst.
> Also hat es nur 12 Restklassen und keine davon ist 0 daher
> nicht teilbar durch 8.
Ja, genau.
> ii) hier ist eine Wiederholung der Klassen nach unendlich
> vielen Ziffern?
Schlecht formuliert. Und es geht in der Tat um eine Periode, also eine Wiederholung nach endlich vielen Schritten (nicht Ziffern).
> Kann man sagen dass sich die Klassen nach
> unendlich vielen Ziffern wiederholen und deswegen reicht es
> wenn ich in der ersten Abfolge eines finde, welches durch
> 8000 teilbar ist ohne Rest?
Ja, eins musst Du finden, und Du musst außerdem zeigen, dass die Restklassen [mm] \mod{8000} [/mm] sich periodisch wiederholen (ohne dass notwendig auch die Periodenlänge zu bestimmen wäre, Hauptsache, sie ist fest).
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:49 Do 21.04.2011 | | Autor: | kushkush |
Hallo reverend,
> Tippfehler
> Da habe ich andere Werte
Ich habe 4 abgezogen von der Fibonacci Folge und die Differenz zur nächsten Potenz von (-)8 gebildet.
Wie hast du denn die Werte berechnet?
> Eines finden Rest beweisen
Ein solches ist doch 0? Es gibt immer einen wiederholende Periode, weil es nur eine endliche Anzahl von Resten gibt wenn man mit n dividiert (n-1) und deshalb gibt es auch eine endliche Anzahl von Paaren von Resten. Also muss irgendeinmal eine Wiederholung anfangen.
> GrüBe
Danke!
Gruss
kushkush
|
|
|
| |
|
Guten Morgen!
> > Da habe ich andere Werte
>
> Ich habe 4 abgezogen von der Fibonacci Folge und die
> Differenz zur nächsten Potenz von (-)8 gebildet.
> Wie hast du denn die Werte berechnet?
Ach so. Ich hatte direkt [mm] \mod{8} [/mm] gerechnet. Nebenbei: nicht Potenz, Vielfaches von 8. Aber das hast Du ja auch gemacht.
> > Eines finden Rest beweisen
>
> Ein solches ist doch 0? Es gibt immer einen wiederholende
> Periode, weil es nur eine endliche Anzahl von Resten gibt
> wenn man mit n dividiert (n-1) und deshalb gibt es auch
> eine endliche Anzahl von Paaren von Resten. Also muss
> irgendeinmal eine Wiederholung anfangen.
Das reicht nicht als Grund. Dann könnte man auch aus einer endlichen Zahl von Ziffern (z.B. 3,4,5,6,7) nur periodische Dezimalbrüche bilden, aber keine transzendenten (oder auch nur irrationalen) Zahlen.
Die Fibonacci-Zahlen müssen [mm] \mod{64} [/mm] und [mm] \mod{125} [/mm] periodische Restklassen haben, dann gilt das auch für 8000=64*125.
Es genügt dazu aber, folgende vier Äquivalenzen zu zeigen:
[mm] f_{64}\equiv f_0 \equiv 0\mod{64}
[/mm]
[mm] f_{65}\equiv f_1\equiv 1\mod{64}
[/mm]
[mm] f_{125}\equiv f_0\equiv 0\mod{125}
[/mm]
[mm] f_{126}\equiv f_1\equiv 1\mod{125}
[/mm]
Viel Erfolg!
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:18 Do 21.04.2011 | | Autor: | kushkush |
Hallo reverend!
> Ja
> reicht nicht !
> Es reicht
Danke!!
> Viel Erfolg
Gruss
kushkush
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:35 Do 21.04.2011 | | Autor: | reverend |
Hallo kushkush,
ich bin einem Denkfehler aufgesessen.
Die Periodenlänge muss gar nicht 64 und 125 sein, Hauptsache, die Fibonacci-Zahlen sind zum betreffenden Modul periodisch.
Die Periodenlänge [mm] \mod{64} [/mm] beträgt 96, und die [mm] \mod{125} [/mm] beträgt 500.
Damit ergibt sich die Periodenlänge [mm] \mod{8000} [/mm] zu 12000.
Sorry, da war ich wohl zu schnell.
Nebenbei: die beiden Periodenlängen sind "experimentell" ermittelt; ich sehe auch gerade nicht, wie das anders ginge.
Grüße
reverend
|
|
|
|
