Fibonaccifolge in Restklassengruppe

27.08.2009, 09:29

anako

Fibonaccifolge in Restklassengruppe

Wollte fragen, ob mir jemand einen Tip geben kann, wie man die Beziehung findet zwischen dem Modul n einer Restklassengruppe Zn/Z und der Länge der Periode der Fibonacci-Folge darin. In (Z5/Z, +) etwa hat die Fibonacci-Folge
(0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0, 1, 1, 2, 3, ...)
eine Periode der Länge 20. Eine obere Schranke für diese Länge wäre ja das Quadrat von n. Habe versucht, die Länge der Periode, abhängig vom Modul n, herauszukriegen, konnte es noch nicht finden. verwirrt

27.08.2009, 09:48

Auf diesen Beitrag antworten »

Hmm, außer dem kleinen Zusatz, dass zwei aufeinander folgende Nullen bei den Resten sicher nicht auftreten können, fällt mir da zunächst auch nichts ein. Und der bewirkt lediglich, dass die Periode nach oben durch $\begin{eqnarray*} n^2-1 \end{eqnarray*}$ beschränkt ist.

EDIT: Ok, vielleicht noch folgende interessante Eigenschaft. Sei $\begin{eqnarray*} p_n \end{eqnarray*}$ die kleinste Periodenlänge von $\begin{eqnarray*} F_k \bmod n \end{eqnarray*}$ , dann ist

$\begin{eqnarray*} m \Big| n \quad\Longrightarrow\quad p_m \Big| p_n \end{eqnarray*}$ .

Beispiel: $\begin{eqnarray*} p_2=3,p_3=8 \end{eqnarray*}$ , also folgt schon mal $\begin{eqnarray*} 24|p_6 \end{eqnarray*}$ . Da außerdem $\begin{eqnarray*} p_6 \leq 6^2-1=35 \end{eqnarray*}$ , bleibt zwangsläufig nur $\begin{eqnarray*} p_6=24 \end{eqnarray*}$ .

EDIT2: Nach kurzer Google-Suche

http://www.ijon.de/mathe/fibonacci/node3.html#0003210

aber das kennst du vielleicht schon.

08.09.2009, 00:21

Mystic

Auf diesen Beitrag antworten »

Für den Fall, wo der Modul eine Primzahl p ist, kann man sich die Periodenlänge $\begin{eqnarray*} \lambda(p) \end{eqnarray*}$ alternativ zu dem in dem obigem Link aufgezeigten Weg auch folgendermaßen ausrechnen, in dem man sich für p=2 und p=5 die Werte $\begin{eqnarray*} \lambda(2)=3 \end{eqnarray*}$ und $\begin{eqnarray*} \lambda(5)=20 \end{eqnarray*}$ wieder direkt berechnet und für die anderen Primzahlen p sich der bekannten Formel

$\begin{eqnarray*} F_n = \frac {\alpha^n-\beta^n} {\alpha -\beta} \end{eqnarray*}$

bedient, wobei

$\begin{eqnarray*} \alpha = \frac {1+\sqrt 5} 2 \end{eqnarray*}$ und $\begin{eqnarray*} \beta = \frac {1-\sqrt 5} 2 \end{eqnarray*}$

ist und diese Ausdrücke als Elemente des Körpers $\begin{eqnarray*} GF(p^2) \end{eqnarray*}$ interpretiert werden müssen.

Ist nun $\begin{eqnarray*} p \equiv \pm 1 \mod 5 \end{eqnarray*}$ , d.h. 5 quadratischer Rest mod p, so rechnet man de facto im Primkörper $\begin{eqnarray*} \mathbb Z_p \end{eqnarray*}$ von $\begin{eqnarray*} GF(p^2) \end{eqnarray*}$ und unter Benützung des "Kleinen Fermat's" folgt daher sofort

$\begin{eqnarray*} F_{p-1} = \frac {\alpha^{p-1}-\beta^{p-1}}{\alpha-\beta} =\frac {1-1}{\alpha-\beta} =0 \end{eqnarray*}$ und $\begin{eqnarray*} F_p = \frac {\alpha^p-\beta^p}{\alpha-\beta} =\frac {\alpha-\beta}{\alpha-\beta} =1 \end{eqnarray*}$

