Divisors of $x^3 + x + 1$ in $Z_3[x]$ Divisors of $f(x) = x^3 + x + 1$ in $Z_3[x]$
Do I have to manually check whether each polynomial in $Z_3[x]$ with degree less than $3$ divides $f$ or is there a better way? That's $3^3 = 27$ polynomials to check (although a few are obviously trivial).
 A: You don't need to check that many polynomials, for three reasons:


*

*If a polynomial of degree $3$ has a factor of degree $2$, it also has a factor of degree $1$; in general, for a polynomial of degree $n$, the highest degree divisor you have to check is ${\lfloor{\frac{n}{2}}\rfloor}$.

*Because $\mathbb{F}_3$ is a field, every nonzero element has an inverse; so if you have a factor $ax+b$, you can rewrite this factor as $x+a^{-1}b$ and just check for factors of the form $x+c$. (Again, you can generalize this to higher degrees; you can always make the coefficient of the highest power of $x$ equal to $1$, and make checking for roots easier.

*Lastly, if you want to see if $x+c$ divides your polynomial $f$, you can just check whether or not $f(-c)=0$. 


If in step $3$, you find no linear factors, it's irreducible. If there's only one, then your polynomial is a product of a linear and irreducible quadratic factor, i.e., $f(x)=(x+a)(x^2+bx+c)$, where the latter polynomial is irreducible. And if you find two, your polynomial is completely reducible into linear factors, $f(x)=(x+a)(x+b)(x+c)$.
A word of warning on step $3$: That you can completely factor your polynomial just by finding linear factors stops working for any degree greater than $3$. Even if we step up into polynomials of degree $4$, we can't just check for linear factors; you can always do that, but your polynomial might be factored as $(x^2+ax+b)(x^2+cx+d)$, so you'd have to check for quadratic factors too! 
A: Hint: What is $f(1)$? That should get you a partial factorization, and make checking the rest quite a bit easier.
Bear in mind that $\Bbb Z_3$ is a field, so every non-zero constant is a divisor.
