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.
See Also
User Contributed Notes
Add a Note
The format of note supported is markdown, use triple backtick to start and end a code block.