blankinship algorithm

Input interpretation

Blankinship algorithm

Definition

A method for finding solutions u and v to a linear congruence a u + b v = d by constructing a matrix formed by adjoining a vector containing a and b with a unit matrix, M = [a | 1 | 0 b | 0 | 1], 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 GCD(a, b).
More information »

Related terms

Euclidean algorithm | greatest common divisor
POWERED BY THE WOLFRAM LANGUAGE