# 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](https://en.wikipedia.org/wiki/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

```python
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,

```python
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!