woraus sich weiter unmittelbar $\begin{eqnarray*} \lambda(p) \mid p-1 \end{eqnarray*}$ ergibt.

Der Fall $\begin{eqnarray*} p \equiv \pm 2 \mod 5 \end{eqnarray*}$ , wo also dann 5 quadratischer Nichtrest mod p ist, ist nur leicht komplizierter. Hier liegen $\begin{eqnarray*} \alpha \end{eqnarray*}$ und $\begin{eqnarray*} \beta \end{eqnarray*}$ dann außerhalb des Primkörpers $\begin{eqnarray*} \mathbb Z_p \end{eqnarray*}$ und werden beim Frobeniusautomorphismus $\begin{eqnarray*} x \mapsto x^p \end{eqnarray*}$ aufeinander abgebildet, d.h. $\begin{eqnarray*} \alpha^p= \beta \end{eqnarray*}$ und $\begin{eqnarray*} \beta^p =\alpha \end{eqnarray*}$ . (Man beachte, dass $\begin{eqnarray*} \alpha \end{eqnarray*}$ und $\begin{eqnarray*} \beta \end{eqnarray*}$ per definitionem zueinander konjugiert sind und der Frobeniusautomorphismus ist nichts anderes als die Konjugation in $\begin{eqnarray*} GF(p^2) \end{eqnarray*}$ , denn beide Automorphismen sind identisch zu dem einzigen nichttrivialen Automorphismus von $\begin{eqnarray*} GF(p^2) \end{eqnarray*}$ .)

Damit rechnet man nun leicht nach, dass gilt

$\begin{eqnarray*} F_{2(p+1)} = \frac {\alpha^{2(p+1)}-\beta^{2(p+1)}} {\alpha - \beta} = \frac {(\beta \alpha)^2-(\alpha \beta)^2} {\alpha-\beta} =\frac {(-1)^2-(-1)^2} {\alpha-\beta} = 0 \end{eqnarray*}$

sowie

$\begin{eqnarray*} F_{2(p+1)+1} =\ldots = \frac {(-1)^2\alpha-(-1)^2\beta} {\alpha-\beta} =1 \end{eqnarray*}$ ,

was also dann $\begin{eqnarray*} \lambda(p) \mid 2(p+1) \end{eqnarray*}$ beweist. Andererseits gilt zwar auch

$\begin{eqnarray*} F_{p+1} =\ldots = \frac {(-1)-(-1)} {\alpha-\beta} =0 \end{eqnarray*}$

jedoch

$\begin{eqnarray*} F_{p+2} =\ldots = \frac {(-1)\alpha-(-1)\beta}{\alpha-\beta}=-1 \end{eqnarray*}$

sodass also der Faktor 2 in obiger Teilbarkeitsbeziehung keinesfalls weggelassen werden darf.

Vielleicht findet ja an diesen Rechnungen irgendjemand Gefallen, obwohl oder gerade weil sie einiges an algebraischer Vorbildung erfordern, sodass ich sie nicht ganz umsonst durchgeführt habe...

08.09.2009, 09:11

Auf diesen Beitrag antworten »

Mal eine klitzekleine Frage von jemanden, der in dieser Algebra nicht so tief drinsteckt:

Wieso darf man für die nichtganze, ja sogar irrationale Zahl $\begin{eqnarray*} \alpha \end{eqnarray*}$ bei $\begin{eqnarray*} \alpha^{p-1} \end{eqnarray*}$ den "kleinen Fermat" anwenden? verwirrt

08.09.2009, 10:29

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Mal eine klitzekleine Frage von jemanden, der in dieser Algebra nicht so tief drinsteckt:

Wieso darf man für die nichtganze, ja sogar irrationale Zahl $\begin{eqnarray*} \alpha \end{eqnarray*}$ bei $\begin{eqnarray*} \alpha^{p-1} \end{eqnarray*}$ den "kleinen Fermat" anwenden? verwirrt

$\begin{eqnarray*} \alpha = \frac {1+\sqrt 5} 2 \end{eqnarray*}$ und $\begin{eqnarray*} \beta = \frac {1-\sqrt 5} 2 \end{eqnarray*}$ müssen, wie ich auch oben geschrieben haben, als Elemente von $\begin{eqnarray*} GF(p^2) \end{eqnarray*}$ interpretiert werden, wobei im Falle der Lösbarkeit von

