Maths WorkshopMaths problems with full solutions
Exercise 753Number theory › Divisibility and gcdL1Added 2 Nov 2026

A divisibility recurrence

#divisibility#recurrence#Euclidean algorithm

Statement

Let F0=0F_0=0, F1=1F_1=1, and Fn+2=Fn+1+FnF_{n+2}=F_{n+1}+F_n (Fibonacci). Show that \divisibility(Fn,Fn+1)=1\divisibility(F_n,F_{n+1})=1 for all nn.

Hint

Use the Euclidean algorithm relation \divisibility(Fn+1,Fn)=\divisibility(Fn,Fn−1)\divisibility(F_{n+1},F_n)=\divisibility(F_n,F_{n-1}).

Show solutionHide solution

Solution

Recurrence. From Fn+1=Fn+Fn−1F_{n+1}=F_n+F_{n-1}, we have
\divisibility(Fn+1,Fn)=\divisibility(Fn+Fn−1,Fn)=\divisibility(Fn−1,Fn).\divisibility(F_{n+1},F_n)=\divisibility(F_n+F_{n-1},F_n)=\divisibility(F_{n-1},F_n).
Iterating:
\divisibility(Fn+1,Fn)=\divisibility(Fn,Fn−1)=⋯=\divisibility(F2,F1)=\divisibility(1,1)=1.\divisibility(F_{n+1},F_n)=\divisibility(F_n,F_{n-1})=\cdots=\divisibility(F_2,F_1)=\divisibility(1,1)=1.

Conclusion. Consecutive Fibonacci numbers are always coprime.

Remark. This is a nice application of the invariance of the divisibility under the Euclidean step.

More problems in Divisibility and gcd

Ex.204Basic divisibility and linear combinations
#divisibility #linear combinations #divisors
Divisibility and gcd
High school
High school
Ex.205Consecutive integers are coprime
#coprime #consecutive integers #Euclidean algorithm
Divisibility and gcd
High school
High school
Ex.206Finding divisors systematically
#divisors #enumeration #bounds
Divisibility and gcd
High school
High school
Ex.232Divisibility rules
#divisibility rules #modular arithmetic #base 10
Divisibility and gcd
High school
High school