A polynomial is said to be irreducible if it cannot be factored into nontrivial polynomials over the same field.
For example, in the field of rational polynomials ![Q[x]](http://mathworld.wolfram.com/images/equations/IrreduciblePolynomial/inline1.gif)
(i.e., polynomials 
with rational coefficients), 
is said to be
irreducible if there do not exist two nonconstant polynomials 
and 
in 
with rational coefficients
such that
(Nagell 1951, p. 160). Similarly, in the finite field GF(2), 
is irreducible, but
is not, since 
(mod 2). A polynomial can be tested to see if it is irreducible using the Mathematica function
IrreducibleQ[p_,n_] := SameQ[Factor[p, Modulus->n], Expand[p]]
In general, the number of irreducible polynomials of degree 
over the finite field GF(
) is given by
where 
is the Möbius function.
The number of irreducible polynomials of degree 
over GF(2) is equal
to the number of 
-bead fixed aperiodic
necklaces of two colors and the number
of binary Lyndon words of length
. The first few numbers of irreducible
polynomial (mod 2) for 
, 2, ... are
2, 1, 2, 3, 6, 9, 18, ... (Sloane's A001037). The following table lists the irreducible polynomials
(mod 2) of degrees 1 through 5.
 | irreducible
polynomials |
| 1 |  ,  |
| 2 |  |
| 3 |  ,  |
| 4 |  ,  ,
 |
| 5 |  ,  ,
 ,  ,
 ,  |
