Irreducible Polynomial (original) (raw)

Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology

Alphabetical Index New in MathWorld

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] (i.e., polynomials f(x) with rational coefficients), f(x) is said to be irreducible if there do not exist two nonconstant polynomials g(x) and h(x) in x with rational coefficients such that

f(x)=g(x)h(x)

(Nagell 1951, p. 160). Similarly, in the finite field GF(2), x^2+x+1 is irreducible, but x^2+1 is not, since (x+1)(x+1)=x^2+2x+1=x^2+1 (mod 2).

Irreducible polynomial checking is implemented in the Wolfram Language as IrreduciblePolynomialQ[_poly_].

In general, the number of irreducible polynomials of degree n over the finite field GF(q) is given by

L_q(n)=1/nsum_(d|n)mu(n/d)q^d,

where mu(n) is the Möbius function.

The number of irreducible polynomials of degree n over GF(2) is equal to the number of n-bead fixed aperiodic necklaces of two colors and the number of binary Lyndon words of length n. The first few numbers of irreducible polynomial (mod 2) for n=1, 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.

The possible polynomial orders of nth 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).

See also

Eisenstein's Irreducibility Criterion, Field, Finite Field, Lyndon Word, Necklace,Polynomial, Primitive Polynomial

Explore with Wolfram|Alpha

References

Marsh, R. Tables of Irreducible Polynomials of GF(2) through Degree 19. Washington, DC: U. S. Dept. Commerce, 1957.Nagell, T. "Irreducibility of the Cyclotomic Polynomial." §47 in Introduction to Number Theory. New York: Wiley, pp. 160-164, 1951.Ruskey, F. "Information on Primitive and Irreducible Polynomials." http://www.theory.csc.uvic.ca/~cos/inf/neck/PolyInfo.html.Sloane, N. J. A. Sequences A001037/M0116 and A059912 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. Figure M0564 in The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Referenced on Wolfram|Alpha

Irreducible Polynomial

Cite this as:

Weisstein, Eric W. "Irreducible Polynomial." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/IrreduciblePolynomial.html

Subject classifications