Extended Euclidean Algorithm
The extended Euclidean algorithm computes the greatest common divisor and solves Bezout's identity.
extGCD(a, b)
a, b |
integer scalars |
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.
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.
There is also a shorter, more elegant recursive version for the extended Euclidean algorithm. For R the procedure suggested by Blankinship appeared more appropriate.
Blankinship, W. A. “A New Version of the Euclidean Algorithm." Amer. Math. Monthly 70, 742-745, 1963.
extGCD(12, 10) extGCD(46368, 75025) # Fibonacci numbers are relatively prime to each other
Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.