Euclidean Algorithm for GCD of polynomials

Question

I am struggling to use the Euclidean algorithm for polynomials.

Given something like $$GCD(x^5+1, x^3+1)$$

I can easily use it as follows:

$$x^5+1 = x^2(x^3+1) -x^2 +1 \\ x^3+1 = -x(-x^2+1) + x +1 \\ -x^2+1 = (x+1)(-x+1)$$

GCD = x+1

But for something like $$GCD(2x^2+6x+3, 2x+1)$$

I cannot figure out how to do it using the same method. I start like this:

$$2x^2+6x+3 = x(2x+1) + 5x+3\\ 2x+1 = \frac{2}{5}(5x+3) - \frac{1}{5}\\$$

and I am not sure how to continue. Any help would be appreciated, sorry for my poor attempt at using LaTeX.

Answer 1

You can observe that if you divide any polynomial then degree of remainder is less than that of divisor . If you divide $2x^2+6x+3$ by 2x+1 the remainder is 13/2 and they also don't have any common constants . So the GCD will be 1.

Answer 2

As $(a,b)=(a+n\cdot b,b),$ where $n$ is any integer

$$(2x^2+6x+3,2x+1=((2x+1)x+5x+3,2x+1)=(5x+3,2x+1)$$

Now, $2(5x+3)-5(2x+1)=1\implies(5x+3,2x+1)=1$

Answer 3

A "complete" explanation in response to your question requires using words like content and primitive part. The wikipedia article on polynomial greatest common divisor would help. If you conclude using your divisions that the final non-zero remainder is $1/5$, over the field of rationals, then the primitive part of this is $1$, which you want.

Knuth's Art of Computer Programming Vol. 2 section 6.2 is still a good discussion. You might also learn that the notion of division with remainder is generally extended, for purposes of polynomial GCD, to pseudo-division. This removes the need for doing calculations with rational numbers. Then for polynomials $f,g$:

$$\gcd(f,g)=\gcd(\text{content}(f),\text{content}(g))\cdot\gcd(\text{primpart}(f),\text{primpart}(g)).$$

Given your particular question, assuming that you want your GCD to correspond to the usual notion, namely as a polynomial in $x$ with integer coefficients, you would return the primitive part of $1/5$, (indeed the primitive part of any constant), namely $1$.