= Fibonacci gcd reduction
{c}
{title2=$\gcd(F_m,F_n)=\gcd(F_{m-n},F_n),\quad m\ge n$}
Consecutive <Fibonacci numbers> are <coprime> by the <Euclidean algorithm>. The <Fibonacci addition formula> writes $F_m=F_{m-n}F_{n+1}+F_{m-n-1}F_n$ for $m>n$. Taking the <greatest common divisor> with $F_n$ removes the last summand, and multiplication by the <coprime> factor $F_{n+1}$ leaves that gcd unchanged. The case $m=n$ uses $F_0=0$. Applying the <Euclidean algorithm> to the indices yields the strong-divisibility identity $\gcd(F_m,F_n)=F_{\gcd(m,n)}$ for nonnegative indices, with the usual zero conventions.
Back to article page
