Polynom irreducibility over $\mathbb Z_5$

Question

So, I have polynom over $\mathbb Z_5$: $x^8 - x^7 + 2x^6 + x^5 + 2x^4 + 2x^2 +3x +1$ and I have to find his irreducibile factors. How to do that? I can find his roots by replacing $x$ with $[1]_5, [2]_5, \dots $ and so on. What step is the next one?

Answer 1

Because $\mathbb{Z}_5$ is a field, an element $r \in \mathbb{Z}_5$ is a root of your polynomial $p$ if and only if $x-r$ is a factor of $p$. So one way to attack this problem is to test each element of $\mathbb{Z}_5$ one at a time to see if it is a root; if it is, use polynomial long division (or synthetic division -- both algorithms work over $\mathbb{Z}_5$ exactly the same way that they do over $\mathbb{R}$) to write $p$ in the form $(x-r)q$, and then iterate the procedure by testing for the roots of $q$. Eventually you will get down to a polynomial that has no roots; at that point the process terminates.

Answer 2

You could start finding all roots in $\Bbb F_5$, which give degree $1$ (irreducible) factors. Don't forget to try again after Euclidean division by $X-a$ after finding a root $a$, since it might be a multiple root. After than it depends on what degree is left. If it is $3$ or less you are done, because such polynomials cannot be reducible without having a root; otherwise you must also consider the possibility of a decomposition without linear factors. If the remaining degree is at most$~5$ it might be worth while to look for roots in $\Bbb F_{25}\setminus\Bbb F_5$ in order to locate degree $2$ irreducible factors. If there is no easy way out, there is [Berlekamp's algorithm][1], which I described in [this answer][2].

It turns out you are extremely lucky here, with a total of $6$ linear factors, leaving a polynomial of degree$~2$ without roots, which is obviously irreducible. Ask for a more interesting example next time!