# 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 is$p_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.