Documentation Center

  • Trial Software
  • Product Updates


Extended Euclidean algorithm for two integers

Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.


igcdex(x, y)


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

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 non-zero, 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 non-zero integers, then the numbers s,t satisfy the inequalities and .

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.


Example 1

We compute the greatest common divisor of some integers:

igcdex(-10, 6)

igcdex(3839882200, 654365735423132432848652680)

The returned numbers satisfy the described equation:

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

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

delete x:
igcdex(4, x)


x, y

arithmetical expressions representing integers

Return Values

Sequence of three integers, or a symbolic igcdex call.

See Also

MuPAD Functions

Was this topic helpful?