Blankinship Algorithm

A method for finding solutions  and  to a linear congruence

by constructing a matrix formed by adjoining a vector containing  and  with a unit matrix,

and applying the Euclidean algorithm to the first column, while extending the operations to all rows. The algorithm terminates when the first column contains the greatest common divisor .

REFERENCES:

Blankinship, W. A. "A New Version of the Euclidean Algorithm." Amer. Math. Monthly 70, 742-745, 1963.

Séroul, R. "The Blankinship Algorithm." §8.2 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 161-163, 2000.