The extended Euclidean algorithm computes the greatest common divisor and
solves Bezout's identity.
Usage
extGCD(a, b)
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.
Arguments
a, b
integer scalars
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.