# gcdx

..  gcdx(x,y)

Computes the greatest common (positive) divisor of x and y and their BÃ©zout coefficients, i.e. the integer coefficients u and v that satisfy :math:ux+vy = d = gcd(x,y).

.. doctest::

julia> gcdx(12, 42)
(6,-3,1)

.. doctest::

julia> gcdx(240, 46)
(2,-9,47)

.. note::

BÃ©zout coefficients are *not* uniquely defined. gcdx returns the minimal BÃ©zout coefficients that are computed by the extended Euclid algorithm. (Ref: D. Knuth, TAoCP, 2/e, p. 325, Algorithm X.) These coefficients u and v are minimal in the sense that :math:|u| < |\frac y d and :math:|v| < |\frac x d. Furthermore, the signs of u and v are chosen so that d is positive.

## Examples

The gcdx(x, y) function in Julia computes the greatest common (positive) divisor of x and y along with their Bézout coefficients. The Bézout coefficients u and v satisfy the equation ux + vy = d = gcd(x, y), where d is the greatest common divisor.

julia> gcdx(12, 42)
(6, -3, 1)

In this example, the greatest common divisor of 12 and 42 is 6. The Bézout coefficients are u = 6 and v = -3.

julia> gcdx(240, 46)
(2, -9, 47)

Here, the greatest common divisor of 240 and 46 is 2. The Bézout coefficients are u = 2 and v = -9.

Note: Bézout coefficients are not uniquely defined. The gcdx function returns the minimal Bézout coefficients computed by the extended Euclid algorithm (Ref: D. Knuth, TAoCP, 2/e, p. 325, Algorithm X). These coefficients u and v are minimal in the sense that |u| < |y/d| and |v| < |x/d|. Additionally, the signs of u and v are chosen such that d is positive.