J2ee Web Hosting, Perl Scripting And Developing Blog

326 ARITHMETIC 4.5.2 The ideas underlying Euclid s algorithm can also be applied to find a general solution in integers of any set of linear equations with integer coefficients. For example, suppose that we want to find all integers w, x, y, .z that satisfy the two equations low + 3x + 3y + 8z = 1, (17) 6w -7x -52 = 2. (18) We can introduce a new variable [10/3]w + [3/31x + [3/3]y + [8/3]z = 3w + x + y + 22 = tl, and use it to eliminate y; Eq. (17) becomes (10 mod 3)w + (3 mod 3)x + 3tI + (8 mod 3) = w + 3tl + 22 = 1, (1% and Eq. (18) remains unchanged. The new equation (19) may be used to elim- inate w, and (18) becomes 6(1 -3tI -2z) -7x -52 = 2; that is, 7x + 18tl + 172 = 4. (20) Now as before we introduce a new variable x + 2t1 + 22 = t2 and eliminate x from (20): 7t2 + 4t1 + 3z = 4. (21) Another new variable can be introduced in the same fashion, in order to eliminate the variable z, which has the smallest coefficient: 2t2 + tl + z =I t3. Eliminating z from (21) yields t2 + t1 + 3t3 = 4, (22) and this equation, finally, can be used to eliminate t2. We are left with two independent variables, tl and t3; substituting back for the original variables, we obtain the general solution w= 17 -5t1 -14t3, x= 20 -5t1 -17t3, (23) y = -55 + 19t1 + 45t3, z= -8 + tl + 7t3.

4.5.2 THE GREATEST COMMON DIVISOR 325 Euclid s algorithm can be extended in another important way: We can calculate integers u and v such that uu + vu = gcd(u, v) (15) at the same time gcd(u, v) is being calculated. This extension of Euclid s algo- rithm can be described conveniently in vector notation: Algorithm X (Extended Euclid s algorithm). Given nonnegative integers u and v, this algorithm determines a vector (ul,u2, us) such that uu1 + vu2 = ug = gcd(u, v). The computation makes use of auxiliary vectors (VI, ~2, vg), (tl , t2, ts); all vectors are manipulated in such a way that the relations ut1 + vt2 = t3, uu1+ vu2 = u3, WI1 + vu2 = 213 (16) hold throughout the calculation. Xl. [Initialize.] Set (ul, u2, u3) t (l,O, u), (211, v2, v3) c (0, 1, w). X2. [Is v3 = O?] If us = 0, the algorithm terminates. X3. [Divide, subtract.] Set q +- Lu3/213J, and then set (h,t2rt3) + (ul,u2,u3)-(%,~2tv3) % (%,u2,u3) +-(%,v2,2)3), (%,v2,u3) + (h,t2,t3). Return to step X2. 1 For example, let u = 40902, v = 24140. At step X2 we have 4 u1 u2 u3 Vl 212 7J3 - 1 0 40902 0 1 24140 1 0 1 24140 1 -1 16762 1 1 -1 16762 -1 2 7378 2 -1 2 7378 3 -5 2006 3 3 -5 2006 -10 17 1360 1 -10 17 1360 13 -22 646 2 13 -22 646 -36 61 68 9 -36 61 68 337 -571 34 2 337 -571 34 -710 1203 0 The solution is therefore 337 .40902 -571 e 24140 = 34 = gcd(40902,24140). The validity of Algorithm X follows from (16) and the fact that the algorithm is identical to Algorithm A with respect to its manipulation of ug and vg; a detailed proof of Algorithm X is discussed in Section 1.2.1. Gordon H. Bradley has observed that we can avoid a good deal of the calculation in Algorithm X by suppressing us, ~2, and t2; then 212 can be determined afterwards using the relation uul + vu2 = u3. Exercise 14 shows that the values of 1~~1, 1~21, 1~1, Iv2l remain bounded by the size of the inputs u and U. Algorithm B, which computes the greatest common divisor using properties of binary notation, can be extended in a similar way; see exercise 35. For some instructive extensions to Algorithm X, see exercises 18 and 19 in Section 4.6.1.

324 ARITHMETIC 4.5.2 the greatest common divisor is taken to be zero; otherwise if only one uj is nonzero, it is the greatest common divisor; otherwise replace uk by uk mod uj for all k # j, where Uj is the minimum of the nonzero u s. The algorithm sketched in the preceding paragraph is a natural generaliza- tion of Euclid s method, and it can be justified in a similar manner. But there is a simpler method available, based on the easily verified identity gcd(w,u2,… , un) = gcd(ul, .sd(uz, . . . ,un,). (14 To calculate gcd(ur, uz, . . . , u,), we may therefore proceed as follows: Cl. Set d t u,, j +-n -1. C2. If d # 1 and j > 0, set d c gcd(uj, d) and j c j -1 and repeat this step. Otherwise d = gcd(ul, . . . , u,). This method reduces the calculation of gcd(ui, . . . , u,) to repeated calculations of the greatest common divisor of two numbers at a time. It makes use of the fact that gcd(ui, . . . , uj, 1) = 1; and this will be helpful, since we will already have gcd(u,-1, u,) = 1 over 60 percent of the time if u,-1 and u, are chosen at random. In most cases, the value of d will decrease rapidly during the first few stages of the calculation, and this will make the remainder of the computation quite fast. Here Euclid s algorithm has an advantage over Algorithm B, in that its running time is primarily governed by the value of min(u, v), while the running time for Algorithm B is primarily governed by max(u, v); it would be reasonable to perform one iteration of Euclid s algorithm, replacing u by u modv if u is much larger than V, and then to continue with Algorithm B. The assertion that gcd(u,-l, u,) will be equal to unity more than 60 percent of the time for random inputs is a consequence of the following well-known result of number theory: Theorem D (G. Lejeune Dirichlet, Abhandlungen Kbniglich PreuB. Akad. Wiss. (1849), 69-83). If u and v are integers chosen at random, the probability that gcd(u, V) = 1 is 6/.rr2 z .60793. A precise formulation of this theorem, which carefully defines what is meant by being chosen at random, appears in exercise 10 with a rigorous proof. Let us content ourselves here with a heuristic argument that shows why the theorem is plausible. If we assume, without proof, the existence of a well-defined probability p that gcd(u, w) equals unity, then we can determine the probability that gcd(u, TJ) = d for any positive integer d, because gcd(u, w) = d if and only if u is a multiple of d and v is a multiple of d and gcd(u/d, v/d) = 1. Thus the probability that gcd(u, ZJ) = d is equal to l/d times l/d times p, namely p/d2. Now let us sum these probabilities over all possible values of d; we should get 1 = c p/d2 = p(1 + ; + ; + ; + . . . ). d>l Since the sum 1 + 4 + 4 + . . . = HE) is equal to .rr2/6 (cf. Section 1.2.7), we need p = 6/n2 in order to make this equation come out right. 1

4.5.2 THE GREATEST COMMON DIVISOR 323 10 IH JXO B4 l+A To B4 with t + -v if u is odd. II B2 JAE 2B B+A B2. Initialize. 12 LDA U B t + 11. 13 B3 SRB I D B3. Halve t. 14 B4 JAE B3 1-BfD B4. Is t even? 15 B5 JAN IF c B5. Reset max(u& 16 STA U E If t > 0, set u + t. 17 SUB v E ttu-v. 18 JMP 2F E 19 IH STA V(ABS) C-E If t < 0, set 21 + -t. 20 B6 ADD U C-E B6. Subtract. .21 2H JANZ B3 c To B3 if t # 0. 22 LDA U 1 rA + u. .23 ENTX 0 rxt 0. 24 SLB 0,l rA + 2k rA. 1 The running time of this program is units, where A = k, B = 1 if t c u in step B2 (otherwise B = 0), C is the number of subtraction steps, D is the number of halvings in step B3, and E is the number of times t > 0 in step B5. Calculations discussed later in this section imply that we may take A = 4, B = 4, C = 0.71n -0.5, D = 1.41n -2.7, E = 0.35n -0.4 as average values for these quantities, assuming random inputs uandwintherange1 0, we can always write u = qv f r where 0 5 r < v and r is even; if r # 0 we set r c r/2 until r is odd, then set u t v, v t r and repeat the process. In subsequent iterations, q 2 3. Extensions. We can extend the methods used to calculate gcd(u, v) in order to solve some slightly more difficult problems. For example, assume that we want to compute the greatest common divisor of n integers ul, 2~2, . . . , u,. One way to calculate gcd(ul, 212,. . . , u,), assuming that the u s are all non- negative, is to extend Euclid s algorithm in the following way: If all uj are zero,

322 ARITHMETIC 4.5.2 As an example of Algorithm B, let us consider u = 40902, 21 = 24140, the same numbers we have used to try out Euclid s algorithm. Step Bl sets k t 1, u + 20451, IJ + 12070. Then t is set to -12070, and replaced by -6035; then v is replaced by 6035, and the computation proceeds as follows: U V t 20451 6035 +14416, +7208, +3604, +1802, +901 901 6035 -5134, -2567; 901 2567 -1666, -833; 901 833 +68, +34, +17; 17 833 -816, -408, -204, -102, -51; 17 51 -34, -17; 17 17 0. The answer is 17 . 2l = 34. A few more iterations were necessary here than we needed with Algorithm A, but each iteration was somewhat simpler since no division steps were used. A MIX program for Algorithm B requires just a little more code than for Algorithm A. In order to make such a program fairly typical of a binary computer s representation of Algorithm B, let us assume that MIX is extended to include the following operators: l SLB (shift left AX binary). C = 6; F = 6. The contents of registers A and X are shifted left M binary places; that is, lrAX/ c 12 rAXI modB O where B is the byte size. (As with all MIX shift commands, the signs of rA &nd rX are not affected.) l SRB (shift right AX binary). C = 6; F = 7. The contents of registers A and X are shifted right M binary places; that is, b-Ax c lb~lP J~ l JAE, JAO (jump A even, jump A odd). C = 40; F = 6, 7, respectively. A JMP occurs if rA is even or odd, respectively. l JXE, JXO (jump X even, jump X odd). C = 47; F = 6, 7, respectively. Analogous to JAE, JAO. Program B (Binary gcd algorithm). Assume that u and 21 are single-precision positive integers, stored respectively in locations U and V; this program uses Algorithm B to put gcd(u, v) into rA. Register assignments: t = rA, k = rI1. 01 ABS EQU 1:5 02 Bl ENTI 0 1 Bl. Find Power of 2. 03 LDX U 1 rx +- 21. 04 LDAN V 1 rA + -v. 05 JMP IF 1 06 2H SRB 1 A Halve rA, rX. 07 INCI 1 A kck+l. 08 STX U A u t u/2. 09 STA V(ABS) A v t v/2.

4.5.2 THE GREATEST COMMON DIVISOR 321 Bl. Find power of 2 B5. Reset max(u, v) Fig. 9. Binary algorithm for the greatest common divisor. A binary method. Since Euclid s patriarchal algorithm has been used for so many centuries, it is a rather surprising fact that it may not always be the best method for finding the greatest common divisor after all. A quite different gcd algorithm, which is primarily suited to binary arithmetic, was discovered by J. Stein in 1961 [see J. Comp. Phys. 1 (1967), 397-4051. This new algorithm requires no division instruction; it relies solely on the operations of(i) subtraction, (ii) testing whether a number is even or odd, and (iii) shifting the binary representation of an even number to the right (halving). The binary gcd algorithm is based on four simple facts about positive integers u and v: a) If u and u are both even, then gcd(u, w) = 2 gcd(u/2, v/2). [See Eq. (8).] b) If u is even and u is odd, then gcd(u, V) = gcd(u/2, v). [See Eq. (6).] c) As in Euclid s algorithm, gcd(u, V) = gcd(u -w, v). [See Eqs. (13), (2).] d) If u and v are both odd, then u -2) is even, and Iu -U[ < max(u, v). These facts immediately suggest the following algorithm: Algorithm B (Binary gcd algorithm). Given positive integers u and U, this algorithm finds their greatest common divisor. Bl. [Find power of 2.1 Set k +- 0, and then repeatedly set k +- k + 1, u + u/2, v t v/2, zero or more times until u and v are not both even. B2. [Initialize.] (Now the original values of u and ZI have been divided by 2 , and at least one of their present values is odd.) If u is odd, set t t --2, and go to B4. Otherwise set t t u. B3. [Halve t.] (At this point, t is even, and nonzero.) Set t + t/2. B4. [Is t even?] If t is even, go back to B3. B5. [Reset max(u, v).] If t > 0, set u t t; otherwise set 21 c -t. (The larger of u and v has been replaced by (t(, except perhaps during the first time this step is performed.) B6. [Subtract.] Set t t u–21. If t # 0, go back to B3. Otherwise the algorithm terminates with us 2 as the output. 1

320 ARITHMETIC 4.5.2 textbooks. Euclid also gave a method (Proposition 34) to find the least common multiple of two integers u and w, namely to divide u by gcd(u, V) and to multiply the result by V; this is equivalent to Eq. (10). If we avoid Euclid s bias against the numbers 0 and 1, we can reformulate Algorithm E in the following way. Algorithm A (Modern Euclidean rtlgorithm). Given nonnegative integers u and V, this algorithm finds their greatest common divisor. (Note: The greatest common divisor of arbitrary integers u and 21 may be obtained by applying this algorithm to 1~1) and 1~11, because of Eqs. (2) and (3).) Al. [w = O?] If v = 0, the algorithm terminates with ZL as the answer. A2. [Take umodv.] Set r + umodv, u + V, w t T, and return to Al. (The operations of this step decrease the value of 21, but they leave gcd(u,v) unchanged.) 1 For example, we may calculate gcd(40902,24140) as follows: gcd(40902,24140) = gcd(24140,16762) = gcd(16762,7378) = gcd(7378,2006) = gcd(2006,1360) = gcd(1360,646) = gcd(646,68) = gcd(68,34) = gcd(34,O) = 34. A proof that Algorithm A is valid follows readily from Eq. (4) and the fact that gcd(u, v) = gcd(w, u - qw), (13) if 4 is any integer. Equation (13) holds because any common divisor of u and w is a divisor of both w and u - qw, and, conversely, any common divisor of w and u - qw must divide both u and w. The following MIX program illustrates the fact that Algorithm A can easily be implemented on a computer: Program A (Euclid s dgorithm). Assume that u and w are single-precision, nonnegative integers, stored respectively in locations U and V; this program puts gcd(u, w) into rA. LDX U 1 rx t 21. JMP 2F 1 IH STX V T v + rx. SRAX5 T rAX + rA. DIV V T rX t rAXmodv. 2H LDA V 1 +T rA+ v. JXNZ 1B 1-t T Done if rX = 0. 1 The running time for this program is 19T + 6 cycles, where T is the number of divisions performed. The discussion in Section 4.5.3 shows that we may take T = 0.842766 In N + 0.06 as an approximate average value, when 21 and w are independently and uniformly distributed in the range 1 5 u, w 5 N.

45.2 THE GREATEST COMMON DIVISOR 319 Therefore no number greater than F will divide A and C, so F is their greatest common divisor. Corollary. This argument makes it evident that any number dividing two numbers divides their greatest common divisor. Q.E.D. Note. Euclid s statements have been simplified here in one nontrivial respect: Greek mathematicians did not regard unity as a divisor of another positive integer. Two positive integers were either both equal to unity, or they were relatively prime, or they had a greatest common divisor. In fact, unity was not even considered to be a number, and zero was of course nonexistent. These rather awkward conventions made it necessary for Euclid to duplicate much of his discussion, and he gave two separate propositions that are each essentially like the one appearing here. In his discussion, Euclid first suggests subtracting the smaller of the two current numbers from the larger, repeatedly, until we get two numbers where one is a multiple of the other. But in the proof he really relies on taking the remainder of one number divided by another; and since he has no simple concept of zero, he cannot speak of the remainder when one number divides the other. It is reasonable to say that he imagines each division (not the individual subtractions) as a single step of the algorithm, and hence an authentic rendition of his algorithm can be phrased as follows: Algorithm E (Original Euclidean algorithm). Given two integers A and C greater than unity, this algorithm finds their greatest common divisor. El. [A divisible by C?] If C divides A, the algorithm terminates with C as the answer. E2. [Replace A by remainder.] If A mod C is equal to unity, the given numbers were relatively prime, so the algorithm terminates. Otherwise replace the pair of values (A, C) by (C, Amod C) and return to step El. 1 The proof Euclid gave, which is quoted above, is especially interesting because it is not really a proof at all! He verifies the result of the algorithm only if step El is performed once or thrice. Surely he must have realized that step El could take place more than three times, although he made no mention of such a possibility. Not having the notion of a proof by mathematical induction, he could only give a proof for a finite number of cases. (In fact, he often proved only the case n = 3 of a theorem that he wanted to establish for general n.) Although Euclid is justly famous for the great advances he made in the art of logical deduction, techniques for giving valid proofs by induction were not discovered until many centuries later, and the crucial ideas for proving the validity of algorithms are only now becoming really clear. (See Section 1.2.1 for a complete proof of Euclid s algorithm, together with a short discussion of general proof procedures for algorithms.) It is worth noting that this algorithm for finding the greatest common divisor was chosen by Euclid to be the very first step in his development of the theory of numbers. The same order of presentation is still in use today in modern

318 ARITHMETIC 45.2 Euclid s algorithm is found in Book 7, Propositions 1 and 2 of his Elements (c. 300 B.C.), but it probably wasn t his own invention. Scholars believe that the method was known up to 200 years earlier, at least in its subtractive form, and it was almost certainly known to Eudoxus (c. 375 B.C.); cf. K. von F ritz, Ann. Math. (2) 46 (1945), 242-264. We might call it the granddaddy of all al- gorithms, because it is the oldest nontrivial algorithm that has survived to the present day. (The chief rival for this honor is perhaps the ancient Egyptian method for multiplication, which was based on doubling and adding, and which forms the basis for efficient calculation of nth powers as explained in Section 4.6.3. But the Egyptian manuscripts merely give examples that are not com- pletely systematic, and these examples were certainly not stated systematically; the Egyptian method is therefore not quite deserving of the name algorithm. Several ancient Babylonian methods, for doing such things as solving special sets of quadratic equations in two variables, are also known. Genuine algorithms are involved in this case, not just special solutions to the equations for certain input parameters; for even though the Babylonians invariably presented each method in conjunction with an example worked with particular input data, they regularly explained the general procedure in the accompanying text. [See D. E. Knuth, CACA4 15 (1972), 671-677; 19 (1976), 108.1 Many of these Babylonian algorithms predate Euclid by 1500 years, and they are the earliest known in- stances of written procedures for mathematics. But they do not have the stature of Euclid s algorithm, since they do not involve iteration and since they have been superseded by modern algebraic methods.) In view of the importance of Euclid s algorithm, for historical as well as practical reasons, let us now consider how Euclid himself treated it. Paraphrasing his words into modern terminology, this is essentially what he wrote: Proposition. Given two positive integers, find their greatest common divisor. Let A, C be the two given positive integers; it is required to find their greatest common divisor. If C divides A, then C is a common divisor of C and A, since it also divides itself. And it clearly is in fact the greatest, since no greater number than C will divide C. But if C does not divide A, then continually subtract the lesser of the numbers A, C from the greater, until some number is left that divides the previous one. This will eventually happen, for if unity is left,, it will divide the previous number. Now let E be the positive remainder of A divided by C; let F be the positive remainder of C divided by E; and let F be a divisor of E. Since F divides E and E divides C -F, F also divides C -F; but it also divides itself, so it divides C. And C divides A -E; therefore F also divides A -E. But it also divides E; therefore it divides A. Hence it is a common divisor of A and C. I now claim that it is also the greatest. For if F is not the greatest common divisor of A and C, some larger number will divide them both. Let such a number be G. Now since G divides C while C divides A-E, G divides A-E. G also divides the whole of A, so it divides the remainder E. But E divides C -F; therefore G also divides C -F. And G also divides the whole of C, so it divides the remainder F; that is, a greater number divides a smaller one. This is impossible.

4.5.2 THE GREATEST COMMON DIVISOR 317 that is a multiple of (i.e., evenly divisible by) both u and w; and lcm(O,O) = 0. The classical method for teaching children how to add fractions u/u + v/v is to train them to find the O; (9) u. w = gcd(u, w) . lcm(u, v), if u, 2) 2 0; (10) gcd(lcm(u, II), lcm(u, w)) = lcm(u, gcd(v, w)); (11) lcm(gcd(u, v), gcd(u, w)) = gcd(u, lcm(v, w)). (12) The latter two formulas are distributive laws analogous to the familiar identity uz, + uw = u(w + w). Equation (10) reduces the calculation of gcd(u, v) to the calculation of lcm(u, w), and conversely. Euclid s algorithm. Although Eq. (6) is useful for theoretical purposes, it is generally no help for calculating a greatest common divisor in practice, because it requires that we first determine the factorization of u and v. There is no known method for finding the prime factors of an integer very rapidly (see Section 4.5.4). But fortunately there is an efficient way to calculate the greatest common divisor of two integers without factoring them, and, in fact, such a method was discovered over 2250 years ago; this is Euclid s algorithm, which we have already examined in Sections 1.1 and 1.2.1.