Extended Euclidean Algorithm
- Natural & Formal Sciences -
Mathematics & Logic Dictionary
Definition
A variant of the Euclidean algorithm that, given two integers a and b, computes their greatest common divisor g and also returns integers x and y such that ax + by = g (Bezout coefficients).
Extended Euclidean Algorithm
- Mathematics & Logic -
Pure Mathematics Dictionary
Definition
An algorithm that computes the greatest common divisor (gcd) of two integers and, simultaneously, integer coefficients u and v such that u·a + v·b = gcd(a,b). It is the Euclidean algorithm augmented to return the Bézout coefficients.