I have two polynomials $f,g\in\mathbb{Q}[x]$, $f=x^3-x^2-1,\ g=x^2-3x+1$ and I have to find their GCD using the Extended Euclidean algorithm. I've done the following steps:

$$ \begin{aligned} f= gq_0+r_0 & \qquad q_0 = x+2 & r_0 = 5x-3 &\qquad\cfrac{x^3-x^2-1}{x^2-3x+1} = x+2+\cfrac{5x-3}{x^2-3x+1}\\ g=r_0q_1 + r_1 & \qquad q_1 = \cfrac{x}{5}-\cfrac{12}{25} & r_1 = -\cfrac{11}{25} &\qquad \cfrac{x^2-3x+1}{5x-3} = \cfrac{x}{5}-\cfrac{12}{25}+\cfrac{-11/25}{5x-3}\\ \end{aligned} $$

And, If I understood everything correctly GCD of $f,g$ is $-\cfrac{11}{25}$, because $\exists q_2\in\mathbb{Q}[x]\colon r_0=r_1q_2+0$ and therefore $-\cfrac{11}{25}$ is equal to GCD of $f,g$ and this is indeed true, because I can divide any of them on this number without any problems. But, according to WolframAlphra and SageMath their GCD is equal to $1$ and I'm much more likely to believe that I've made a mistake somewhere, But I can't see any issues with my computations either (I've checked all polynomial divisions etc using the same tools, so I think that it is not a computational error)

And another question that follows from previous one: if GCD of two polynomials of nonzero degree is a polynomial of a zero degree (in other words an number) does that mean that they are coprime?

NOTE Those polynomials do not have any common roots even in $\mathbb{C}$

P.S Sorry for asking such basic question but wasn't able to find any examples of the Extended Euclidean algorithm that involved polynomials with a degree more than two and used Euclidean algorithm instead of factoring

P.P.S. Sage Math code

f = x^3-x^2-1 g = x^2-3*x+1 f.gcd(g) 1


2 Answers 2


I didn't check your computations, but there is a basic misunderstanding in what you wrote. Asserting that $\gcd\bigl(p(x),q(x)\bigr)=-\frac{11}{25}$ or asserting that $\gcd\bigl(p(x),q(x)\bigr)=1$ is the same thing. That because if $\gcd\bigl(p(x),q(x)\bigr)=r(x)$, then $\gcd\bigl(p(x),q(x)\bigr)=k\times r(x)$ for any $k\in\mathbb{Q}\setminus\{0\}$. We usually normalize the answer by taking the only monic polynomial which is a multiple of the one we got by applying the extended Euclidean algorithm.


This is an extended meditation on the answer of @JoséCarlosSantos, who wrote pretty much what I would have written. But some very interesting things are going on here, and I would like to say something about them, even if they may be at a more advanced level than interests you.

I will shorten notation somewhat by writing your dividend $x^3-x^2-1=\Delta$, and your divisor $x^2-3x+1=d$. What you have shown is $$ -\frac{11}{25}=\left(\frac{x^2}5-\frac{2x}{25}+\frac1{25}\right)d+\left(-\frac x5+\frac{12}{25}\right)\Delta\,, $$ since that’s what your two divisions boil down to. This equation is sufficient to show that in the ring $\Bbb Q[x]$, $\gcd(\Delta,d)=1$, that is, that they are relatively prime. As Santos says, in this context we are interested in gcd only up to units. But what if we want to work in the ring $\Bbb Z[x]$? It’s no longer a principal ideal domain, but it is a unique factorization domain, and maybe we can say something there. We can clear of fractions and change the sign, multiplying by $-25$, to get $$ 11=\left(-5x^2+2x-1\right)d +\left(5x-12\right)\Delta\,. $$ This says that $11\in(d,\Delta)$, the ideal of $\Bbb Z[x]$ generated by $d$ and $\Delta$. It’s just the set of all things of form $d(x)A(x)+\Delta(x)B(x)$ for integer polynomials $A$ and $B$. One of the interesting things that this second equation says is that if we pass to a universe where eleven is zero, the original two polynomials will no longer be relatively prime. Indeed, when we work over $\Bbb F_{11}=\Bbb Z/11\Bbb Z$, we find that the gcd is now $x+6$, so that $5=-6$ is a root of both of our polynomials when we work in $\Bbb F_{11}$.

Now, I looked at the fact that $11\in(d,\Delta)$, and wondered about the resulting ideal inclusion $(11)\subset(d,\Delta)$. It couldn’t be equality, could it? The big ideal looks like it might be maximal in $\Bbb Z[x]$, while $(11)$ certainly is not maximal: we have $\Bbb Z[x]/(11)\cong\Bbb F_{11}[x]$, which is not a field.

I am hoping to find an additional generator, with $11$, of the ideal $(d,\Delta)$. It should be something like $x+6$, because that’s a generator of the ideal of $\Bbb F_{11}[x]$ generated by $d$ and $\Delta$, or at least their images there. We have it in your first remainder $r_0=5x-3$. I’ll now show that $(d,\Delta)=(11,5x-3)$.

We already know that $11$ and $5x-3$ are in $(d,\Delta)$, so that $(11,5x-3)\subset(d,\Delta)$. Now for the reverse inclusion; I’ll spare you the computations that led me to these: \begin{align} d=x^2-3x+1&=11(-4x^2-x+2)\quad+\quad(5x-3)(9x+7)\\ \Delta=x^3-x^2-1&=11(-4x^3+x^2-x+1)\quad+\quad(5x-3)(9x^2+3x+4) \end{align} Since both $d$ and $\Delta$ are in $(11,5x-3)$, we get the desired inclusion $(x^3-x^2-1,x^2-3x+1)\subset(11,5x-3)$, and thus equality.

  • $\begingroup$ Simpler: $\ 11\in(\Delta,d)\,\Rightarrow\,(\Delta,d) = (11,\Delta,d) = (11,\,(\Delta,d)\bmod 11) = (11,\,x\!+\!6)$ $\ $ $\endgroup$ Mar 9, 2019 at 3:59

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.