## `gcdex` -- the extended Euclidean algorithm for polynomials

#### Introduction

`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`.

#### Call(s)

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

#### Parameters

`p, q` | - | polynomials of type `DOM_POLY`
`f, g` | - | polynomial expressions
`x` | - | an indeterminate: an identifier or an indexed identifier

#### Returns

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

### Overloadable:

`p`, `q`

#### Related Functions

`factor`, `div`, `divide`, `gcd`, `ifactor`, `igcd`, `igcdex`, `ilcm`, `lcm`, `mod`, `poly`

#### Details

- `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 = 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:
  - 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.

- 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))

            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

#### Changes

- no changes

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000