Problem
NT-B2-M12-P011 Divisibility by Index
#11
★★★☆☆ Level 3 of 5
Prove: if \(d\mid n\), then \(F_d\mid F_n\).
Show that \(F_d\mid F_r\) implies \(F_d\mid F_{r+d}\).
Use the identity \(F_{r+d}=F_{d-1}F_r+F_dF_{r+1}\). If \(F_d\mid F_r\), then both terms on the right are divisible by \(F_d\). Hence \(F_d\mid F_{r+d}\). Starting with \(r=d\), induction gives \(F_d\mid F_{2d},F_{3d},\ldots\). If \(n=td\), then \(F_d\mid F_n\).
The next step is the gcd of Fibonacci numbers.