To find gcd(420, 66) using the binary GCD algorithm takes the following steps (compare with Example 27). You can do these steps in your head! 420 66 Fact 1 Save the 2 factor to multiply at the end 210 33 Fact 2 105 33 Fact 3 36 33 Fact 2 18 33 Fact 2 9 33 Fact 3 [Because gcd(a, b) = gcd(b, a), it doesnt matter whether the larger number is first or second or whether the even number is first or second.] 9 12 Fact 2 9 6 Fact 2 9 3 Fact 3 3 3 Fact 3 0 3 One number is now 0, so the other number is a factor in the gcd, therefore gcd(420, 66) = 2*3 = 6 (the factor of 2 comes from the very first step).

Math 1432 Section 15738 MWF 10-11am SEC 100 Dr. Melahat Almus almus@math.uh.edu http://www.math.uh.edu/~almus COURSE WEBSITE: http://www.math.uh.edu/~almus/1432_fall16.html and www.casa.uh.edu Visit CASA regularly for announcements and course material! Read the...