Exercise 921Number theory › Divisibility and gcdL1Added 3 Nov 2026

A recursive GCD

#gcd#Fibonacci#recursion

Statement

Let $F_n$ be the Fibonacci sequence with $F_0=0$ , $F_1=1$ . Show that $\gcd(F_m,F_n)=F_{\gcd(m,n)}$ .

Hint

Use the Euclidean algorithm and the Fibonacci recurrence.

Show solutionHide solution

Key identity. $\gcd(F_m,F_n)=\gcd(F_{m-n},F_n)$ for $m>n$ (from $F_m=F_{m-n}F_{n+1}+F_{m-n-1}F_n$ ).

Iteration. This mirrors the Euclidean algorithm on $(m,n)$ , so the final gcd is $F_d$ where $d=\gcd(m,n)$ .

Conclusion. $\gcd(F_m,F_n)=F_{\gcd(m,n)}$ .

Example. $\gcd(F_6,F_4)=\gcd(8,3)=1=F_{\gcd(6,4)}=F_2=1$ .