For computing the GCD of two multivariate polynomials we have the Euclidian algorithm. However, it's well known that the Euclidian algorithm is not very efficient (because of intermediate expression swell). Therefore many other GCD algorithms (like the subresultant algorithm based on polynomial remainder sequences or modular algorithms) exists.

Now my question is: Is there any "efficient" algorithm for computing the extended GCD of two polynomials? (computing $t$ and $s$ such that $ta+sb = GCD(a,b)$)


1 Answer 1


Not really. Consider that, in $\mathbb{Q}[x,y]$, there are no $f(x,y),g(x,y)$ for which $f(x,y)x + g(x,y)y = 1$, although $\operatorname{gcd}(x,y) = 1$. Therefore, $\mathbb{Q}[x,y]$ is not a Bezout Domain.

See Algorithm 6.59 in the second edition of "Modern Computer Algebra", by J. von zur Gathen and J. Gerhard, Cambridge Univ. Press, 2003. That algorithm presents a case of a bi-variate extended Euclidean algorithm, but it's not quite what you want.

Groebner Bases provide a multivariate generalisation of polynomial division with remainder.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .