# Polynom irreducibility over $\mathbb Z_5$

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?

-

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.

-
Exactly how does it depend on fact that $\mathbb Z_5$ is a field? – Dark Archon Jun 9 '14 at 16:32
@DarkArchon The fact that $Z_5$ is a field implies that it has no $0$ divisors. – AJ Stas Jun 9 '14 at 16:33
You misuderstood me. How does the fact that $r$ is root of polynomial if and only if $x−r$ is a factor of $p$ depends on a fact that $\mathbb Z_5$ is a field? – Dark Archon Jun 9 '14 at 16:35
You should add after "this process terminates": and the real work begins. – Marc van Leeuwen Jun 9 '14 at 16:36
@MarcvanLeeuwen -- Yes indeed, but in this case it just so happens that after factoring out all linear factors, all that is left is an irreducible quadratic. So there isn't very much "real work" to do. – mweiss Jun 9 '14 at 16:53

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!

-