igcdex
-- the extended Euclidean
algorithm for two integersigcdex(
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.
igcdex(x, y)
x, y |
- | arithmetical expressions representing integers |
a sequence of three integers, or a
symbolic igcdex
call.
div
, divide
, factor
, gcd
, gcdex
, ifactor
, igcd
, ilcm
, lcm
, mod
, numlib::igcdmult
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 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.We 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)