A method for finding solutions u and v to a linear congruence

by constructing a matrix formed by adjoining a vector containing a and b 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
.
Euclidean Algorithm, Greatest Common Divisor
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.
Eric W. Weisstein. "Blankinship Algorithm."
From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/BlankinshipAlgorithm.html

![]() |
|||
![]() |
![]() |
© 1999-2005 Wolfram Research, Inc.