# Irreducible polynomial

In mathematics, an irreducible polynomial is, roughly speaking, a non-constant polynomial that may not be factored into the product of two non constant polynomials. The property of irreducibility depends on the field or ring to which the coefficients are considered to belong. For example, the polynomial x2 - 2 is irreducible if the coefficients 1 and -2 are considered as integers and factors as $(x-\sqrt{2})(x+\sqrt {2})$ if the coefficients are considered as real numbers. One says "the polynomial x2 - 2 is irreducible over the integers but not over the reals".

A polynomial that is not irreducible is sometimes said to be reducible.[1][2] However this term must be used with care, as it may refer to other notions of reduction.

Irreducible polynomials appear naturally in polynomial factorization and algebraic field extensions.

It is helpful to compare irreducible polynomials to prime numbers: prime numbers (together with the corresponding negative numbers of equal magnitude) are the irreducible integers. They exhibit many of the general properties of the concept of 'irreducibility' that equally apply to irreducible polynomials, such as the essentially unique factorization into prime or irreducible factors.

## Definition

If F is a field, a non-constant polynomial is irreducible over F if its coefficients belong to F and it cannot be factored into the product of two non-constant polynomials with coefficients in F.

A polynomial with integer coefficients, or, more generally, with coefficients in a unique factorization domain R is sometimes said to be irreducible over R if it is an irreducible element of the polynomial ring (a polynomial ring over a unique factorization domain is also a unique factorization domain), that is, it is not invertible, nor zero and cannot be factored into the product of two non-invertible polynomials with coefficients in R. Another definition is frequently used, saying that a polynomial is irreducible over R if it is irreducible over the field of fractions of R (the field of rational numbers, if R is the integers). Both definitions generalize the definition given for the case of coefficients in a field, because, in this case, the non constant polynomials are exactly the polynomials that are non-invertible and non zero.

## Simple examples

The following six polynomials demonstrate some elementary properties of reducible and irreducible polynomials:

$p_1(x)=x^2+4x+4\,={(x+2)(x+2)}$,
$p_2(x)=x^2-4\,={(x-2)(x+2)}$,
$p_3(x)=9x^2-3\,=3(3x^2-1)\,=3(x\sqrt{3}-1)(x\sqrt{3}+1)$,
$p_4(x)=x^2-4/9\,=(x-2/3)(x+2/3)$,
$p_5(x)=x^2-2\,=(x-\sqrt{2})(x+\sqrt{2})$,
$p_6(x)=x^2+1\,={(x-i)(x+i)}$.

Over the ring $\mathbb Z$ of integers, the first three polynomials are reducible (the third one is reducible because the factor 3 is not invertible in the integers), the last two are irreducible. (The fourth, of course, is not a polynomial over the integers.)

Over the field $\mathbb Q$ of rational numbers, the first two and the fourth polynomials are reducible, but the other three polynomials are irreducible (as a polynomial over the rationals, 3 is a unit, and, therefore, does not count as a factor).

Over the field $\mathbb R$ of real numbers, the first five polynomials are reducible, but $p_6(x)$ is still irreducible.

Over the field $\mathbb C$ of complex numbers, all six polynomials are reducible.

## Over the complexes

Over the complex field, and, more generally, over an algebraically closed field, a univariate polynomial is irreducible if and only if its degree is one. This is the Fundamental theorem of algebra in the case of complexes and, in general, the definition of "algebraically closed".

It follows that every nonconstant univariate polynomial can be factored as

$a(x-z_1)\cdots (x-z_n)$

where $n$ is the degree, $a$ the leading coefficient and $z_1,\dots,z_n$ the zeros of the polynomial (not necessarily distincts).

There are irreducible multivariate polynomials of every degree over the complexes. For example, the polynomial

$x^n+y^n-1,$

which defines Fermat curve, is irreducible for every positive n.

## Over the reals

Over the field of reals, the degree of an irreducible univariate polynomial is either one or two. More precisely, the irreducible polynomials are the polynomials of degree one and the quadratic polynomials $ax^2+bx+c$ that have a negative discriminant $b^2-4ac.$

It follows that every non-constant univariate polynomial can be factored as a product of polynomials of degree at most two. For example, $x^4 + 1$ factors over the real numbers as $(x^2 + \sqrt{2}x + 1)(x^2 - \sqrt{2}x + 1),$ and it cannot be factored further, as both factors have a negative discriminant: $(\pm \sqrt{2})^2-4=-2<0.$

As in the complex case, there are irreducible polynomials in two (or more) variables of every degree.

## Unique factorization property

Every polynomial over a field F may be factored in a product of a non-zero constant and a finite number of irreducible (over F) polynomials. This decomposition is unique up to the order of the factors and the multiplication of the factors by non-zero constants whose product is 1.

