I leave my earlier post below where I mistakenly understood the original problem because of a bad illustrative example given there. Here I only indicate the explicit formula for the number $N_ m(p)$ of monic polynomials of exact degree $m$ irreducible over $GF(p)$:
$$
N_m(p)=\frac1m\sum_{d\mid m}\mu(d)p^{m/d}.
$$
This formula is again from Prasolov's *Polynomials*, and it seems to be absent in other posts and comments.

I assume that the irreducibility is discussed over $\mathbb Z$, otherwise $x^{400}+x^5+x^2+1$ has zero $x=1$ in $GF(2)$.

Victor Prasolov in Section 8 of his book *Polynomials* discusses the irreducibility
of trinomials and quadrinomials, mostly based on the work [W. Ljunggren, On the
irreducibility of certain trinomials and quadrinomials, *Math. Scand.* **8**
(1960), 65--70]. One of the results from there is as follows.

**Theorem.** Let $n\ge2m$, $d=\text{gcd}(n,m)$, $n_1=n/d$ and $m_1=m/d$. Then the
polynomial
$$
g(x)=x^n+\epsilon x^m+\epsilon', \quad\text{where}\ \epsilon,\epsilon'\in\lbrace\pm1\rbrace,
$$
is irreducible except for the following cases in which $n_1+m_1\equiv0\pmod3$:

(a) $n_1$ and $m_1$ are odd and $\epsilon=1$;

(b) $n_1$ is even and $\epsilon'=1$;

(c) $m_1$ is even and $\epsilon=\epsilon'$.

In all three cases (a)--(c), $g(x)$ is a product of a certain irreducible polynomial
and $x^{2d}+\epsilon^m{\epsilon'}^nx^d+1$.

**Corollary.**
If $n\not\equiv2\pmod3$, then $x^n+x+1$ is irreducible.

If $n\equiv2\pmod3$, then $x^n+x^2+1$ is irreducible.

In other words, there is an irreducible degree $n$ polynomial $g(x)$ of the wanted form such that $\deg(g(x)-x^n)\le2$, and this bound cannot be further improved.

unitary, except for the zero polynomial!) $\endgroup$ – Mariano Suárez-Álvarez Nov 23 '11 at 17:13