$\begin{eqnarray*} x^2 \equiv 5 \mod p \end{eqnarray*}$

sogar schon der Restklassenring $\begin{eqnarray*} \mathbb Z_p \end{eqnarray*}$ , d.h., der Primkörper von $\begin{eqnarray*} GF(p^2) \end{eqnarray*}$ ausrreicht. $\begin{eqnarray*} \sqrt 5 \end{eqnarray*}$ steht dann einfach für eine der beiden Lösungen und ist keinesfalls irrational, sondern eher eine ganze Zahl, wobei diese aber als Vertreter für eine bestimmte Restklasse mod p aufzufassen ist.

Rechnen wir doch Ganze am Beispiel p=11 einmal durch... Indem ich nachfolgend etwas salopp die Restklassen $\begin{eqnarray*} \bar a \end{eqnarray*}$ kurz mit $\begin{eqnarray*} a \end{eqnarray*}$ bezeichne, hat die Gleichung $\begin{eqnarray*} x^2 =5 \end{eqnarray*}$ in $\begin{eqnarray*} \mathbb Z_{11} \end{eqnarray*}$ z.B. die Lösung 4, sodass wir dann für p=11 überall wo eine $\begin{eqnarray*} \sqrt 5 \end{eqnarray*}$ auftaucht dafür einfach 4 schreiben können. (Man könnte genausogut auch die andere Lösung, nämlich 7 nehmen, doch ändert das nichts, solange man konsequent dabei bleibt.) Ferner wird noch benötigt, dass 6 das Inverse zu 2 ist in $\begin{eqnarray*} \mathbb Z_{11} \end{eqnarray*}$ ist. Damit berechnet sich dann $\begin{eqnarray*} \alpha \end{eqnarray*}$ und $\begin{eqnarray*} \beta \end{eqnarray*}$ zu

$\begin{eqnarray*} \alpha = \frac {1+\sqrt 5} 2 = (1+4)6 = 8 \end{eqnarray*}$ und $\begin{eqnarray*} \beta = \frac {1-\sqrt 5} 2 = (1-4)6 = 4 \end{eqnarray*}$

und es ist $\begin{eqnarray*} \alpha - \beta = 4 \end{eqnarray*}$ , sowie $\begin{eqnarray*} (\alpha - \beta)^{-1} = 3 \end{eqnarray*}$ . Insgesamt ergibt sich somit

$\begin{eqnarray*} F_n = 3(8^n-4^n) \end{eqnarray*}$

wenn man das als Gleichung in $\begin{eqnarray*} \mathbb Z_{11} \end{eqnarray*}$ interpretiert.

Ich hoffe, dass nach diesen Ausführungen einiges klarer geworden ist...

08.09.2009, 17:29

Auf diesen Beitrag antworten »

Oh ja, da sieht man meine peinlichen Wissenslücken in der Algebra, insbesondere bei offenbar gebräuchlicher Terminologie wie hier dann $\begin{eqnarray*} \sqrt{5} \in \mathbb{Z}_p \end{eqnarray*}$ - entschuldige. Augenzwinkern

14.09.2009, 14:46

anako

Auf diesen Beitrag antworten »

Zuallererst möchte ich Arthur Dent und vor allem auch Mystic ausdrücklich danken für die tiefgehenden Antworten auf meine Frage nach der Periode in Fibonacci-Folgen mod n.
Den schon sehr weit gehenden Beitrag in dem Link
http://www.ijon.de/mathe/fibonacci/node3.html#0003210
habe ich noch nicht gekannt; ich werde das darin Enthaltene weiter studieren.
Besonderen Dank auch an Mystic für den zu obigem alternativen Weg, $\begin{eqnarray*} \lambda \left(p\right) \end{eqnarray*}$ dort auszurechnen, wo der Modul eine Primzahl ist. Ich brauche noch etwas länger, um das Gegebene durchzuarbeiten und verbleibe zunächst mit bestem Dank.

Neue Frage »

Antworten »

Fibonaccifolge in Restklassengruppe

Verwandte Themen