Affordable web hosting - 326 ARITHMETIC 4.5.2 The ideas underlying Euclid s algorithm
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.