This is machine translation

Translated by Microsoft
Mouse over text to see original. Click the button below to return to the English verison of the page.


Extended Euclidean algorithm for two integers

MuPAD® notebooks are not recommended. Use MATLAB® live scripts instead.

MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.


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?