Finding irreducible factors of a polynomial over $\mathbb{F}_3$ How to find irreducible factors of a polynomial? For example, how to find the  irreducible factors of $x^4+1$ over integers mod 3? I have a start but need some help.
 A: First of all, note that for any $x\in \Bbb Z_3$, we have either $x^4=0$ or $x^4=1$, so in no case do we have $x^4+1=0$. Thus, if it factors at all over $\Bbb Z_3$, it will factor as two irreducible quadratics. We may as well assume they are monic, and we readily find that they must be of the form $$x^4+1=(x^2+ax+b)(x^2-ax+d),$$ where $$b+d=a^2\\a(d-b)=0\\bd=1.$$ Now, if $a=0$, then we would find by the first and third of the equations in the system above that $-1$ has a square root in $\Bbb Z_3.$ (Why?) However, $0$ and $1$ are the only squares in $\Bbb Z_3$, so $a\ne0$, whence $b=d$ by the second equation in the system above, so the system becomes $$2b=a^2=1\\b^2=1.$$ Hence, $b=2=-1,$ so $$x^4+1=(x^2+x-1)(x^2-x-1).$$ See this post for some of the details I glossed over.
A: An integer factorization that everyone ought to know or to learn:
 $$x^4+4=(x^2+2x+2)(x^2-2x+2)\,.$$ The mod-$3$-factorization of $x^4+1$ follows.
A: Hint $\rm\: mod\ 3\!:\,\ x^4\!+\!1 \equiv (x^2\!-\!1)^2\!-x^2 \equiv\, (x^2\!-\!1\!+\!x)\,(x^2\!-\!1\!-\!x)$
$\begin{eqnarray}\rm\!\! {\bf Generally}\ \ mod\,\ a^2\!+\!2b\!:\,\ x^4\!+\!b^2 &\equiv\,&\rm x^4\!+\!b^2\!-\!(\color{#0a0}{2b}\!+\!\color{#c00}{a^2})\,x^2\\ &\equiv\,&\rm x^4\!-\!\color{#0a0}{2b}\,x^2\!+b^2 - \color{#c00}{a^2}\,x^2\\ &\equiv\,&\rm (x^2\!-\!b)^2-(ax)^2\\ &\equiv\,&\rm (x^2\!-\!b\!-\!ax)\,(x^2\!-\!b\!+\!ax)\end{eqnarray}$
i.e. completing the square yields a differences of squares, so a factorization.
