You can just do it by exhaustion. There are very few cases to think about (and if you have to start thinking about the case deg=1 then you're missing something).
LaTeX is explained in the introduction to LaTeX thread (probably in physics): just look around.
Okey, something like this?
The case deg 1 is obvious. The case 2 is obvious except for the irreducible x^2+x+1, where I can find a solution. Degree 4 is obvious except for the irreducible cases which I can try?
Why not? Have you actually tried to look at the irreducible casees? If you do you might figure out what a general condition would be, and why the degs 1,2,4 polys all satisfyit (and presumably why there is a deg 3 poly that doesn't). You won't figure out a general criterion just by pulling it out of thin air. You look at cases where it is true, where it isn't and figure out what quantifies the difference. That's how you do maths.