This is machine translation

Translated by Microsoft
Mouse over text to see original. Click the button below to return to the English verison of the page.


Extended Euclidean algorithm for polynomials

MuPAD® notebooks are not recommended. Use MATLAB® live scripts instead.

MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.


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?