gcdext(A,B)
gcdext(A,B,X)
gcdext(A,B,X,P)

The gcdext command computes the greatest common divisor of A and B, which can be integers or polynomials. It returns a vector containing [G,S,T] where G = A*S + B*T. For polynomials the variable X must be given and an optional fourth argument runs the algorithm modulo P.

Examples

# integers
gcdext(10,15);
	[5, -1, 1]

# polynomials
gcdext(x^2-1,x^3-1,x);
	[x-1, -x, 1]

# polynomials mod p
gcdext(x^2-1,x^3-1,x,11);
	[x+10, 10*x, 1]

Algorithm

References