## `gcd` -- the greatest common divisor of polynomials

#### Introduction

`gcd``(p, q...)` returns the greatest common divisor of the polynomials p, q, ...

#### Call(s)

`gcd(p, q...)`
`gcd(f, g...)`

#### Parameters

`p, q...` | - | polynomials of type `DOM_POLY`
`f, g...` | - | polynomial expressions

#### Returns

a polynomial, a polynomial expression, or the value `FAIL`.

### Overloadable:

`p`, `q`, `f`, `g`

#### Related Functions

`content`, `div`, `divide`, `factor`, `gcdex`, `icontent`, `ifactor`, `igcd`, `igcdex`, `ilcm`, `lcm`, `mod`, `poly`

#### Details

- `gcd(`p, q...`)` calculates the greatest common divisor of any number of polynomials. The coefficient ring of the polynomials may either be the integers or the rational numbers, Expr, a residue class ring IntMod`(n)` with a prime number `n`, or a domain.

  All polynomials must have the same indeterminates and the same coefficient ring.

- Polynomial expressions are converted to polynomials. See `poly` for details. `FAIL` is returned if an argument cannot be converted to a polynomial.
- The return value is of the same type as the input polynomials, i.e., either a polynomial of type `DOM_POLY` or a polynomial expression.
- `gcd` returns 0 if all arguments are 0, or if no argument is given. If at least one of the arguments is -1 or 1, then `gcd` returns 1.
- Use `igcd` if all arguments are known to be integers, since it is much faster than `gcd`.

#### Example 1

The greatest common divisor of two polynomial expressions can be computed as follows:

    >> gcd(6*x^3 + 9*x^2*y^2, 2*x + 2*x*y + 3*y^2 + 3*y^3)

                                             2
                                    2 x + 3 y

    >> f := (x - sqrt(2))*(x^2 + sqrt(3)*x-1):
       g := (x - sqrt(2))*(x - sqrt(3)):
       gcd(f, g)

                                          1/2
                                     x - 2

One may also choose polynomials as arguments:

    >> p := poly(2*x^2 - 4*x*y - 2*x + 4*y, [x, y], IntMod(17)):
       q := poly(x^2*y - 2*x*y^2, [x, y], IntMod(17)):
       gcd(p, q)

                         poly(x - 2 y, [x, y], IntMod(17))

    >> delete f, g, p, q:

#### Background

- If the arguments are polynomials with coefficients from a domain, then the domain must have the methods `"gcd"` and `"_divide"`. The method `"gcd"` must return the greatest common divisor of any number of domain elements. The method `"_divide"` must divide two domain elements. If domain elements cannot be divided, this method must return `FAIL`.

#### Changes

- Arbitrary expressions are now accepted as coefficients.

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