# symbolic polynomial euclidean algorithm

Hi there!

Suppose we have polynomials $f(x),g(x)$ with coefficients in $\mathbb{Q}(a,b)$ for example $f(x)=ax^2, g(x)=x^2-b.$ How can we find polynomials $f_1(x),g_2(x) \in \mathbb{Q}(a,b)[x]$ such that $f(x)f_1(x)+g(x)g_1(x)=g.c.d.(f(x),g(x))$?

Thanks

edit retag close merge delete

Sort by » oldest newest most voted

Here's a simple example over $\mathbb{Q}$ with $f(x) = x^3+1$ and $g(x) = x^2-1$. First, define a polynomial ring over $\mathbb{Q}$:

sage: R.<x> = PolynomialRing(QQ,'x')
sage: f = x^3+1; g = x^2-1
sage: f.gcd(g)
x+1


One can also do this with extension fields. (By the way, there's probably a faster way to do the following.) First, let's construct $\mathbb{Q}(\sqrt{2},\sqrt{3})$ using the ring R constructed above

sage: p = x^2-2        # using the x defined above
sage: q = x^2-3
sage: K.<a,b> = QQ.extension([p,q])
sage: print a^2, b^2   # testing variable assignment
2  3


Now create a polynomial ring over K, define some elements, and compute their GCD:

sage: S.<x> = PolynomialRing(K,'x')
sage: f = a*x^2 * (x-1); g = a*x^2 * (x-b)
sage: f.gcd(g)
x^2


Hrm, it seems like there's either a bit of a bug, here, or I constructed something incorrectly. (The result should be $\sqrt{2}x^2$.) I'll submit this as a bug report. However, it seems like you'll at least get a common factor "modulo" the elements used to create the extension field.

sage: f/x^2
a*x - a
sage: g/x^2
a*x - b*a


So perhaps by inspection you can compute the GCD. Hopefully this will be resolved soon.

more

The answer $x^2$ is correct. The number $\sqrt{2}$ is a unit in K.

more

D'oh. It's been too long since my last encounter with algebra, I suppose.

( 2011-04-01 08:30:26 -0600 )edit