I am trying to find the gcd of those 2 polynomials

$x^5-2x^2+1$ and $x^3+3x^2-x-3$

In the book I use, there is a corollary just before this exercice saying that

Corollary : Let $F$ $\subset$ $E$ be fields, and let $f(x),g(x)$ $\in$ F[$x$] $\subset$ E[x]. Then the gcd of $f$ and $g$ computed in $F[x]$ is the same as the gcd of f and g computed in $E[x]$.

My plan is then to find the gcd of those 2 polynomials in an "easy" fields, i.e $\mathbb{Z}_2[x]$

So, working in $\mathbb{Z}_2[x]$, our 2 polynomials become $x^5+1$ and $ x^3+x^2-x-1$, is this true to start with ?

When I apply the euclidian algorithm, I find the quotient $q(x) = x^2-x+2$ and the remainder $r(x) = -2x^2+x+3$, i.e in $\mathbb{Z}_2[x]$, $q(x)=x^2-x$ and $r(x)=x+1$.

Applying again the algorithm i.e, euclidian division of $p(x)= x^3+x^2-x-1$ by $r(x)=x+1$, I find $r'(x) = 0$, $q'(x)=x^2-1$.

As the remainder is $0$, then the gdc of the 2 polynomials in $\mathbb{Z}_2[x]$ should be the former remainder, i.e $r(x)=x+1$ but it does not work in $\mathbb{Z}[x]$ ! Take $x=5$, the first polynomial gives 3076, the second one gives 192. The gdc should then be $x+1=5+1=6$ but $6$ does not divide $3076$.

In $\mathbb{Z}_2[x]$, the first polynomial gives $x^5+1=3126$, the second one $ x^3+x^2-x-1=144$ Here, 6 indeed divides those 2 numbers, why does it not work in $\mathbb{Z}[x]$ ?

Which is not what is expected from the corollary.

Where did I go wrong ?

I tried to factorise the polynomial, they have a $1$ as a common root, so could $x-1$ be their gcd ? It is a common divisor but I do not know how to prove it is the greatest one.

Thanks very much for any help you can provide ! :D

  • 4
    $\begingroup$ $\mathbb{Z}$ is not a field, and $\mathbb{Z}/2\mathbb{Z}$ is not even a subring of $\mathbb{Z}$. $\endgroup$ – Tobias Kildetoft Oct 1 '13 at 11:00
  • $\begingroup$ Could you five me two fields I could use to solve this then ? Thanks for your answer ! $\endgroup$ – ALM Oct 1 '13 at 11:01
  • 1
    $\begingroup$ You need to also use that monic polynomials factor the same over $\mathbb{Z}$ and over $\mathbb{Q}$, which will then allow you to use the corollary with for example $\mathbb{Q}$ and $\mathbb{C}$ (assuming you can factor them completely). $\endgroup$ – Tobias Kildetoft Oct 1 '13 at 11:04
  • 1
    $\begingroup$ Do polynomial division by that root and see that there are no further common roots over $\mathbb{C}$ (you can easily find the roots of one of them and check that they are not roots of the other). $\endgroup$ – Tobias Kildetoft Oct 1 '13 at 11:13
  • 1
    $\begingroup$ Yes, that is a correct argument, since you use the corollary to calculate the gcd over $\mathbb{C}$. $\endgroup$ – Tobias Kildetoft Oct 1 '13 at 11:27

We factorize first the 2 given polynomials such that :

$x^5−2x^2+1=(x−1)(x^4+x^3+x^2−x−1)$ and $x^3+3x^2−x−3=(x−1)(x^2+4x+3)$

They have the common root $1$. The others roots of the second polynomials are {-3,-1} but they are not roots of the first one, i.e $x-1$ is the only (then the greatest) common divisor of those 2 polynomials.

Keep in mind we use the corollary given in the original post to justify this argument.

Thanks for your help


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.