The first polynomial I had to decompose over $\mathbb{Z}_3$ is:
$$x^2+x+1$$
I started by noticing that one root of it is $1$ so I thougth that I could factor this polynomial by $(x-1)$ but I couldn't find a way (why?). Then I started to brute force things, like: "hmmm, all the coefficients are $1$, what is congruent to $1 \mod 3$ ? 4, for example. So I remembered of the polynomial:
$$x^2+4x+4 = (x+2)(x+2)$$
$x^2+4x+4 = x^2+x+1 = (x+2)(x+2) \mod 3$
Am I doing it right? How'd you do it without 'brute forcing'? Why I couldn't divide by $(x-1)$?
How could I apply this for this other polynomial:
$$2x^3+2x^2+x+1$$
?
Yes, you're doing it right. Polynomial division gets very easy to compute, once you remeber little things such that $1\equiv-2 \pmod3$.
For instance: $$2x^3+2x^2+x+1 = (2x^2+1)(x+1) = (1-x^2)(x+1) = (x+1)^2(x-1)$$
Of course, with a polynomial of degree $>3$ checking the roots is not enough anymore, since it could be a product of irreducible factors of degree $\ge 2$, e.g. $$x^4+2x^3+2x^2+x+1=(x^2+x+2)^2$$