Problem
NT-B2-M12-P010 Fibonacci Periodicity
#10
★★★☆☆ Level 3 of 5
Let \(F_0=0\), \(F_1=1\), \(F_{n+2}=F_{n+1}+F_n\). Prove that the sequence \(F_n\) is periodic modulo every \(m\ge2\).
Consider pairs of consecutive residues.
The pairs \((F_n,F_{n+1})\) modulo \(m\) have at most \(m^2\) possible values, so some pair repeats. The transition \((x,y)\mapsto(y,x+y)\) is reversible modulo \(m\): from \((y,z)\) we recover \((z-y,y)\). Hence, once a pair repeats, the period extends backward to the initial pair \((0,1)\). Therefore the sequence is periodic from the start.
Reversibility distinguishes Fibonacci from an arbitrary recurrence.