30/05/2011

Thoughts on Fibonacci Numbers

In 1988, round about the time I first learned of Binet’s formula

$F_n = \frac{\left (1 + \sqrt{5} \right )^n - \left (1 - \sqrt{5} \right )^n}{2^n \sqrt{5}} \qquad \qquad \forall n \geq 0$

which appears to have been described by de Moivre some 50 years before Binet was born, I was calculating

$F_n \bmod{n}$

for no good reason on my very own Casio FX730P

when a friend looked over my shoulder and made a discovery. She had noticed that

$F_p \equiv \pm1 \pmod{p} \qquad \qquad \text{if }p \text{ is prime}, p \neq 5$

(The prime 5 had soon to be excluded, since F₅ = 5 ≡ 0 (mod 5).)

The program was modified to confirm this conjecture, at least in the Casio’s integer range. It became clear that a prime p was sufficient but not necessary, because early on we found

$F_{4} \equiv -1 \pmod{4}\\F_{14} \equiv -1 \pmod{14}\\F_{22} \equiv +1 \pmod{22}\\F_{26} \equiv -1 \pmod{26}\\F_{34} \equiv -1 \pmod{34}\\F_{38} \equiv +1 \pmod{38}\\F_{46} \equiv -1 \pmod{46}\\F_{58} \equiv +1 \pmod{58}\\F_{62} \equiv +1 \pmod{62}\\F_{74} \equiv -1 \pmod{74}\\F_{82} \equiv +1 \pmod{82}\\F_{86} \equiv -1 \pmod{86}\\F_{94} \equiv -1 \pmod{94}\\$

Those were all even numbers, they couldn’t be prime anyway. We were now looking for

$F_n \equiv \pm1 \pmod{n} \qquad \qquad \text{where }n \text{ is odd and not prime}$

Those were the first we found

$F_{323} = 17 \cdot 19 \equiv +1 \pmod{323}\\F_{2737} = 7 \cdot 17 \cdot 23 \equiv +1 \pmod{2737}\\F_{4181} = 37 \cdot 113 \equiv +1 \pmod{4181}\\F_{5777} = 53 \cdot 109 \equiv -1 \pmod{5777}\\F_{6479} = 11 \cdot 19 \cdot 31 \equiv +1 \pmod{6479}\\F_{6721} = 11 \cdot 13 \cdot 47 \equiv +1 \pmod{6721}\\F_{7743} = 3 \cdot 29 \cdot 89 \equiv +1 \pmod{7743}\\$

I could not find how these numbers were connected. Still, our initial conjecture was pretty cool. I showed it to a few mathematicians who assured me we were on to something. I never managed to prove it and eventually forgot about it. Then in May 2008 a paper captured my attention[1]. It includes reference to a proof in [2]. It turns out that the conjecture can be made more precise:

$\text{For }p\text{ a prime, }k > 0\\F_p \equiv\begin{cases} +1 \pmod{p}, & p = 5k\pm1\\ -1 \pmod{p}, & p = 5k\pm2\end{cases}$

[1] V. E. Hoggatt, Jr. and Marjorie Bicknell: Some Congruences of the Fibonacci Numbers Modulo a Prime P; Mathematics Magazine, Vol. 47, No. 4, (Sep., 1974), pp. 210-214

[2] G. H. Hardy, and E. M. Wright: An Introduction to the Theory of Numbers; 4th ed., Oxford University Press, 1960

Sharing is caring.

Post a comment Cancel reply