<s>[INST] Justify $\gcd$ of $f(x) = x^3 - 6x^2 + x + 4$ and $g(x) = x^5 - 6x +1$ Let $f(x) = x^3 - 6x^2 + x + 4$ and $g(x) = x^5 - 6x +1$. Using Euclidean algorithm I find $\gcd[f(x), g(x)] = 1$. How could I JUSTIFY that $h(x) = 1$ is the ACTUAL $\gcd$ of $f(x)$ and $g(x)$? 
Thanks.
 [/INST] Actually Euclidean Algorithm is a really good proof.
One other way is to factorize one of the polynomials into linear polynomials. To do the find the zeroes of that polynomials. I'll use the polynomial $f(x)$ so the zeroes are at $x = 1$, $x=\frac 12 (5 \pm \sqrt{41})$.
So we can factorize it as:
$$x^3 - 6x^2 + x + 4 = (x-1)(\frac 12 (x-5+\sqrt{41}))(\frac 12 (x-5-\sqrt{41}))$$
$$x^3 - 6x^2 + x + 4 = \frac14(x-1)(x-5+\sqrt{41})(x-5-\sqrt{41})$$
So now we need to check which of this factors divide $g(x)$. Using the Polynomial remainder Theorem we know that a linear polynomial of the type $(x-a)$ divides some polynomial $p(x)$ if and only if $p(a) = 0$
So we have three cases to check those are $a = 1$, $a = 5 + \sqrt{41}$ and $a = 5 - \sqrt{41}$. And for all three cases we'll get that $g(a) \neq 0$, so neither of the factors of $f(x)$ is divisor of $g(x)$, i.e $gcd(f(x),g(x)) = 1$
Also sometimes to get rid of those ugly calculation you can use Sylvester matrix to check whether 2 polynomials are coprime. You can read how to generate one reading the intructions in the link so for this example the matrix would look like:
$$\begin{bmatrix}
 1 & 0 &  0 & 0 & -6 &  1 &  0 &  0 \\
 0 & 1 & 0 &  0 & 0 & -6 &  1 &  0 \\
 0 & 0 & 1 & 0 &  0 & 0 & -6 &  1 \\
 1 & -6 & 1 &  4 &  0 &  0 & 0 &  0 \\
 0 & 1 & -6 & 1 &  4 & 0 & 0 & 0 \\
 0 & 0 & 1 & -6 & 1 &  4 & 0 & 0 \\
 0 & 0 & 0 & 1 & -6 & 1 &  4 & 0 \\
 0 & 0 & 0 & 0 & 1 & -6 & 1 &  4 
\end{bmatrix}$$
Take the determinant of it. If it's $0$ the two polynomials have a common root and a common factor. Otherwise they are coprime and you can stop your caclulation there. So for this two polynomials we have:
$$\begin{vmatrix}
 1 & 0 &  0 & 0 & -6 &  1 &  0 &  0 \\
 0 & 1 & 0 &  0 & 0 & -6 &  1 &  0 \\
 0 & 0 & 1 & 0 &  0 & 0 & -6 &  1 \\
 1 & -6 & 1 &  4 &  0 &  0 & 0 &  0 \\
 0 & 1 & -6 & 1 &  4 & 0 & 0 & 0 \\
 0 & 0 & 1 & -6 & 1 &  4 & 0 & 0 \\
 0 & 0 & 0 & 1 & -6 & 1 &  4 & 0 \\
 0 & 0 & 0 & 0 & 1 & -6 & 1 &  4 
\end{vmatrix} = 120784$$
So clearly this isn't equal to $0$ and we can conclude that these two polynomails are coprime.
</s>