## `igcdex` -- the extended Euclidean algorithm for two integers

#### Introduction

`igcdex(`x, y`)` computes the nonnegative greatest common divisor `g` of the integers `x` and `y` and integers `s` and `t` such that g = s*x + t*y.

#### Call(s)

`igcdex(x, y)`

#### Parameters

`x, y` | - | arithmetical expressions representing integers

#### Returns

a sequence of three integers, or a symbolic `igcdex` call.

#### Related Functions

`div`, `divide`, `factor`, `gcd`, `gcdex`, `ifactor`, `igcd`, `ilcm`, `lcm`, `mod`, `numlib::igcdmult`

#### Details

- `igcdex(`x, y`)` returns an expression sequence `g, s, t` with three elements, where `g` is the nonnegative greatest common divisor of `x` and `y` and `s`, `t` are integers such that g=sx+ty. These data are computed by the extended Euclidean algorithm for integers.

  `igcdex(`0, 0`)` returns the sequence `0, 1, 0`. If `x` is nonzero, then `igcdex(`0, x`)` and `igcdex(`x, 0`)` return `abs(x), 0, sign(x)` and `abs(x), sign(x), 0`, respectively.

  If both `x` and `y` are nonzero integers, then the numbers `s,t` satisfy the inequalities |s| < |y/g| and |t| < |x/g|.

- If one of the arguments is a number but not an integer, then `igcdex` returns an error message. If some argument is not a number, then `igcdex` returns a symbolic `igcdex` call.
- The function `numlib::igcdmult` is an extension of `igcdex` for more than two arguments.

- `igcdex` is a function of the system kernel.

#### Example 1

We compute the greatest common divisor of some integers:

    >> igcdex(-10, 6)

                                      2, 1, 2

    >> igcdex(3839882200, 654365735423132432848652680)

                         109710920, -681651885490791809, 4

The returned numbers satisfy the described equation:

    >> [g, s, t] := [igcdex(9, 15)];
       g = s*9 + t*15

                                    [3, 2, -1]

                                       3 = 3

If one argument is not a number, the result is the a symbolic `igcdex` call:

    >> delete x:
       igcdex(4, x)

                                   igcdex(4, x)

#### Changes

- no changes

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