This is machine translation

Translated by Microsoft



Extended Euclidean algorithm for polynomials




gcdex(p, q, <x>)
gcdex(f, g, x)


gcdex(p, q, x) regards p and q as univariate polynomials in x and returns their greatest common divisor as a linear combination of p and q.

gcdex(p, q, x) returns a sequence g, s, t with three elements, where the polynomial g is the greatest common divisor of p and q. The polynomials s and t satisfy g = sp + tq and deg(s) < deg(q), deg(t) < deg(p). These data are computed by the extended Euclidean algorithm.

gcdex only processes univariate polynomials:

  • If the indeterminate x is specified, the input polynomials are regarded as univariate polynomials in x.

  • If no indeterminate is specified, the indeterminate of the polynomials is searched for internally. An error occurs if more than one indeterminate is found.

Note that x must be specified if polynomial expressions are used on input.

Polynomial expressions are converted to polynomials. See poly for details. FAIL is returned if an argument cannot be converted to a polynomial.

The returned polynomials are polynomial expressions if the input consists of polynomial expressions. Otherwise, polynomials of type DOM_POLY are returned.

The coefficient ring of the polynomials must provide the method "_divide". This method must return FAIL if domain elements cannot be divided.

    Note:   If the coefficient domain of the polynomial is not a field, then it may not be possible to represent a greatest common divisor as a linear combination of the input polynomials. In such a case, an error is raised.


Example 1

The greatest common divisor of two univariate polynomials in extended form can be computed as follows:

gcdex(poly(x^3 + 1), poly(x^2 + 2*x + 1))

For multivariate polynomials, an indeterminate must be specified:

gcdex(poly(x^2*y), poly(x + y), x)

gcdex(poly(x^2*y), poly(x + y), y)

gcdex(x^3 + a, x^2 + 1, x)


p, q

polynomials of type DOM_POLY

f, g

polynomial expressions


An indeterminate: an identifier or an indexed identifier

Return Values

Sequence of three polynomials, or a sequence of three polynomial expressions, or FAIL.

Overloaded By

p, q

See Also

MuPAD Functions

Was this topic helpful?