<s>[INST] Find monic irreducible polynomials in $Z_3[x]$ which divide both f(x) and g(x) The Problem
Find all monic irreducible polynomials in $Z_3[x]$ which divide both $f(x)$ and $g(x)$.
Where
$f(x) = x^5+x^3+x^2+x+2$, $g(x) = x^6+x^5+x^3+1$
This problem is part of an early exam so it comes with a solution.
My attempt at a solution
What I did was doing $gcd(f(x),g(x))$ and that went alright, the first 2 iterations gave me these results:
$g(x) = (x+1)f(x) + 2x^4+2x^3+x^2+2$
$f(x) = (2x+1)(2x^4+2x^3+x^2+2) + 2x^3$
After finding the gcd you simply find the irreducible factors of the gcd, and then you divide f(x) and g(x) by the gcd and start over. That's what I would do anyway.
The solution given
They start out with the gcd:
$g(x) = (x+1)f(x) + 2x^4+2x^3+x^2+2$
then let $2h(x) =  2x^4+2x^3+x^2+2$
$f(x) = (x+2)h(x) + 0$
Therefore $gcd(f(x),g(x)) = h(x)$
We now look for linear factors in $h(x)$ and find that $h(2)=0$ therefore $x-2=x+1$ is a factor of $h(x)$, polynomial division gives us:
$h(x)=(x+1)(x^3+2x+1)$, and $x^3+2x+1$ has a degree beneath or equal to 3 and no linear factors, therefore irreducible.
Answer: the factors are $x+1$ and $x^3+2x+1$
My questions
Why can we 'take out' the 2 from $2h(x)$ when we continue in our gcd search?
Why do we not divide $f(x)$ and $g(x)$ to search for further gcd:s to find new factors?
 [/INST] We have $\ \gcd(g,f) = \gcd(g\bmod  f,f) = \gcd(2h,f) = \gcd(h,f) = h\ $ since $\ \gcd(2,f) = 1$
Alternatively we can use $\, 2 = -1\ \in\Bbb Z_3\,$ so $\,\gcd(2h,f) = \gcd(-h,f) = \gcd(h,f) = h$
There is an error in your calculation: $\ f\bmod 2h = 0,\, $ not $\, 2x^3 $ (so there's no need to go further)
</s>