5.1.31 extgcd

Syntax:

extgcd ( int_expression, int_expression )
extgcd ( bigint_expression, bigint_expression )
extgcd ( poly_expression, poly_expression )

Type:

list of 3 objects of the same type as the type of the arguments

Purpose:

computes extended gcd: the first element is the greatest common divisor of the two arguments, the second and third are factors such that if list L=extgcd(a,b); then L[1]=a*L[2]+b*L[3].

Note:

Polynomials must be univariate (in the same variable) to apply extgcd.

Example:

extgcd(24,10); ==> [1]: ==> 2 ==> [2]: ==> -2 ==> [3]: ==> 5 ring r=0,(x,y),lp; extgcd(x4-x6,(x2+x5)*(x2+x3)); ==> [1]: ==> x5+x4 ==> [2]: ==> 1/2x2+1/2x+1/2 ==> [3]: ==> 1/2