extGCD: Extended Euclidean Algorithm

In numbers: Number-Theoretic Functions

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

GCD

Examples

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

numbers documentation built on Nov. 23, 2022, 9:06 a.m.