gcdex -- the extended Euclidean
algorithm for polynomials
Introductiongcdex(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.
Call(s)gcdex(p, q <, x>)
gcdex(f, g, x)
Parametersp, q |
- | polynomials of type
DOM_POLY |
f, g |
- | polynomial expressions |
x |
- | an indeterminate: an identifier or an indexed identifier |
Returnsa sequence of three polynomials, or a sequence of three polynomial
expressions, or FAIL.
p, q
Related
Functionsfactor, div, divide, gcd, ifactor, igcd, igcdex, ilcm, lcm, mod, poly
Detailsgcdex(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 = s*p +
t*q and degree(s, x) < degree(q, x), degree(t,
x) < degree(p, x). These data are computed by the extended
Euclidean algorithm.gcdex only processes univariate polynomials:
x is specified, the input
polynomials are regarded as univariate polynomials in
x.x must be specified if polynomial expressions
are used on input.poly for details.
FAIL is returned if an argument cannot be converted to a
polynomial.DOM_POLY are
returned."_divide". This method must return FAIL if domain elements cannot be
divided.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
1The 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))
poly(x + 1, [x]), poly(1/3, [x]), poly(- 1/3 x + 2/3, [x])
For multivariate polynomials, an indeterminate must be specified:
>> gcdex(poly(x^2*y), poly(x + y), x)
/ 1 \ / / 1 \ 1 \
poly(1, [x]), poly| --, [x] |, poly| | - -- | x + -, [x] |
| 3 | | | 2 | y |
\ y / \ \ y / /
>> gcdex(poly(x^2*y), poly(x + y), y)
/ 1 \ / 1 \
poly(1, [y]), poly| - --, [y] |, poly| -, [y] |
| 3 | \ x /
\ x /
>> gcdex(x^3 + a, x^2 + 1, x)
2
a + x 1 - x - a x
1, ------, ------------
2 2
a + 1 a + 1