Fibonacci series modulo \(m\). (English) Zbl 0101.03201

Wall, D. D.

Am. Math. Mon. 67, 525-532 (1960).

Eine interessante, wenn auch teils bereits Bekanntes betreffende Untersuchung über die Periodenlänge der Reste mod \(m\) bei einer Fibonaccischen Zahlenfolge \((u_{n+1} = u_n + u_{n-1})\) im allgemeinen und bei der Folge mit dem Beginn \(0,1\) im besonderen; diese Längen seien \(h(m)\) und \(k(m)\) genannt. Das Problem besteht im wesentlichen für Primzahlpotenzmoduln \(p^n\); zu beliebigem \(m\) kommt man dann durch Bildung des kleinsten gemeinsamen Vielfachen. Es besteht manche Analogie zu den Potenzrestperioden.
Zunächst gibt es keine „Vorperiode“. Ist ferner \(k(p^2)\ne k(p)\), so gilt allgemein \(k(p^n) = p^{n-1}k(p)\); doch gibt es unterhalb 10000 keine Primzahl mit \(k(p^2) = k(p)\), was etwa analog \(2^{364} - 1 \equiv 0 (10^{932})\) wäre. Dies wurde mittels Computer festgestellt. (Hierzu vgl. auch nachstehendes Referat [Zbl 0101.03202].)
Für \(m=p=10n \pm 1\) gilt \(k\mid p-1\), für \(p= 10n \pm 3\) ist \(k\mid 2(p+1)\) und \(k\equiv 0(4)\); \(k (2) = 3\), \(k(5) = 20\). Übrigens ist \(k(m)\) für \(m>2\) immer gerade.
In der allgemeinen Folge mit dem Anfang \(a\), \(b\) und \((a, b, m) = 1\) hat man noch: Stets ist \(h\mid k\); \(h(p^n) = k(p^n)\) für \(p = 5n \pm 2\); bei \(m = 5^n\) ist \(h = k\) oder \(h = k/5\), je nachdem \(b^2 - ab - a^2 \not\equiv 0(5)\) oder \(\equiv 0(5)\); bei \(m = p^n\), \(p = 10n \pm 1\) ist \(h = k\) wenn \(h\) gerade, \(h = k/2\) wenn \(h\) ungerade. Immer wenn \((b^2 - ab - a^2, m) = 1\), ist \(h = k\).
Die Beweise sind elementar. Am Schlusse steht eine Liste der Werte \(k\) für alle Primzahlen unter 2000, bei denen \(k\) nicht den Höchstwert \(p-1\), bzw. \(2p + 2\) erreicht. Es sind dies 99 der insgesamt 301 Primzahlen außer 2 und 5.

Reviewer: Alexander Aigner (Graz)

MSC:

11B39	Fibonacci and Lucas numbers and polynomials and generalizations
11B50	Sequences (mod \(m\))

Keywords:

Fibonacci series modulo \(m\); period length of residues mod m

Citations:

Zbl 0101.03202