Showing in a simple way that the GCD of two polynomials is $1$.

Question

I have been trying to solve the following problem:

Find the GCD of $4x^5+7x^3+2x^2+1$ and $3x^3+x+1$ in $\mathbb{Q}[x]$.

I understand, by looking at similar problems and talking to my friends, that it is $1$. However, I cannot find a way to show this without going through some nasty fractions, be it using the Euclidean Algorithm or just long division. Is it not $1$? If it is, is there a simpler, more elegant way to show it, other than nasty fractions?

Answer 1

Write $f(x), g(x)$ for your two polynomials. They're both primitive, so by Gauss's lemma their irreducible factorization over $\mathbb{Q}[x]$ consists of primitive irreducible polynomials in $\mathbb{Z}[x]$. Hence their gcd $h(x) = \gcd(f(x), g(x))$ has integer coefficients. By an examination of leading coefficients $h(x)$ must be monic, which implies that it can't have degree $3$ (since then it would be equal to $g(x)$ which can't divide $h(x)$ in $\mathbb{Z}[x]$), so $\deg h(x) \le 2$.

This means $h(x)$ can take the value $1$ for integer values of $x$ at most twice without being identically equal to $1$ (since $h(x) - 1$ can have at most $2$ roots). So if we can find $3$ integer values $x_1, \dots x_4$ such that $\gcd(f(x_i), g(x_i)) = 1$ (these are $\gcd$s of ordinary integers now), this implies that $h(x) = 1$.

Now we calculate:

• $\gcd(f(0), g(0)) = \gcd(1, 1) = 1$
• $\gcd(f(-1), g(-1)) = \gcd(-8, -3) = 1$
• $\gcd(f(1), g(1)) = \gcd(14, 5) = 1$

So $h(x) = 1$.

---

A second approach is to prove that $g(x)$ is irreducible, which is not hard using the rational root theorem and then working $\bmod 2$; it follows that $h(x) = 1$ or $g(x)$, and we ruled out $h(x) = g(x)$ above.