Pisano period π(m): Fibonacci mod m repeats with period π(m). π(1)=1, π(2)=3, π(3)=8, π(4)=6, π(5)=20, π(6)=24, π(7)=16, π(8)=12, π(9)=24, π(10)=60. For prime p: π(p) | p²−1. For p≡±1(mod 5): π(p) | p−1. For p≡±2(mod 5): π(p) | 2(p+1).
How to Use
Enter modulus m:
- π(m): Pisano period
- Sequence: F(n) mod m
- Pattern: Periodic block
Properties
- π(m) always exists (pigeonhole)
- π(mn) = lcm(π(m),π(n)) when gcd(m,n)=1
- For prime p: π(p) | p²−1
- π(10)=60, so last digits of Fibonacci repeat every 60
Applications
Finding F(n) mod m efficiently: compute n mod π(m), then F(n mod π(m)) mod m. This reduces astronomical Fibonacci index computations to manageable size. Used in competitive programming and cryptography.
Step-by-Step Instructions
- 1Enter modulus m.
- 2Compute π(m).
- 3See Fib mod m.
- 4Verify period.
- 5Use for F(n) mod m.