Question

Prove the claim at the end of the section about the Euclidean Algorithm and Fibonacci numbers. Specifically, prove that if positive naturals a and b are each at most F(n), then the Euclidean Algorithm performs at most n − 2 divisions. (You may assume that n > 2.)

Answer 1

Given that

The claim at the end of the section about the Euclidean Algorithm and Fibonacci numbers

we have f _n = f _x-1 +f _x-2

f _x+1 =f _x +f _x-1

f ₀ = 0 , f ₁ =1 ,f ₂ =1 , f ₃ = 2 , .........

Let us Show that g c d ( f _n ,f _n+1) = 1 by Mathematical Induction

g c d (f ₁ , f ₂ ) = g c d (1,1)= 1

The statement is true for n = 1

assume that the statement is true for n = k

g c d ( f _k , f _k+1 ) = 1

assume that the statement is true for n= k

g c d ( f _k , f _k+1 ) = 1

Let gcd   ( f _k , f _k+1 ) = d

   d

  

Now &

​​​​​​

d =   1

but d = gcd ( f _k+1 , f _k+2) > 0

d = 1

gcd ( f _k+1 , f _k+2 ) = 1

The statement is proved for n = k+1

by Mathematical Induction gcd( fx , f _x-1 ) = 1

Let us find gcd ( f _x , f _x+1 ) by Euclid's Algorithm

we have f_x+1 = (1)f_x +f _x-1 ; 0 < f _x-1 < f _x

f_x = (1) f _x-1+ f _x-2 ;  0 < f _x-2< f _x-1

f_x-1 = (1) f _x-2+ f _x-3 ;  0 < f_x-3 < f _x-2

continuing this process

f ₄ =  (1) f₃+ f ₂ ;  0 < f ₂< f ₃

f ₃ = (2) f ₂ +0

gcd (f_x ,f _x+1) = f ₂​​​​​​ = 1

(n-1) steps used to adopt Eucli d's Algorithm to conclude gcd (f_x ,f _x+1) = 1