# GCD of two polynomials without Euclidean algorithm

The book gives this example of greatest common divisor:

The quadratic polynomials $2x^{2}+7x+3$ and $6x^{2}+x-1$ in $\mathbb{Q}[x]$ have GCD $x+\frac{1}{2}$ since $$2x^{2}+7x+3=(2x+1)(x+3)=2\left(x+\frac{1}{2}\right)(x+3),\\6x^{2}+x-1=(2x+1)(3x-1)=2\left(x+\frac{1}{2}\right)(3x-1).$$

I understand that $2x+1$ is a common divisor, and we divide out $2$ to make it monic. I understand that $\left(x+\frac{1}{2}\right)$ is a common divisor because you can multiply it to the polynomials $2(x+3)$ and $2(3x-1)$ to get the two original polynomials.

My questions are:

1) How did they know $\left(x+\frac{1}{2}\right)$ would be divisible by all the other common divisors? I started by saying let $p(x)$ be another common divisor. But I don't know why $p(x)$ would have to divide $\left(x+\frac{1}{2}\right)$.

2) These two polynomials were easy to factor by hand. What if we had polynomials that weren't so easy to factor? How would you find a common divisor to start with?

(Note: I am self-learning. This is from the book Groups, Rings, and Fields by Wallace. I say "without Euclidean algorithm" because I tried looking up stuff about this but got answers saying use the Euclidean algorithm which is covered in the next section of the book.)

• I think you have what you need. Polynomials have unique factorization over most of the common rings (UFD's). If the degree of the polynomials is small and you know how to factor them, find the the appropriate factorizations and take the common factors. If you have something to difficult to factor by hand, then the Euclidean algorithm, to be covered in the next chapter, will be a tool. – Doug M Jul 18 '17 at 20:00
• i.e. $\,c\mid f,g\iff c\mid (f,g) =: d.\ \$ All the linear factors are (nonassociate primes, so it is clear the that only prime common factor is $\,x+1/2\ \$ – Bill Dubuque Jul 18 '17 at 21:37
• Oh okay, I didn't know that. Thank you very much. – anonanon444 Jul 19 '17 at 12:30

1) by definition, the GCD includes all common factors. If the factorizations of the polynomials in first degree binomials are available, it is trivial to find it.

2) if you may not use Euclid, then there are special methods for the factorization of certain polynomials (f.i. https://en.wikipedia.org/wiki/Factorization_of_polynomials#Factoring_univariate_polynomials_over_the_integers). But in the general case, polynomial factorization can only be achieved numerically with root finders.

The wonderful thing with Euclid is that it doesn't require any factorization to deliver the GCD.

Learn the Euclidean algorithm for polynomials. If you can do that fairly well, you will be ahead of the game. It is necessary to allow rational coefficients, not just integers.

$$\left( 2 x^{2} + 7 x + 3 \right)$$

$$\left( 6 x^{2} + x - 1 \right)$$

$$\left( 2 x^{2} + 7 x + 3 \right) = \left( 6 x^{2} + x - 1 \right) \cdot \color{magenta}{ \left( \frac{ 1}{3 } \right) } + \left( \frac{ 20 x + 10 }{ 3 } \right)$$ $$\left( 6 x^{2} + x - 1 \right) = \left( \frac{ 20 x + 10 }{ 3 } \right) \cdot \color{magenta}{ \left( \frac{ 9 x - 3 }{ 10 } \right) } + \left( 0 \right)$$ $$\frac{ 0}{1}$$ $$\frac{ 1}{0}$$ $$\color{magenta}{ \left( \frac{ 1}{3 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ 1}{3 } \right) }{ \left( 1 \right) }$$ $$\color{magenta}{ \left( \frac{ 9 x - 3 }{ 10 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ 3 x + 9 }{ 10 } \right) }{ \left( \frac{ 9 x - 3 }{ 10 } \right) }$$ $$\left( x + 3 \right) \left( \frac{ 3}{10 } \right) - \left( 3 x - 1 \right) \left( \frac{ 1}{10 } \right) = \left( 1 \right)$$ $$\left( 2 x^{2} + 7 x + 3 \right) = \left( x + 3 \right) \cdot \color{magenta}{ \left( 2 x + 1 \right) } + \left( 0 \right)$$ $$\left( 6 x^{2} + x - 1 \right) = \left( 3 x - 1 \right) \cdot \color{magenta}{ \left( 2 x + 1 \right) } + \left( 0 \right)$$ $$\mbox{GCD} = \color{magenta}{ \left( 2 x + 1 \right) }$$ $$\left( 2 x^{2} + 7 x + 3 \right) \left( \frac{ 3}{10 } \right) - \left( 6 x^{2} + x - 1 \right) \left( \frac{ 1}{10 } \right) = \left( 2 x + 1 \right)$$

• Thanks for the help! – anonanon444 Jul 19 '17 at 12:31

You don't need to worry about "monic" polynomials until the end. In fact, you can use any (non zero) rational multiple of the polynomials that are convenient.

$$\color{red}{(6x^2 + x - 1)} = 3\color{red}{(2x^2 + 7x + 3)} - \color{red}{(20x + 10)}$$

$$\color{red}{(6x^2 + x - 1)} = 3\color{red}{(2x^2 + 7x + 3)} - 10\color{red}{(2x + 1)}$$

$$\color{red}{(2x^2 + 7x + 3)} = (x + 3)\color{red}{(2x+1)}$$

So the gcd is $$2x+1 = 2\left(x + \dfrac 12 \right)$$.