# Efficient Extended GCD Algorithm for Polynomials

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)$)

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.