Recursionmedium
0:00.0

The Fibonacci sequence modulo 3 is defined by FnFn1+Fn2(mod3)F_n \equiv F_{n-1} + F_{n-2} \pmod{3} with F00,F11(mod3)F_0 \equiv 0, F_1 \equiv 1 \pmod{3}. Compute the sequence and determine the period (the smallest positive pp such that (Fp,Fp+1)(F0,F1)(mod3)(F_p, F_{p+1}) \equiv (F_0, F_1) \pmod{3}).