igcdex -- the extended Euclidean
algorithm for two integers
Introductionigcdex(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)
Parametersx, y |
- | arithmetical expressions representing integers |
Returnsa sequence of three integers, or a
symbolic igcdex call.
Related
Functionsdiv, divide, factor, gcd, gcdex, ifactor, igcd, ilcm, lcm, mod, numlib::igcdmult
Detailsigcdex(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|.
igcdex returns an error
message. If some argument is not a number,
then igcdex returns a symbolic igcdex
call.numlib::igcdmult is an extension of
igcdex for more than two arguments.igcdex is a function of the system kernel.
Example
1We 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)