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 as + bt = gcd(a,b). In other words, gcd(a,b) is a linear combination of a and b. gcd(a,b) is the least positive combination of the two integers. a and b themselves are expressed as trivial combinations: a = 1·a + 0·b and b = 0·a + 1·b. Starting with these two, an extension of Euclid's algorithm finds s and t whose existence was so far only established in a formal way.

Write the two linear combinations in a column and apply one step of Euclid's algorithm to the left-hand side. Assuming a = bp + r. Multiply the second equation by p and subtract it from the first equation:

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 as + bt = gcd(a,b) because, otherwise, we would be able to divide the whole equation by their common factor. The right side, gcd(a,b), would also be divided by that number which would give a positive linear combination of a and b smaller than gcd(a,b). But we know that this is impossible. Division by gcd(a,b), in our case, leads to 20·387 - 71·109 = 1. Wherefrom, 71/387 and 20/109 are consecutive fractions in the Farey series of order 387.

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 gcd(a,b)|g. Therefore, indeed g = gcd(a,b). It thus appears that by finding s and t the algorithm actually proves its own correctness. A nice feature for an algorithm to have.

References

1. A.Engel, Exploring Mathematics with Your Computer, MAA, 1993
2. H.Davenport, The Higher Arithmetic, Harper&Brothers, NY
3. R.Graham, D.Knuth, O.Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
4. D.Knuth, The Art of Computer Programming, v1, 2.

On Internet

1. Applet for Euclid's Algorithm (Extended)

• Modular Arithmetic
  • Differences and Similarities
  • Solutions to some problems
• Chinese Remainder Theorem
• Euclid's Algorithm
  • Euclid's Game
  • Binary Euclid's Algorithm
  • gcd and the Fundamental Theorem of Arithmetic
  • Extension of Euclid's Algorithm
  • Stern-Brocot Tree
    • Fine features
    • Binary Encoding
    • Binary Encoding, a Second Interpretation
    • Continued Fractions on the Stern-Brocot Tree
    • Fractions on a Binary Tree
  • Farey series
    • Farey series, a story
• Pick's Theorem
  • Pick's Theorem, A Proof
  • Farey Series
  • Pick's Theorem Applies to the Farey Series
  • Stern-Brocot Tree
• Fermat's Little Theorem
• Wilson's Theorem
• Euler's Function
• Divisibility Criteria
  • Further examles of divisibility criteria
• Examples
• Equivalence relations
• A real life story

Copyright © 1996-2010 Alexander Bogomolny