## Compute the greatest common divisor of two polynomials over QQ

Compute the greatest common divisor of $p(x) = x^4 + 3x^3 + 10x^2 + 18x + 24$ and $q(x) = x^4 + 2x^3 + 13x^2 + 12x + 42$ in $\mathbb{Q}[x]$.

We will carry out the Euclidean algorithm. Note that $p(x) = q(x) + (x^3-3x^2+6x-18)$, $q(x) = (x^3-3x^2+6x-18)(x+5) + (22x^2+132)$, and $x^3-3x^2+6x-18 = (22x^2+132)(\frac{1}{22}x - \frac{3}{22})$. In particular, $22x^2+132$ is a greatest common divisor of $p(x)$ and $q(x)$ in $\mathbb{Q}[x]$. Since 22 is a unit, we see that $x^2 + 6$ is also a greatest common divisor.

Indeed, $p(x) = (x^2+6)(x^2+3x+4)$ and $q(x) = (x^2+6)(x^2+2x+7)$. Note that $x^2+3x+4$ is irreducible in $\mathbb{Z}[x]$ (hence $\mathbb{Q}[x]$) since $\{a+b=3, ab=4 \}$ has no integer solutiions, and similarly $x^2+2x+7$ is irreducible, and these are not associates.