Math. 55 Euclid’s GCD Algorithm May 10, 1999 6:15 pmProf. W. Kahan Page 1 Given two positive integers a ≥ b > 0 we seek their Greatest Common Divisor ( GCD ), which is the biggest integer d that divides both a and b leaving no remainder. Ordinary long division computes a positive integer quotient q :=  a/b  and leaves a remainder r := a – q·b that satisfies 0 ≤ r < b . Clearly every divisor of both a and b divides r too, and conversely every divisor of both b and r divides a = q·b + r too; therefore GCD(a, b) = GCD(b, r) . But the pair (b, r) is smaller than the pair (a, b) in the sense that b ≤ a and r < b . This leads to an algorithm … Euclid’s GCD Algorithm Given integers a ≥ b > 0 , set r 0 := a and r 1 := b and perform successive long divisions getting, for j = 1, 2, 3, …, n in turn until r n+1 = 0 , quotients q j and remainders r j that satisfyr j–1 = q j ·r j + r j+1 with 0 ≤ r j+1 < r j .( Here at step j we divide r j–1 by r j to get quotient q j and remainder r j+1 , stopping when a remainder r n+1 = 0 . At that point q n > 1 ; can you see why?) The algorithm stops because this decreasing sequence of n+1 positive integers, r 0 = a ≥ r 1 = b > r 2 > … > r n–1 > r n > r n+1 = 0 , cannot have n > b . Then GCD(a, b) = r n because, as explained in the first paragraph,GCD(a, b) =: GCD(r 0 , r 1 ) = GCD(r 1 , r 2 ) = … = GCD(r n–1 , r n ) = GCD(r n , r n+1 ) = r n .The quotients q j appear to play no important role in the foregoing algorithm, but appearances can mislead. By translating the algorithm’s recurrence into matrix language we find uses for q j :Set := first; then for j = 1, 2, 3, …, n in turn confirm that = , with 0 ≤ r j+1 < r j and r n+1 = 0 , so = … . Now set row := … to obtain two integers A and B (not both positive) satisfying GCD(a, b) = r n = = = B·a + A·b . We have just found that GCD(a, b) is a linear combination of a and b with integer coefficients, thus proving the following … ( Cf. text p. 137, and p. 201 ex. 58.) Theorem 1: As A and B run independently through all integers the expression B·a + A·b runs through a set of integers among which the smallest positive integer is GCD(a, b) = B·a + A·b . Hard Exercise: Running A and B through all integers is unnecessary: Theorem 1 remains true after restrictions |A| < a and |B| ≤ b ≤ a are imposed; why? Can you prove |A| < a/GCD(a, b) and |B| ≤ b/GCD(a, b) ? See below. There are two ways to compute A and B . The easiest is to evaluate from-left-to-right the matrix product defining after all the q j ’s have been computed; this gives rise to a recurrence:s n := 1 ; s n–1 := –q n–1 ; for j = n–2, n–3, …, 2, 1 in turn s j := s j+2 – q j ·s j+1 .Finally A := s 1 and B := s 2 . Another way to compute them is to evaluate from-right-to-left the matrix product defining row simultaneously with the computation of the q j ’s :r0r1abrjrj1+011qj–rj1–rjrn0011qn–011qn1––011qn2––011q2–011q1–r0r1BA 10011qn–011qn1––011qn2––011q2–011q1–10rn0BAabBABA This document was created with FrameMaker404Math. 55 Euclid’s GCD Algorithm May 10, 1999 6:15 pmProf. W. Kahan Page 2 := ; := ; for j = 2, 3, …, n–1 in turn := .Finally := . Note that q n never figures in the computation of A and B . Whichever way be chosen to compute A, B and GCD(a, b) = B·a + A·b , the algorithm is called “the Extended Euclidean Algorithm” and has important applications. Here is one of them: Exercise: Given integers a, c and b > 0 , when does “ a·x ≡ c mod b ” have integer solutions x ? Here “ p ≡ q mod b ” is pronounced “ p is congruent to q mod b ” and means that p–q is divisible by b . Let d := GCD(a, b) . Exhibit all d noncongruent solutions x if and only if d divides c ; otherwise prove no solution x exists. Continued FractionsIf d = GCD(a, b) then (a/d)/(b/d) exhibits a/b “in lowest terms” but is not the only unique encoding of rational numbers. By substituting rj–1/rj = qj + 1/(rj/rj+1) repeatedly for j = 1, 2, …, n in turn we obtain a Terminating Continued Fraction .This is the continued fraction for the rational number a/b . Here q1 ≥ 1 because a ≥ b > 0 ; in fact every qj ≥ 1 and the last qn ≥ 2 to ensure that the encoding of each rational a/b > 1 by a finite sequence (q1, q2, q3, …, qn–1, qn–1) of positive integers be unique. Euclid’s algorithm converts a rational number given as a ratio of integers into its continued fraction; how do we get back? The obvious way evaluates the continued fraction “bottom-up” : Rn+1 := 0 ; Rn := 1 ; for j = n, n–1, n–2, …, 2, 1 in turn Rj–1 := qj·Rj + Rj+1 ; finally a/b = R0/R1 in lowest terms.Exercise: Confirm that every integer Rj = rj/GCD(a, b) .Translating the bottom-up evaluation of the continued fraction into matrix terms yields first = , then = … . This last expression offers two interesting opportunities. One is a way to evaluate the continued fraction “top-down” ::= ; := ; for j = 2, 3, …, n in turn := ; finally := .This top-down evaluation turns out to be a good way to evaluate endless continued fractions that encode non-rational numbers; successive ratios hj/gj can be shown to converge alternatingly.Exercise: The endless continued fraction in which every qj = 1 represents µ := (1 + √5)/2 ; can you see why?Another opportunity offered by that long matrix product is a clear proof of Lamé’s Theorem : To compute d = GCD(a, b) for a ≥ b > 0 Euclid’s algorithm needs n ≤ 1+ln(b/d)/ln(µ) divisions.Exercise: Prove it by showing every Rj is at least as