ExtendedGCD Command

CAS Syntax

ExtendedGCD( <Integer>,<Integer> ): Returns a list containing the integer coefficients $s, t$ of Bézout’s identity $as+bt= GCD(a,b)$ and the greatest common divisor of the given integers $a$ and $b$ . Results are calculated by applying the Extended Euclidean algorithm.

ExtendedGCD(240,46) yields { $-9,47,2$ }. (Plugging the result into the Bézout’s identity we have: $-9 \cdot 240+47 \cdot 46=2$ ).

ExtendedGCD( <Polynomial>, <Polynomial> ): Returns a list containing the polynomial coefficients $S(x), T(x)$ of Bézout’s identity for polynomials $A(x)S(x) + B(x)T(x) = GCD(A(x), B(x))$ and the greatest common divisor of the given polynomials $A(x)$ and $B(x)$ . Results are calculated by applying the Extended Euclidean algorithm.

ExtendedGCD(x^2-1,x+4) yields { $1,-x+4,15$ }. (Plugging the result into the Bézout’s identity for polynomials we have: $1 \cdot (x^2-1) + (-x+4) \cdot (x+4) = 15$ ).

The GCD of two polynomials is not unique (it’s unique up to a scalar multiple).
See also GCD Command.