The extended Euclidean algorithm computes the greatest common divisor and
solves Bezout's identity.
Usage
extGCD(a, b)
Arguments
a, b
integer scalars
Value
a numeric vector of length three, c(d, n, m), where d is the
greatest common divisor of a and b, and n and m
are integers such that d = n*a + m*b.
Details
The extended Euclidean algorithm not only computes the greatest common
divisor $d$ of $a$ and $b$, but also two numbers $n$ and
$m$ such that $d = n a + m b$.
This algorithm provides an easy approach to computing the modular inverse.
References
Blankinship, W. A. ``A New Version of the Euclidean Algorithm."
Amer. Math. Monthly 70, 742-745, 1963.