How to find all possible polynomials over a given finite field?

Question

How would I find the possible polynomials over GF(p)? I'm trying to figure out which polynomials of a specific given finite field have no roots.

Answer 1

Let's use a specific example, say $\mathbb{Z}_3$. The degree zero polynomials are: $$0,1,2,$$ the degree 1 are: $$x, x+1,x+2, 2x, 2x+1, 2x+2,$$ the degree 2 are: $$x^2, x^2+1, x^2+2, x^2+x, x^2+x+1, x^2+x+2,...$$

See the pattern? This generalizes upwards. For $\mathbb{Z}_p[x]$, the order is infinite, unless you discuss only polynomials of degree $\le n$, in which case some elementary combinatorics gives you $p^{n+1}$.