# GCD of two polynomials

Find the greatest common divisor of each of the following pairs $p(x)$ and $q(x)$ of polynomials. $p(x) = 7x^3 + 6x^2 −8x+ 4$ and $q(x) = x^3 + x− 2$, where $p(x), q(x) \in Q[x]$.

I divided $p(x)$ by $q(x)$ and I got $7$ with the remainder $r_1(x) = 6x^2 - 15x + 18$

then I got completely confused and don't know how to find the $\gcd$ of them. Please help. Thank you!

• Are you familiar with the Euclidean algorithm? – quapka Nov 23 '14 at 19:59
• yes, a(x) and b(x) such that a(x)p(x) + b(x)q(x) = d(x) – Jessy White Nov 23 '14 at 20:02
• Well, this equality is called Bézout's identity (which you can get using extended GCD/Euclidean algorithm). But you don't need to find the polynomials $a(x), b(x)$ (those you mention in the previous comment) in order to find $d(x)$. – quapka Nov 23 '14 at 20:10
• Have you got time to do the Euclidean algorithm I posted in my answer? – quapka Nov 24 '14 at 11:51

The basic of Euclidean algorithm more e.g. here. Having the polynomials $p,q$. We calculate \begin{alignat*}{2} p &= s_0\cdot q & &+ r_0\\ q &= s_1\cdot r_0 & &+ r_1\\ r_0 &= s_2 \cdot r_1 & &+ r_2\\ &\vdots & &\\ r_{n-3} &= s_{n-1}\cdot r_{n-2} & &+ r_{n-1}\\ r_{n-2} &= s_{n}\cdot r_{n-1} & &+ r_{n}.\\ \end{alignat*}
Each line means dividing one polynomial by other (you dividing $p$ by $q$ is the first row). $s_i$ and $r_j$ are also polynomials. $r_j$ are the remainders after the division. We do those steps while $r_n \neq 0$. If $r_n = 0$ then $\gcd{(p,q)} = r_{n-1}$.
Euclidean algorithm for $p(x), q(x)$. $$7x^3 + 6x^2 - 8x+4 = 7\cdot (x^3+x-2) + 6x^2-15x + 18$$ So according to notation in the algorithm above $s_0(x) = 0$ and $r_0(x) = 6x^2-15x + 18$. No we divide $q(x)$ by $r_0(x)$
$$x^3+x-2 = \left(\frac{1}{6}x + \frac{5}{12}\right)\cdot (6x^2-15x) + \frac{17}{4}x - \frac{19}{2}.$$
So $s_1(x) = \frac{1}{6}x + \frac{5}{12}$ and $r_1(x) = \frac{17}{4}x - \frac{19}{2}$. Can you continue in this algorithm?
• Well, wolfram gives $\gcd{(p(x), q(x))=1}$. – quapka Nov 25 '14 at 22:52