GCD of polynomials

Definition 5.3.1. A polynomial with 1 as its leading coefficient is called a monic polynomial.

Definition 5.3.2. Let g(x) and f(x) two non-zero polynomials in 𝕂[x]. We define the greatest common divisor between g(x) and f(x) and indicate as GCD(g(x), f(x)) or simply by (g(x) and f(x)), the polynomial d(x) such that

• d(x) | f(x),   d(x)| g(x)

• if d'(x) | f(x), d'(x) | g(x),   then   d'(x) | d(x)

The same euclidean algorithm used for finding the GCD of two integers can be used for polynomials and guarantees the existence of a GCD of two non-zero polynomials. One of the conditions that we place on a greatest common divisor of two polynomials is that it be monic. Without this condition, the greatest common divisor of two polynomials would not be unique.

Proposition 5.3.3. (Euclid's Algorithm) Let g(x) and f(x) two non-zero polynomials in K[x], we successively divide in the following way

Applying the same procedure as in ℤ, the last non-null remainder in the sequence of the divisions is the gcd.

Example 5.3.4 Find the gcd of x² + 7x + 6 and x² − 5x − 6:

Since 12x + 12 is the last nonzero remainder, it is a GCD of the original polynomials, and the monic GCD is x + 1.

Example 5.3.5 Compute the greatest common divisor of the polynomials f(x) = x³ + 1, g(x) = x² + 1 on ℚ. We have

and so GCD(f(x), g(x)) = 2.

Definition 5.3.6. Two elements g(x) and f(x) ∈ K[x] such that f(x) and g(x) are said associates if there exists an invertible element a of K[x] such that

The relation of being associates is an equivalence relation and in each equivalence class there is exactly one monic polynomial, which we regard as the canonical representative of the class. For example 4x² + 8x² + 4 is associated to the monic polynomial x² + 2x + 1. Any polynomial is an associate of exactly one monic polynomial.

Let d'(x) and d(x) two elements verifying both the condition of being gcd between g(x) and f(x). It is easy to see that they are associates. Then we can say that the greatest common divisor between g(x) and f(x) is the unique monic polynomial.

The Bezout's relation holds true for polynomials as well. If g(x) and f(x) are in K[x], let d(x) their gcd then there exist h(x) and k(x) ∈ K[x] such that

Definition 5.3.7. Two polynomials are said coprime if

Definition 5.3.8. A nonconstant and non-invertible polynomial f(x) ∈ K[x] is said to be irreducible over K, if

If it is not irreducible the polynomial is said reducible. □

The definition says that f is irreducible if no decomposition f = gh into non-zero, non-units is possible. To phrase it in terms of reducibility, a polynomial f is reducible if there exists a decomposition f = gh such that g and h are non-zero non-units.
This means that for *every* possible factorization in terms of two polynomials g(x) and h(x), one of those must be invertible; it's not enough to find one factorization i.e. 2x² − 8 = 2(x² − 4) in ℚ[x] but we've also 2x² − 8 = 2(x − 2)(x + 2) and the polynomials 2(x + 2) and x − 2 are not invertible. However 2(x² − 4) is reducible in ℤ[x] since neither 2 nor (x² − 4) is not a unit in ℤ.

Example. f(x) = x² + x + 1 is irreducible over ℚ. If we take any unit in ℚ, say 5/3, the only possible factorization would be f(x) = a ⋅ b where a = 3/5 (x² + x + 1) and b = 5/3.  ■

Example 5.3.8. The polynomial x² − 2 is reducible over ℝ as

and x + 2 and x − 2 are irreducible polynomials with coefficients in ℝ, while it is irreducible over ℚ, as the polynomial x² − 2 has no roots in ℚ, that is,

The polynomial x² + 1 is reducible over ℂ and

is a factorisation into irreducibles, but it is irreducible over ℝ and over ℚ as x² + 1 has no roots in ℝ, and therefore it cannot factor (into linear factors). ■

In the polynomial ring K[x] where K is a field, the invertible elements consist of all polynomials of degree zero, i.e. the factors are the elements of the field itself.

Example 5.3.9. Consider the polynomial x² − 2. Note that x² − 2 has no zeroes over ℚ. This is the same as saying t hat √2 is irrational, so the polynomial cannot decomposed in terms of a linear factor (see Ruffini's theorem. If x² − 2 is reducible then we may write x² − 2 = g(x)h(x), where the degree of g(x) and h(x) is less than two. As the degree ofthe LHS is two, the only possibility is that both g(x) and h(x) have degree one. In this case x² − 2 has a zero in ℚ, a contradiction. Thus x² − 2 is irreducible over ℚ.On the other hand, √2 ∈ ℝ so that x² − 2 is reducible over ℝ, x² − 2 = (x − √2)(x + √2).

So 2x + 4 = (2)(x + 2) with the first factor invertible in ℝ[x], is not a factorization for getting 2x + 4 reducible. In fact 2x + 4 is irreducible, as are all linear polynomials over a field.

In ℤ[x], where the only invertible things are 1 and −1, both 2 and x + 2 are non-invertible, so here, 2x + 4 is reduciblle since both factors in (2)(x + 2) are non-invertible in ℤ[x].

In the definition above K could be either a field or a simple ring but if F is a field then we could be the following definition:

A nonconstant polynomial is said to be irreducible over the field F if it cannot be factored in F[x] into a product of polynomials of lower degree. It is said to be reducible over F if such a factorization exists.

When we are not dealing with a field this is not true: Consider 4 ∈ ℤ[x]. It cannot be expressed as the product of two polynomials of lower degree. But it is not irreducible, since 4 = 2×2.

As another example x² + 5 is irreducible in ℤ₁₁ because x² + 5 = (2)(6x² + 8) and 2 is the unit in K[x].

Definition 5.3.10. A non-zero and non-invertible polynomial f(x) ∈ K[x] is said to be prime if, every time that f(x) divides a product g(x)h(x) (with g(x), h(x) ∈ K[x]), then it divides one of the two factors.

Irreducible polynomials play a role in the factorization of polynomials corresponding to the role that prime integers play in the factorization of integers.

Proposition 5.3.11. A polynomial in K[x] is irreducible iff is prime.

Theorem 5.3.12 (Unique Factorization Theorem) Every polynomial f(x) of degree ≥ 1 in K[x] can be factorised as a finite product of irreducible elements. Such a factorisation is unique, that is

p_i(x) and q_j(x) are irreducible in K[x], then s = t and there exists a biunique correspondence between {p₁(x) p₂(x) ... p_s(x)} and {q₁(x) q₂(x) ... q_t(x)} such that if q_j(x) corresponds to p_i(x), then p_i(x) is associated to q_j(x). □