Extrapolated Comments converted to answer:
First, we note that there are $2^n$ polynomials in $\mathbb{Z}_2[x]$ of degree $n$.
A polynomial $p(x)$ of degree $2$ or $3$ is irreducible if and only if it does not have linear factors. Therefore, it suffices to show that $p(0) = p(1) = 1$. This quickly tells us that $x^2 + x + 1$ is the only irreducible polynomial of degree $2$. This also tells us that $x^3 + x^2 + 1$ and $x^3 + x + 1$ are the only irreducible polynomials of degree $3$.
As hardmath points out, for a polynomial $p(x)$ of degree $4$ or $5$ to be irreducible, it suffices to show that $p(x)$ has no linear or quadratic factors. To rule out the linear factors, we can again throw out any polynomial not satisfying $p(0) = p(1) = 1$. That is, we can throw out any polynomial with constant term $0$, and we can throw out any polynomial with an even number of terms. This rules out $3/4$ of the polynomials. For example, the $4^{th}$ degree polynomials which do not have linear factors are:
- $ x^4 + x^3 + x^2 + x + 1 $
- $ x^4 + x^3 + 1 $
- $ x^4 + x^2 + 1 $
- $ x^4 + x + 1 $
The $5^{th}$ degree polynomials which do not contain linear factors are:
- $x^5 + x^4 + x^3 + x^2 + 1$
- $x^5 + x^4 + x^3 + x + 1$
- $x^5 + x^4 + x^2 + x + 1$
- $x^5 + x^3 + x^2 + x + 1$
- $x^5 + x^4 + 1$
- $x^5 + x^3 + 1$
- $x^5 + x^2 + 1$
- $x^5 + x + 1$
It still remains to check whether $x^2 + x + 1$ (which is the only quadratic irreducible polynomial in $\mathbb{Z}_2[x]$) divides any of these polynomials. This can be done by hand for sufficiently small degrees. Again, as hardmath points out, since $x^2 + x + 1$ is the only irreducible polynomial of degree $2$, it follows that $(x^2 + x + 1)^2 = x^4 + x^2 + 1$ is the only polynomial of degree $4$ which does not have linear factors and yet is not irreducible. Therefore, the other $3$ polynomials listed must be irreducible. Similarly, for degree $5$ polynomials, we can rule out
$$
(x^2 + x + 1)(x^3 + x^2 + 1) = x^5 + x + 1
$$
and
$$
(x^2 + x + 1)(x^3 + x + 1) = x^5 + x^4 + 1.
$$
The other $6$ listed polynomials must therefore be irreducible.
Notice that this trick of throwing out polynomials with linear factors, then quadratic factors, etc. (which hardmath called akin to the Sieve of Eratosthenes) is not efficient for large degree polynomials (even degree $6$ starts to be a problem, as a polynomial of degree $6$ can factor as a product of to polynomials of degree $3$). This method, therefore only works for sufficiently small degree polynomials.
To recap, the irreducible polynomials in $\mathbb{Z}_2[x]$ of degree $\leq 5$ are:
- $x$
- $x+1$
- $x^2 + x + 1$
- $x^3 + x^2 + 1$
- $x^3 + x + 1$
- $ x^4 + x^3 + x^2 + x + 1 $
- $ x^4 + x^3 + 1 $
- $ x^4 + x + 1 $
- $x^5 + x^4 + x^3 + x^2 + 1$
- $x^5 + x^4 + x^3 + x + 1$
- $x^5 + x^4 + x^2 + x + 1$
- $x^5 + x^3 + x^2 + x + 1$
- $x^5 + x^3 + 1$
- $x^5 + x^2 + 1$
Over $\mathbb{F}_p$, the product of all monic irreducible polynomials with degree $1$ or $2$ is given by $x^{p^2}-x$, the product of all monic irreducible polynomials with degree $1$ or $3$ is given by $x^{p^3}-x$ and the product of all monic irreducible polynomials with degree $1$ is given by $x^{p}-x$. It follows that there are
$$\frac{p^2-p}{2}\text{ monic irreducible polynomials with degree } 2$$
and
$$\frac{p^3-p}{3}\text{ monic irreducible polynomials with degree } 3.$$
This happens because a monic irreducible polynomial $q(x)$ with degree $d$ defines a finite field $\mathbb{F}_{p^d}\simeq\mathbb{F}_p[x]/(q(x))$ over which $\alpha\to\alpha^p$ is a field homomorphism (Frobenius' homomorphism).
As an alternative, a monic polynomial is irreducible over $\mathbb{F}_p$ iff it has no roots in $\mathbb{F}_p$. Reducible monic polynomials have the form $(x-a) q(x)$ (with $q(x)$ being a monic, irreducible, second-degree polynomial) or $(x-a_1)(x-a_2)(x-a_3)$. There are $p\cdot\frac{p^2-p}{2}$ polynomials in the first case and $p+p(p-1)+\binom{p}{3}$ polynomials in the second case (accounting for $1$, $2$ or $3$ distinct roots in the field). The conclusion is the same as before.
A monic, reducible polynomial with degree $4$ can completely split in linear factors (there are $p+p(p-1)+\binom{p}{2}+\binom{p}{2}(p-2)+\binom{p}{4}$ polynomials with such a property, associated with $a_1^4,a_1^3 a_2,a_1^2 a_2^2, a_1 a_2 a_3^2, a_1 a_2 a_3 a_4$), or split as the product of two quadratic irreducible polynomials (there are $\binom{(p^2-p)/2}{2}+(p^2-p)/2$ cases), or split as the product of a quadratic factor and two linear factors (there are $\frac{p^2-p}{2}\left(p+\binom{p}{2}\right)$ cases), or split as the product of a cubic factor and a linear factor (there are $p\cdot\frac{p^3-p}{3}$ cases). It follows that the number of irreducible, monic polynomials with degree $4$ is $\frac{p^4-p^2+1}{4}$.
A useful generalization of the previous approach is:
Over $\mathbb{F}_p$, there are
$$ \frac{1}{k}\sum_{d\mid k} \mu\left(d\right)p^{k/d} $$
monic irreducible polynomials with degree $k$, with $\mu$ being Moebius' function.
Best Answer
A reducible monic polynomial is of the form $x^2+2bx+c$, where $b^2-c$ is a square, that is $\Delta=b^2-c\in\{0,1,4\}$.
For any of these cases, we can assign $b$ any value and determine $c$. So $15$.
In another way: a reducible monic polynomial has the form $(x-h)(x-k)$, where $h$ and $k$ are the roots. Five cases for $h=k$; ten cases for $h\ne k$, because $$ \binom{5}{2}=10 $$ (the order of the roots is irrelevant).
Another way. The field $F_{25}$ with $25$ elements is generated by any root of an irreducible polynomial; there are $25-5=20$ elements that generate $F_{25}$, but the minimal polynomial of any of these $20$ elements has two distinct roots. So we have $10$ irreducible polynomials.