Wednesday, September 6, 2017

abstract algebra - 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.)


Answer




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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...