Polynomial gcd of $x^5+x+1$ and $x^2+1$

Question

In a multiple choice assignment I had to find the gcd of

$$x^5+x+1$$

and

$$x^2+1$$

I can find it with the Euclidean algorithm, but that is taking me quite some time and work. Since this test was supposted to be solved very quickly there must be an easier method I guess. One of the multichoice answers was actually $1$ which is the correct solution. So I though maybe it's obvious that there is no gcd other than $1$ for this question? Is that so and if yes, why?

Answer 1

Let $d(x)$ be the greatest common divisor, so that $d(x)\mid x^2+1$ and $d(x)\mid x^5+x+1$.

Suppose $d(x)\ne 1$.

Then any root of $d$ is a root of $x^2+1$, so equals $\pm i$.

Any root of $d$ is a root of $x^5+x+1$. But $(\pm i)^5 +(\pm i)+1=\pm 2i+1\ne 1$.

Hence $d(x)=1$.

[All this can be done in your head in seconds].

Answer 2

One other way I see is to factorize $x^5+x+1$ over $\Bbb Q$. Since it has no rational root by the rational root theorem, we may assume that it is a product of a quadratic and a cubic polynomial. This quickly leads to $$ x^5+x+1=(x^3 - x^2 + 1)(x^2 + x + 1), $$ which is interesting in itself, and also implies that $\gcd(x^2+1,x^5+x+1)=1$.

Answer 3

Go to complex numbers, as the GCD is the same over real numbers and over complex numbers. (Euclid's algorithm doesn't "care" if you are executing it in $\mathbb R$ or in a bigger field.)

So, $x^2+1$ factorises as $(x-i)(x+i)$. Try the roots $i, -i$ in $x^5+x+1$ and you will get $2i+1$ and $-2i+1$, respectively. So none of the "prime" factors of $x^2+1$ divide $x^5+x+1$.

Thus, $x^2+1$ and $x^5+x+1$ are coprime and their gcd is $1$.