BACKWARDS EUCLIDEAN ALGORITHM Philosophy and Motivation behind B.E.A. --------------------------------------- One can turn the Euclidean Algorithm backwards as a technique to find an answer to the following problem: Find integers x and y such that 175x + 77y = 7. We call this "expressing 7 as a _linear_combination_ of 175 and 77". For example, 11 = 3 x 5 + (-2) x 2 - - expresses 11 as a linear combination of 5 and 2. How do we express 7 as a linear combination of 175 and 77? Well, we take advantage of the fact that we already have a decreasing sequence of numbers 175, 77, 21, 14, 7, such that each of 21, 14, and 7 can be expressed as linear combinations of larger numbers in that sequence. That is, we could take our above collection of Euclidean algorithm equations and subtract the "something x something" term from both sides to obtain 1) 175 = 2 x 77 + 21 ====> 21 = 175 - 2 x 77 -- == == -- 2) 77 = 3 x 21 + 14 ====> 14 = 77 - 3 x 21 -- == == -- 3) 21 = 1 x 14 + 7 ====> 7 = 21 - 1 x 14 -- = = -- Reading from down to up, this expresses 7 as a linear combination of 14 and 21, 14 as a linear combination of 21 and 77, and 21 as a linear combination of 77 and 175. We can therefore bootstrap our way up, reexpressing each remainder as a linear combination of larger guys until our expression of 7 as a linear combination of 14 and 21 becomes an expression of 7 as a linear combination of 77 and 175. ----------------------------------------------------------------- Nuts and Bolts: Carrying out the B.E.A Step by Step --------------------------------------------------- Find x, y such that 175x + 77y = 7. 1. Do Euclidean Algorithm Forwards. 2. Flip each of these equations: In each of these equations, subtract the product term from the number on the left-hand-side and set it equal remainder on the right-hand-side, like this.... a) 175 = 2 x 77 + 21 ====> 21 = 175 - 2 x 77 --- -- == == --- -- b) 77 = 3 x 21 + 14 ====> 14 = 77 - 3 x 21 -- -- == == -- -- c) 21 = 1 x 14 + 7 ====> 7 = 21 - 1 x 14 -- -- = = -- -- 14 = 2 x 7 + 0 -- - 3. Backwards: Write down the _last_ flipped equation, the one with the gcd in it, and then alternate between subbing for the smallest underlined term and collecting terms. Start with eq. (c) 7 = 21 - 1 x 14 -- -- Plug in (b) for 14. 7 = 21 - 1 x (77 - 3x21) -- -- -- Collect terms: 7 = -1 x 77 + 4 x 21 -- -- Plug in (a) for 21. 7 = -1 x 77 + 4 x (175 - 2 x 77) -- --- -- Collect terms: 7 = 4 x 175 + -9 x 77 --- -- STOP! You're done! We now have 175x + 77y = 7, with x = 4, y = -9.