extGCD {numbers} | R Documentation |
Extended Euclidean Algorithm
Description
The extended Euclidean algorithm computes the greatest common divisor and solves Bezout's identity.
Usage
extGCD(a, 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.
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
.
Note
There is also a shorter, more elegant recursive version for the extended Euclidean algorithm. For R the procedure suggested by Blankinship appeared more appropriate.
References
Blankinship, W. A. “A New Version of the Euclidean Algorithm." Amer. Math. Monthly 70, 742-745, 1963.
See Also
Examples
extGCD(12, 10)
extGCD(46368, 75025) # Fibonacci numbers are relatively prime to each other