Fibonacci Numbers mod n

Taking the fibonacci sequence mod 2 provides this pattern:

Sequence:              1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,…
Sequence mod 2:   1, 1, 0, 1, 1, 0,   1,   1,   0,   1,   1,      0,    1,     1,…

Taking the fibonacci sequence mod 3 also produces an interesting pattern:

Sequence:              1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,…
Sequence mod 3:   1, 1, 2, 0, 2, 2,   1,   0,   1,   1,   2,      0,    2,     2,…

Mod 4:

Sequence:              1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,…
Sequence mod 4:   1, 1, 2, 3, 1, 0,   1,   1,   2,   3,   1,      0,    1,     1,…

This can be continued for mod n.

Consider this table from Pisano Periods – Wikipedia :

(let p_n be the period of fibonacci numbers mod n)

n p_n cycle
1 1 0
2 3 011
3 8 0112 0221
4 6 011231
5 20 01123 03314 04432 02241
6 24 011235213415 055431453251
7 16 01123516 06654261
8 12 011235 055271
9 24 011235843718 088764156281
10 60 011235831459437 077415617853819 099875279651673 033695493257291

Note also:

  • 2*3=6 which isp_4
  • 4*6=24 which is p_6 and p_9
  • 3*8=24 which is p_6 and p_9
  • the period for n=5 is 20, while the period for n=10 is 60. p_{2n}=3p_n for n=1,2 , n=3,6 and n=5,10 , and n=7,14 (p_{14}=48 according to OEIS)

Can we say that p_{2n}=3p_n \forall n \mid n \equiv 1 \mod 2 ?

Answer: no. n=9 provides a counter example because p_9=24 and p_{18}=24 . Therefore, p_{2n} \neq3p_n where n=9 .

If we extend our table, we can also see that p_{10}=60 and p_{50}=300 . In this case, p_{5n}=5p_n . This also works for n=5,25 , n=9,45 and possibly more. However n=1,5 and n=2,10 do not work. Can we say that p_{5n}=5p_n \forall n>2 ?

Answer: no, n=4 and n=11 do not work. Why are these special cases?

I’ll write a program to test this stuff more when I get home today.

Advertisements