Photo by Ludde Lorentz on Unsplash

# Finding Modulo of Large Fibonacci Number

Fibonacci Numbers increase very rapidly as the sequence progresses, but is there a way to compute the modulo of the Fibonacci number that you are interested in. In this article I'll be explaining how I had to find this in order to complete a problem in a programming competition.

In a coding competition there was a problem, which was essentially to find,

$$ {Fib}(n) \ {mod} \ 10 \ {for} \ n \le 10^9 $$

As you may know fibonacci numbers increase very rapidly, given below is the \(100^{th}\) fibonacci number.

$$ {Fib}({100}) = {354224848179261915075} $$

So you can see that for an input about \(10^9\) it would be impossible to represent int a 64-bit integer value and it would also take a very long time.

To bypass this bottleneck I needed to find a way to compute the \({Fib}(n) \ mod \ m \ \forall(m\gt1)\) without having to compute very large fibonacci numbers. To do that we need to first get to know *The Pisano Period*

### The Pisano Period

Pisano Period, \(\pi(m)\) is defined as the period which the fibonacci sequence modulo \(m\) repeats.

For example lets take \(m = 2\)

\(n\) | \(Fib(n)\) | \(Fib(n) \ mod \ 2\) |

0 | 1 | 1 |

1 | 1 | 1 |

2 | 2 | 0 |

3 | 3 | 1 |

4 | 5 | 1 |

5 | 8 | 0 |

6 | 13 | 1 |

7 | 21 | 1 |

8 | 34 | 0 |

As you can see there is a pattern of period 3.

So essentially for a given number $m$ there is a number $\pi(m)$ which is the period at which the fibonacci sequence repeats itself.

If you need to know more about the Pisano Period, feel free to google it!

So lets code the `get_pisano_period`

function

```
def get_pisano_period(m):
a = 0
b = 1
for i in range(0, m*m):
c = (a + b) % m
a = b
b = c
if a == 0 and b == 1:
return i + 1
```

### Applying to the Problem

So how does the Pisano Period helps us in finding the modulo of fibonnaci number. Let me demonstrate,

Let \(Fib(n) \ mod \ m\) be the value we want to find

Let \(p = \pi(m)\), where \(\pi(x)\) is the Pisano Period of \(x\)

Then we know that the \(Fib(x) \ mod \ m\) function repeats after every \(p\) iterations.

We can express that as \(n = a*p + b \ (a,b \in \mathbb{N})\). So we only need to compute the \(Fib(b) \ mod \ m\).

The python code for that is as follows,

```
def fib(n):
if n == 0:
return 1
n1 = 0
n2 = 1
for i in range(0, n):
t = n1 + n2
n1 = n2
n2 = t
return n2
def fibmod(n, m):
p = get_pisano_period(m)
b = n % p
return fib(n) % m
```

So I hope you guys understood this article, if you have any doubts or you can think of a quicker way to find the modulo of fibonacci numbers please feel free to comment on it!