5.1.28 extgcd

Syntax:

extgcd ( int_expression, int_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 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]: → 2x5+2x4 → [2]: → x2+x+1 → [3]: → 1

See gcd; int; poly.