<s>[INST] Find the greatest common divisor (gcd) of $f(x) = x^2 + 1$ and $g(x) = x^6 + x^3 + x + 1$ Find the greatest common divisor (gcd) of $f(x) = x^2 + 1$ and $g(x) = x^6 + x^3 + x + 1$.
Since $x^6 + x^3 + x + 1 = (x^2 + 1)(x^4 - x^2 + x + 1)$, $\mathrm{gcd}[f(x),g(x)] = x^2 + 1$.
My question is how could I JUSTIFY that the answer is ACTUAL gcd of $f(x)$ and $g(x)$. thanks
 [/INST] Clearly $x^{2}+1$ divides both $f$ and $g$, as you have shown. On the other hand, since $g=x^{2}+1$, any polynomial $h$ dividing both $f$ and $g$ must divide $g=x^{2}+1$. Thus, by definition, $x^{2}+1$ is the greatest common divisor.
This example was easy since $g$ divides $f$. In other cases, you could use the Euclidean Algorithm to find the gcd of $f$ and $g$.
</s>