numbers (version 0.7-5)

extGCD: 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

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.

See Also

GCD

Examples

# NOT RUN {
extGCD(12, 10)
extGCD(46368, 75025)  # Fibonacci numbers are relatively prime to each other
# }