pracma (version 0.2-2)

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

modinv

Examples

gcd(12, 10)
gcd(46368, 75025)  # Fibonacci numbers are relatively prime to each other
lcm(12, 10)
lcm(46368, 75025)  # = 46368 * 75025