Web hosting comparison - 4.5.2 THE GREATEST COMMON DIVISOR 327 In other
4.5.2 THE GREATEST COMMON DIVISOR 327 In other words, all integer solutions (w, Z, y, Z) to the original equations (li ), (18) are obtained from (23) by letting ti and t3 independently run through all integers. The general method that has just been illustrated is based on the following procedure: Find a nonzero coefficient c of smallest absolute value in the system of equations. Suppose that this coefficient appears in an equation having the form cx,, + cl51 + + Ckxk = d; (24 assume for simplicity that c > 0. If c = 1, use this equation to eliminate the variable x0 from the other equations remaining in the system; then repeat the procedure on the remaining equations. (If no more equations remain, the computation stops, and a general solution in terms of the variables not yet eliminated has essentially been obtained.) If c > 1, then if cl mod c = . . . = ck mod c = 0 check that d mod c = 0, otherwise there is no integer solution; then divide both sides of (24) by c and eliminate x0 as in the case c = 1. Finally, if c > 1 and not all of cimodc, . . . . ck mod c are zero, then introduce a new variable lc/cjxO + Lcl/cjxl + + Lck/cjxk = t; (25) eliminate the variable x0 from the other equations, in favor of t, and replace the original equation (24) by ct + (cl mod c)5i + . . . + (ck mod c)rk = d. (2 4 (Cf. (19) and (21) in the above example.) This process must terminate, since each step reduces either the number of equations or the size of the smallest nonzero coefficient in the system. A study of the above procedure will reveal its intimate connection with Euclid s algorithm. The method is a comparatively simple means of solving linear equations when the variables are required to take on integer values only. It isn t the best available method for this problem, however; substantial refinements are possible, but beyond the scope of this book. High-precision calculation. If u and v are very large integers, requiring a multiple- precision representation, the binary method (Algorithm B) is a simple and fairly efficient means of calculating their greatest common divisor, since it involves only subtractions and shifting. By contrast, Euclid s algorithm seems much less attractive, since step A2 requires a multiple-precision division of u by v. But this difficulty is not really as bad as it seems, since we will prove in Section 4.5.3 that the quotient Lu/vJ is almost always very small; for example, assuming random inputs, the quotient l~/vj will be less th an 1000 approximately 99.856 percent of the time. Therefore it is almost always possible to find lu/vJ and (U modv) using single-precision calculations, together with the comparatively simple operation of calculating u -gv where q is a single-precision number. Furthermore, if it does turn out that u is much larger than 2, (e.g., the initial input data might have this form),