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?