This is machine translation

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

Note: This page has been translated by MathWorks. Please click here
To view all translated materals including this page, select Japan from the country navigator on the bottom of this 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?