Over a unique factorization domain the same theorem is true, but is more accurately formulated by using the notion of primitive polynomial. A primitive polynomial is a polynomial over a unique factorization domain, such that 1 is a greatest common divisor of its coefficients.

Let F be a unique factorization domain. A non-constant irreducible polynomial over F is primitive. A primitive polynomial over F is irreducible over F if and only if it is irreducible over the field of fractions of F. Every polynomial over F may be decomposed into the product of a non zero constant and a finite number of non-constant irreducible primitive polynomials. The non-zero constant may itself be decomposed into the product of a unit of F and a finite number of irreducible elements of F. Both factorizations are unique up to the order of the factors and the multiplication of the factors by a unit of F

This is this theorem which motivates that the definition of irreducible polynomial over a unique factorization domain often suppose that the polynomial is non-constant.

All algorithms for factoring polynomials over the integers and over the rational numbers use this this result (see Factorization of polynomials).

## Over the integers

The irreducibility of a polynomial over the integers $\mathbb Z$ is related to that over the field $\mathbb F_p$ of $p$ elements (for a prime $p$). In particular, if a univariate polynomial f over $\mathbb Z$ is irrreducible over $\mathbb F_p$ for some prime $p$ that does not divide the leading coefficient of f (the coefficient of the higher power of the variable), then f is irreducible over $\mathbb Z$. Eisenstein's criterion is a variant of this property where irreducibility over $p^2$ is also involved.

The converse, however, is not true, there are polynomials of arbitrary large degree that are irreducible over the integers and reducible over every finite field.[3] A simple example of such a polynomial is $x^4+1,$ which is irreducible over the integers and reducible over every finite field.

The relationship between irreducibility over the integers and irreducibility modulo p is deeper than the previous result: to date, all implemented algorithms for factorization and irreducibility over the integers and over the rational numbers use the factorization over finite fields as subroutine.

## Algorithms

The unique factorization property of polynomials does not mean that the factorization of a given polynomial may always be computed. Even the irreducibility of a polynomial may not always been proved by a computation: there are fields over which no algorithm can exist for deciding the irreducibility of any polynomial.[4]

Algorithms for factoring polynomials and deciding irreducibility are known and implemented in computer algebra systems for polynomials over the integers, the rational numbers, finite fields and finitely generated field extension of these fields. All these algorithms use the algorithms for factorization of polynomials over finite fields.

## Field extension

If an univariate polynomial p has a root (in some field extension) which is also a root of an irreducible polynomial q, then p is a multiple of q, and thus all roots of q are roots of p; this is Abel's irreducibility theorem. This implies that the roots of an irreducible polynomial may not be distinguished through algebraic relations. This result is one of the starting points of Galois theory, which has been introduced by Évariste Galois to study the relationship between the roots of a polynomial.

The existence of irreducible polynomials of degree greater than one (without zeros in the original field) historically motivated the extension of that original number field so that even these polynomials can be reduced into linear factors: from rational numbers$\mathbb{Q}$ ), to the real subset of the algebraic numbers$\mathcal{A}\cap\mathbb{R}$ ), and finally to the algebraic subset of the complex numbers$\mathcal{A}\cap\mathbb{C}$ ). After the invention of calculus those latter two subsets were later extended to all real numbers$\mathbb{R}$ ) and all complex numbers$\mathbb{C}$ ).

For algebraic purposes, the extension from rational numbers to real numbers is too "radical": it introduces transcendental numbers, which are not the solutions of algebraic equations with rational coefficients. These numbers are not needed for the algebraic purpose of factorizing polynomials (but they are necessary for the use of real numbers in analysis). The set of algebraic numbers$\mathcal{A}$ ) is the algebraic closure of the rationals, and contains the roots of all polynomials (including i for instance). This is a countable field and is strictly contained in the complex numbers – the difference being that this field ( $\mathcal{A}$ ) is "algebraically complete" (as are the complex numbers, $\mathbb{C}$ ) but not analytically complete since it lacks the aforementioned transcendentals.

The above paragraph generalizes in that there is a purely algebraic process to extend a given field F with a given polynomial $p(x)$ to a larger field where this polynomial $p(x)$ can be reduced into linear factors. The study of such extensions is the starting point of Galois theory.

## Over an integral domain

If R is an integral domain, an element f of R which is neither zero nor a unit is called irreducible if there are no non-units g and h with f = gh. One can show that every prime element is irreducible;[5] the converse is not true in general but holds in unique factorization domains. The polynomial ring F[x] over a field F (or any unique-factorization domain) is again a unique factorization domain. Inductively, this means that the polynomial ring in n indeterminants (over a ring R) is a unique factorization domain if the same is true for R.