Euclid-Wallis Algorithm ----------------------- This algorithm computes gcd(m,n), solves the Diophantine equation mx + ny = gcd(m,n), and yields the continued fraction for m/n. Start with the two columns 1 0 0 1 m n Above each successive column write down the floor of the quotient of the base of the previous column divided into the base of the column before that, then compute the new column by subtracting that number times the previous column from the column before that. The column preceding that with 0 at its base has gcd(m,n) at its base. Also, m times the top row plus n times the middle row equals the bottom row. Thus, the column with gcd(m,n) at its base has the coefficients for mx + ny = gcd(m,n) in the top two. Also, the column with 0 at its base has the smallest non-zero solution to mx + ny = 0. Multiples of this solution can be added to a particular solution of mx + ny = k to get all solutions. The quotients above the columns yield the continued fraction for m/n. Let us work an example; m = 17, n = 23: 0 1 2 1 5 <-- continued fraction ------------------- 1 0 1 -1 3 -4 23 <-- m times this row 0 1 0 1 -2 3 -17 <-- plus n times this row 17 23 17 6 5 1 0 <-- equals this row | | | m n gcd(m,n) Thus, gcd(17,23) = 1, (-4+23k)17 + (3-17k)23 = 1, and the continued fraction for 17/23 is [0,1,2,1,5]. It has been brought to my attention that W. A. Blankinship published the essence of this algorithm in 1963. See Blankinship Algorithm at MathWorld. Rob Johnson