Fibonacci Modulo Calculator
Calculate F(n) mod m for very large n using fast matrix exponentiation.
Input
Matrix Method:
[F(n+1), F(n)] = [[1,1],[1,0]]^n × [1, 0]
Computes F(n) in O(log n) time using matrix exponentiation.
F(100) mod 1,000,000,007
687995182
Lucas Number L(100)
876413006
GCD(F(100), 1000000007)
1
First Fibonacci Numbers mod 1000000007
F(0)=0F(1)=1F(2)=1F(3)=2F(4)=3F(5)=5F(6)=8F(7)=13F(8)=21F(9)=34F(10)=55F(11)=89F(12)=144F(13)=233F(14)=377F(15)=610F(16)=987F(17)=1597F(18)=2584F(19)=4181F(20)=6765F(21)=10946F(22)=17711F(23)=28657F(24)=46368F(25)=75025F(26)=121393F(27)=196418F(28)=317811F(29)=514229F(30)=832040
Fibonacci Identities
Pisano Period
F(n) mod m is periodic with period π(m). For prime p, π(p) divides p² - 1 (or p - 1 if p ≡ ±1 mod 5).
GCD Property
gcd(F(m), F(n)) = F(gcd(m, n)). The GCD of two Fibonacci numbers is itself a Fibonacci number.