Expert: Paul Klarreich - 2/5/2009

Question
Gi Paul,
I hope you can help.  I am including the question and what I have done so far to see if I am anywhere near my target.  Thank you!!!

Question:
Part a:
Let 0<n<m using Euclidean's algorithm, r_k = mx + ny.  Suppose the algorithm takes k steps.
Show that n>= F_(k+1) where F_1, F_2 etc are the Fibonacci numbers.

Part b:
with m,n,k as pervious, let t be the number of digits written in base 10.  Show that k<= 5t.

Work Done:
Part a:
Apply Euclidean algorithm to the Fib. numbers
F_(n+1), F_(n+2)
F_(n+2) = F_(n+1) + F_n
F_(n+1) = F_n + F_(n-1)
F_n = F_(n-1) + F_(n-2)
.
.
.
F_4= F_3 + F_2
F_3= 2F_2
Therefore gcd(F_(n+1), F_n(n+2)= 2F_2 = 1 and the algortithm uses n divions to find the gcd.
Let 0<n<m with r_0 = m and r_1 = n then
r_0=q_1r_1 + r_0
r_1 = q_2r-2 + r_3
r_2 = q_3r_3 + r_4
.
.
.
r_(n-2) = q_(n-2)r_(n-2) + r_(n-1)
r_(n-2)= q_(n-1)r_(n-1) + r_n
r_(n-1) = q_n(r_n)
Again we need n divisions and (q_1, q_2, ...,q_(n-1)>=1 and q_n>=2 since r_n< r_(n-1)  Therefore
r_n>=1 = F_2
r_(n-1)>= 2r_n>=2F_2 = F_3
.
.
.
n=r_1>= r_2 + r_3 >= F_n + F_(n-1) = F_(n=1)

Part b I have not started.
I am not even sure if I am on the right track with this proof.  Any help or criticism or whatever you can give would be awesome!

Thanks again!

Answer
Questioner:   karen
Category:  Advanced Math
Private:  No
 
Subject:  Abstract Algebra
Question:  Hi Paul,
I hope you can help.  I am including the question and what I have done so far to see if I am anywhere near my target.  Thank you!!!

Question:
Part a:
Let 0 < n < m using Euclidean's algorithm, r_k = mx + ny.  

Suppose the algorithm takes k steps.

Show that n >= F_(k+1) where F_1, F_2 etc are the Fibonacci numbers.

Part b:
with m,n,k as pervious, let t be the number of digits written in base 10.  Show that k<= 5t.

Work Done:
Part a:
Apply Euclidean algorithm to the Fib. numbers F_(n+1), F_(n+2)

F_(n+2) = F_(n+1) + F_n

F_(n+1) = F_n + F_(n-1)

F_n = F_(n-1) + F_(n-2)
.
.
.
F_4= F_3 + F_2
F_3= 2F_2


Therefore gcd(F_(n+1), F_n(n+2)= 2F_2 = 1 and the algortithm uses n divions to find the gcd.
Let 0<n<m with r_0 = m and r_1 = n then
r_0=q_1r_1 + r_0
r_1 = q_2r-2 + r_3
r_2 = q_3r_3 + r_4
.
.
.
r_(n-2) = q_(n-2)r_(n-2) + r_(n-1)
r_(n-2)= q_(n-1)r_(n-1) + r_n
r_(n-1) = q_n(r_n)
Again we need n divisions and (q_1, q_2, ...,q_(n-1)>=1 and q_n>=2 since r_n< r_(n-1)  Therefore
r_n>=1 = F_2
r_(n-1)>= 2r_n>=2F_2 = F_3
.
.
.
n=r_1>= r_2 + r_3 >= F_n + F_(n-1) = F_(n=1)

Part b I have not started.
I am not even sure if I am on the right track with this proof.  Any help or criticism or whatever you can give would be awesome!

Thanks again!
 


====================================
Aha! I think I know what you are trying to do in (a).  Show that if you apply the EA to find  gcd(m,n), with  m > n, and if it takes k steps, then the smaller number must be at least  F(k+1).  

(Saying that the Fibonacci numbers are the MOST DIFFICULT numbers to gcd-ize.)

I think basically you have it right, but the notation is a bit dense.  Let's try:

You have your two numbers, which we will call  M and N, with M being the larger.

You apply the EA:


here is the sequence of divisions.



M      = Q[k  ] N      + r[k  ],

N      = Q[k-1] r[k]   + r[k-1]

r[k  ] = Q[k-2] r[k-1] + r[k-2]

...


r[3 ] = Q[1  ] r[2] + r[1], which = 0


Now, at the bottom, r[2] >= 1, which is F1, and Q[1] >= 1;
therefore:

r[3] >= F2;

r[4 ] = Q[2  ] r[3] + r[2]

Since  r[2] >= F1,  r[3] >= F2,

r[4 ] >= Q[2  ] F2 + F1 >= F2 + F1 = F3.


Working our way up, on the (inductive) assumption that  

r[k] >= F[k-1] and  r[k-1] >= F[k-2], we will have:

N      = Q[k-1] r[k]   + r[k-1]
 >= Q[k-1]F[k-1] + F[k-2]
 >= F[k-1] + F[k-2]
 >= F[k]

I think that is what you were expected to prove.  [maybe I am off by one, but you can clean it up, I think.]

I also think this is about the same as your work, but your notation was a bit heavy.
........................
Part b:

with m,n,k as pervious, let t be the number of digits [OF WHICH NUMBER] written in base 10.  Show that k<= 5t.

I think this is saying the following:

Let m,n be any two numbers, m > n, and  k is the number of iterations of the E.A.
Further, let t be the number of decimal digits in n.

Some notation:  log = log[base 10],  L2 = log[base 2]



Now  n < 10^t, if n has t digits in base 10.
and that means log(n) < t


So how many iterations are needed for  m,n?  It is certainly less than the number of iterations needed if m,n were F[k+1] and F[k].

How many would that be?  Each time we iterate, the remainder is less than the smaller number, because it was the divisor.  Therefore, it is less than HALF of the larger number.

So our remainders are cut more than half each time, finally reaching 1.  How many are needed?  If k is the number, then

So k <= L2(n)

  = L2(10) log (n)

k <= 3.32 log(n)

k <= 3.32 t, which is even better.


Ex: Suppose n = 999.  (3 digits).
Now we certainly need at most 10 iterations, because 2^10 > 1000.

And  10 < 3.32 * log 1000 = 3.32 * 3