Ask Your Question

symbolic polynomial euclidean algorithm

asked 2011-03-25 14:03:25 -0500

manenir gravatar image

updated 2011-04-28 09:47:40 -0500

Kelvin Li gravatar image

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


edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted

answered 2011-03-26 14:18:49 -0500

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)

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)

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.

edit flag offensive delete link more

answered 2011-03-31 23:05:43 -0500

mmarco gravatar image

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

edit flag offensive delete link more


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

cswiercz gravatar imagecswiercz ( 2011-04-01 08:30:26 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2011-03-25 14:03:25 -0500

Seen: 798 times

Last updated: Mar 31 '11