Extension of Euclid's Algorithm
We already know that, for any two whole numbers a and b, there exist integers s and t such that
Write the two linear combinations in a column and apply one step of Euclid's algorithm to the left-hand side. Assuming
a = 1·a + 0·b
b = 0·a + 1·b
r = 1·a + (-p)·b
Apply the same procedure to the last two equations. Continue in this manner until Euclid's algorithm on the left stops. On the right, there will be the linear combination we are after. Let check this with an example: let a = 2322, b = 654. I adopt the usual convention of solving linear equations and omit all the terms in a linear combination but the left-hand side and the two coefficients on the right. The results are placed into a table with the fourth column being equal to p (from a = bp + r, which changes on each step. Multiply three numbers to the left of p by p and subtract them from the numbers directly above them. Record the results on the next line.)
Therefore, 20·2322 - 71·654 = 6. Note that 20 and 71 are coprime. This is the case for any s ant t such that
The algorithm, as described above, is a real extension of Euclid's algorithm in the sense that without removing any of the operations needed for the latter it only adds 2 multiplications and 2 subtractions on every step. Furthermore, these operations in no way affect the progress of Euclid's algorithm proper. Which proves that the extended algorithm terminates together with the common algorithm. However, the extension is by far more reliable.
Indeed, assume the extended algorithm has furnished s,t, and g such that as + bt = g. We can easily check whether or not g|a and g|b. Unless there was an error, this would imply g|gcd(a,b). Moreover, once g is expressed as a linear combination of a and b we know that
- A.Engel, Exploring Mathematics with Your Computer, MAA, 1993
- H.Davenport, The Higher Arithmetic, Harper&Brothers, NY
- R.Graham, D.Knuth, O.Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
- D.Knuth, The Art of Computer Programming, v1, 2.
Copyright © 1966-2016 Alexander Bogomolny