This document summarizes key results about the Euclidean algorithm for computing the greatest common divisor (GCD) of two numbers. It discusses how the remainders in the Euclidean algorithm form a decreasing Fibonacci-like sequence. It then proves that if the GCD requires n divisions, the smaller number must be greater than the (n+1)th Fibonacci number. Finally, it proves Lame's Theorem, which states that the number of divisions needed will never exceed five times the number of digits in the smaller number.
This document summarizes key results about the Euclidean algorithm for computing the greatest common divisor (GCD) of two numbers. It discusses how the remainders in the Euclidean algorithm form a decreasing Fibonacci-like sequence. It then proves that if the GCD requires n divisions, the smaller number must be greater than the (n+1)th Fibonacci number. Finally, it proves Lame's Theorem, which states that the number of divisions needed will never exceed five times the number of digits in the smaller number.
This document summarizes key results about the Euclidean algorithm for computing the greatest common divisor (GCD) of two numbers. It discusses how the remainders in the Euclidean algorithm form a decreasing Fibonacci-like sequence. It then proves that if the GCD requires n divisions, the smaller number must be greater than the (n+1)th Fibonacci number. Finally, it proves Lame's Theorem, which states that the number of divisions needed will never exceed five times the number of digits in the smaller number.
This document summarizes key results about the Euclidean algorithm for computing the greatest common divisor (GCD) of two numbers. It discusses how the remainders in the Euclidean algorithm form a decreasing Fibonacci-like sequence. It then proves that if the GCD requires n divisions, the smaller number must be greater than the (n+1)th Fibonacci number. Finally, it proves Lame's Theorem, which states that the number of divisions needed will never exceed five times the number of digits in the smaller number.
San Jose State College THE EUCLI DEAN ALGORI THM II 1. I NTRODUCTI ON In P a r t I [ l ] we s aw t hat t he g r e a t e s t c o mmo n d i v i s o r of . t wo n u mb e r s coul d be c onve ni e nt l y c o mp u t e d vi a t he f a mous Eu c l i d e a n a l g o r i t h m. Suppos e t ha t e x a c t l y n s t e ps ( di vi s i ons ) a r e r e q u i r e d t o c o mp u t e t he g. c. d. of s and t (s > t ) . We t he n ha ve (1) s = t q , + r , 0 < r < t (2) t = r , q^ + r , 0 < r ? < r (3) r x = r 2 q 3 + x y 0 < ^ < r z (4) r 2 = r 3 q 4 + r ^ 0 < T^ < r^ (5) r 3 = r 4 q 5 + r ^ Q < x 5 x 4 ( n- 1) r 0 = r ^ q -,+r 1 0 < r , < r 9 N ' n - 3 n - 2 ^ n - 1 n - 1 , n- 1 n - 2 (n) r ~ = r , q + 0 . x ' n - 2 n - 1 ^n Si nce e a c h quot i e nt q. > 1, t he a bove e qua t i ons i mp l y e t c , (2 1 ) t > r : + r 2 (3' ) r l - ^ r 2 + r 3 (4' ) r 2 > r 3 + r 4 (5' ) r 3 > r 4 + r 5 135 136 F' F. CJNr^Rt ' ^ ' r i i or w Apr i l Fr om (2 1 ) and ^ i, - ~, * -' , , ' /, I r om (4 f ) ? 2 r + r > (2 r . + 2 r J + r_, Si m: ^"Ly, L - -.. t 'i r \ ^ -! " r . > (3 r . + 3 r . ) + 2 r . , et c. Continuing In ch. -1 s JI* u % . .v j i<^ * he gener ous abundance of Fi bonacci number s . Thus t r , +r > 2r -1-r, > 3r n - f 2r , > 5r , +3r r 1 2 2 j ~~ ..:> 4 *~ 4 5 > , r _ + F n r _ "~ n-1 n- 2 n-2 n- 1 2. A BASIC RESULT Since the r emai nder s form a sti' i^tiy decr eas i ng sequence with r , the l ast n on- zer o r emai nder . n- 1 - c v r XI-& "* 1 1 - I Consequently, n- 1 xi" L n-L ) j - ! '"" n- 1 n-Z n+1 To s ummar i ze, if n di vi si ons a r e r equi r ed to comput e the g. c. d. of st s and t, then t i s at l east as l ar ge as the (n + 1) Fi bonacci number ! 3. LAME' S THEOREM Although the Eucl i dean al gor i t hm i s over 2, 000 year s old, the following r es ul t was est abl i shed by Gabr i el Lame in 1844. Theor em The number of di vi si ons r equi r ed to find the g c. d. of two num- ber s is never gr eat er than five t i mes the number of di gi t s in the s mal l er number . Proof. Let 4> desi gnat e the golden r at i o. In [2] it was shown t hat *p n = F n <t> + F n ^ | , n=l , 2, 3, . . . 1964 BEGINNERS' CORNER 137 Now si nce 2 > <t> = (1 + ^/5)/Z 9 we see t hat 2F + F , > F 4> + F , or n i i -1 n n- 1 F > * n n+2 Repl aci ng n by n~l and usi ng the "basi c r e s ul t " of the pr ecedi ng sect i on yi el ds t > * n - 1 . To compl et e the proof note t hat (i) if t has d di gi t s then d > log t (ii) log t > (n-1) log 0 (iii) log 4> > 1/5 . Thus d > ( n- l ) / 5 or n < 5d . REFERENCES 1. D. E. Thoro, "The Eucl i dean Al gor i t hm I, " Fi bonacci Quar t er l y, Vol. 2, No. 1, Febr uar y 1964. (Note t hat i ne xc e r c i s e s E8 and E10, (F . , , F ) and max (n, F- l ) v n+1 n n should be r epl aced by N(F , . , F ) and max N (n, F- l ) ^ J n+1 n' n r espect i vel y. ) 2. D. E. Thoro, "The Golden Rat i o: Comput at i onal Consi der a- t i ons, " Fi bonacci Quar t er l y, Vol. 1, No. 3, Oct ober 1963, pp. 53- 59. xxxxxxxxxxxxxxxxxxxx
