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]](/images/equations/IrreduciblePolynomial/Inline1.svg)
(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).
Irreducible polynomial checking is implemented in the Wolfram Language as IrreduciblePolynomialQ[poly].
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, ... (OEIS A001037).
The following table lists the irreducible polynomials (mod 2) of degrees 1 through
5.
 | irreducible polynomials |
| 1 |  ,  |
| 2 |  |
| 3 |  ,  |
| 4 |  ,
 ,
 |
| 5 |  ,  ,  ,  ,  ,  |
The possible polynomial orders of 
th degree irreducible polynomials over the finite
field GF(2) listed in ascending order are given by 1; 3; 7; 5, 15; 31; 9, 21,
63; 127; 17, 51, 85, 255; 73, 511; ... (OEIS A059912).
