Greatest Common Divisor

Let \( p_1(x) \) and \( p_2(x) \) be polynomials. The GCD of \( p_1(x) \) and \( p_2(x) \), denoted as \( \text{GCD}(p_1(x), p_2(x)) \), is the polynomial of the highest degree that divides both \( p_1(x) \) and \( p_2(x) \) without remainder.

If direct factorization of \( p_1(x) \) and \( p_2(x) \) is challenging, alternative methods such as the Euclidean Division Algorithm may be employed. Consider the Euclidean Division of \( p_1(x) \) by \( p_2(x) \), expressed as \( p_1(x) = q(x)p_2(x) + r(x) \), where \( q(x) \) is the quotient and \( r(x) \) is the remainder. It follows that, any common divisor of \( p_1(x) \) and \( p_2(x) \) is necessarily a divisor of \( r(x) \).

Proof:

Consider polynomials \( p_1(x) \) and \( p_2(x) \). If a polynomial \( d(x) \) divides both \( p_2(x) \) and the remainder \( r(x) \), then \( d(x) \) must also divide \( p_1(x) \). This is evident from the equation \( p_1(x) = q(x)\color{red}p_2(x) \color{black}+ \color{red}r(x)\).

Moreover, since \( r(x) = \color{red}p_1(x)\color{black} - q(x)\color{red}p_2(x) \), any factor common to \( p_1(x) \) and \( p_2(x) \) must divide \( r(x) \) as well. This means that all common factors of \( p_1(x) \) and \( p_2(x) \) are also common to \( p_2(x) \) and \( r(x) \), completing the mutual relationship between their common factors. \(\blacksquare\)

The conclusion from this mutual relationship is that the GCD of \( p_1(x) \) and \( p_2(x) \) can be found by instead considering the GCD of \( p_2(x) \) and \( r(x) \), and this substitution can be iteratively applied as the Euclidean Algorithm progresses.

Euclidean Algorithm for GCD of two polynomials

To determine the greatest common divisor (GCD) of two polynomials \( p_1(x) \) and \( p_2(x) \), apply the Euclidean Algorithm as follows:

Perform long division on \( p_1(x) \) by \( p_2(x) \) to find a quotient \( q_1(x) \) and a remainder \( r_1(x) \), such that \( p_1(x) = q_1(x)p_2(x) + r_1(x) \), with \( r_1(x) \) of lower degree than \( p_2(x) \).
Divide \( p_2(x) \) by the new remainder \( r_1(x) \) to obtain a quotient \( q_2(x) \) and remainder \( r_2(x) \), so \( p_2(x) = q_2(x)r_1(x) + r_2(x) \), where \( r_2(x) \) is of lower degree than \( r_1(x) \).
Continue the process by dividing the last non-zero remainder by the current remainder. For the third iteration, it would be \( r_1(x) = q_3(x)r_2(x) + r_3(x) \), with each new remainder \( r_i(x) \) having a lower degree than the previous remainder \( r_{i-1}(x) \).
Proceed iteratively \( n \) times until the division yields a remainder \( r_{n}(x) \) that is either a constant or identically zero, with the previous step being \( r_{n-2}(x) = q_{n}(x)r_{n-1}(x) + r_{n}(x) \).
The algorithm concludes when the remainder \( r_{n}(x) \) is zero or a constant. If \( r_{n}(x) \) is zero, then \( r_{n-1}(x) \) is the GCD. If \( r_{n}(x) \) is a non-zero constant, \( p_1(x) \) and \( p_2(x) \) share no common divisors other than units, indicating they are relatively prime.

Example

Let \( p_1(x) = x^4 - 7x^3 + 17x^2 - 17x + 6 \) and \( p_2(x) = x^3 - 7x^2 + 14x - 8 \). We seek the greatest common divisor of \( p_1(x) \) and \( p_2(x) \).

Solution:

We begin by dividing \( p_1(x) \) by \( p_2(x) \):

\[ \frac{x^4 - 7x^3 + 17x^2 - 17x + 6}{x^3 - 7x^2 + 14x - 8} \]

The quotient is \( x \) and the remainder is \( 3x^2 - 9x + 6 \).

We proceed by dividing \( p_2(x) \) by the remainder from the previous division:

\[ \frac{x^3 - 7x^2 + 14x - 8}{3x^2 - 9x + 6} \]

To simplify the division, we notice that \( 3x^2 - 9x + 6 \) is \( 3 \) times the polynomial \( x^2 - 3x + 2 \). We can factor out the constant \( 3 \) to obtain \( x^2 - 3x + 2 \).

Upon dividing \( p_2(x) \) by \( x^2 - 3x + 2 \), we find that the quotient is \( x - 4 \) and the remainder is \( 0 \).

Therefore, \( x^2 - 3x + 2 \), which factors as \( (x - 1)(x - 2) \), is the Greatest Common Divisor of \( p_1(x) \) and \( p_2(x) \).

Theorem:

For any two polynomials \( p(x) \) and \( q(x) \), if there exist polynomials \( u(x) = ap(x) + bq(x) \) and \( v(x) = cp(x) + dq(x) \) with coefficients \( a, b, c, d \in \mathbb{R} \) and \( ad - bc \neq 0 \), then the greatest common divisor (GCD) of \( u(x) \) and \( v(x) \) is the same as the GCD of \( p(x) \) and \( q(x) \).

Proof:

The condition \( u(x) = ap(x) + bq(x) \) and \( v(x) = cp(x) + dq(x) \) implies that any common factor of \( p(x) \) and \( q(x) \) is also a factor of \( u(x) \) and \( v(x) \), since common factors are distributive over polynomial addition.

Moreover, if we consider the expressions for \( p(x) \) and \( q(x) \) derived from \( u(x) \) and \( v(x) \), we have:

\[ p(x) = \frac{du(x) - bv(x)}{ad - bc} \quad \text{and} \quad q(x) = \frac{cv(x) - au(x)}{bc - ad} \]

It follows from these equations that any common factor of \( u(x) \) and \( v(x) \) is also a common factor of \( p(x) \) and \( q(x) \).

Consequently, the set of common factors of \( u(x) \) and \( v(x) \) coincides with the set of common factors of \( p(x) \) and \( q(x) \), and thus their greatest common divisors are equivalent. This result allows the use of linear combinations \( u(x) \) and \( v(x) \) to simplify the process of finding the GCD of \( p(x) \) and \( q(x) \).

Example

Given polynomials \( p(x) = 2x^4 + x^3 - x - 2 \) and \( q(x) = 6x^4 + x^3 + x^2 - 4x - 4 \).

Defining \( u(x) = 3p(x) - q(x) \) results in \( u(x) = 2x^3 - x^2 - x - 2 \), and defining \( v(x) = q(x) - 2p(x) \) gives \( v(x) = x^2 - x - 2 \). These choices for \( u(x) \) and \( v(x) \) ensure \( u(x) \) has no \( x^4 \) term and \( v(x) \) has no constant term.

Calculating the GCD of \( u(x) \) and \( v(x) \) yields \( 2x^3 - x^2 - x - 2 = (x - 1)(2x^2 + x + 2) \).

Therefore, the GCD of \( p(x) \) and \( q(x) \) is also \( (x - 1)(2x^2 + x + 2) \) based on the theorem that linear combinations of \( p(x) \) and \( q(x) \) maintain the GCD.

Prime and Composite Polynomials

A polynomial is termed prime if it is non-factorable over the set of polynomials with coefficients in a given field, meaning it cannot be expressed as the product of two non-constant polynomials in that field. Conversely, if a polynomial can be factored as such, it is composite. For instance, \( (x+1) \) and \( x^2+1 \) are prime polynomials in the field of real numbers, whereas \( x^2(x+1) \) and \( (x^2+1)(x-2) \) are composite since they can be factored into the product of lower-degree polynomials.

Two polynomials are coprime if they share no common polynomial factors except for constant factors, which are disregarded. For example, \( 2(x^2+1) \) and \( 4(x+1) \) are coprime to one another since any common factor would be a non-constant polynomial, which they do not possess.

Given polynomials \( p(x) \), \( q(x) \), and \( r(x) \), if \( p(x) \) is a factor of \( q(x)r(x) \) and \( p(x) \) is coprime to \( q(x) \), it must be that \( p(x) \) is a factor of \( r(x) \). This is due to the fact that any factor of \( q(x)r(x) \) that is not a factor of \( q(x) \) must necessarily be a factor of \( r(x) \) by virtue of \( p(x) \) and \( q(x) \) being coprime.

Little Bezout's Identity Theorem:

For any two polynomials \( p(x) \) and \( q(x) \), there exist polynomials \( A(x) \) and \( B(x) \) such that \( A(x)p(x) + B(x)q(x) = \text{gcd}(p(x), q(x)) \), or equivalently, \( A(x)p(x) + B(x)q(x) = 1 \) if \( p(x) \) and \( q(x) \) are coprime.

Proof:

Suppose the gcd of \( p(x) \) and \( q(x) \) exists. By employing the Euclidean Algorithm to find the gcd, we obtain a sequence of equations:

\[ \begin{align*} p &= q_1q + R_1, \\ q &= q_2R_1 + R_2, \\ R_1 &= q_3R_2 + R_3, \\ &\ \vdots \\ R_{n-2} &= q_nR_{n-1} + R_n. \end{align*} \]

It follows that \( \text{gcd}(p, q) = \text{gcd}(q, R_1) = \text{gcd}(R_1, R_2) = \ldots = \text{gcd}(R_{n-1}, R_n) \).

Now, we have that \( p = q_1q + R_1 \) implies \( R_1 = p - q_1q \), and \( q = q_2R_1 + R_2 \) can be rewritten as \( R_2 = q - q_2R_1 \). Substituting for \( R_1 \), we have \( R_2 = q - q_2(p - q_1q) = -q_2p + (1 + q_1q_2)q \). Repeating this substitution process for all remainders, we can express \( R_i \) as a linear combination of \( p \) and \( q \).

Eventually, the last non-zero remainder \( R_n \) is the gcd of \( p \) and \( q \), and it is expressed as a linear combination \( A(x)p(x) + B(x)q(x) \), where \( A(x) \) and \( B(x) \) are found from the recursive substitution of remainders in terms of \( p \) and \( q \).

If the gcd is not a constant, the equation \( A(x)p(x) + B(x)q(x) = \text{gcd}(p(x), q(x)) \) holds. If \( p \) and \( q \) are coprime, then the gcd is 1, and we have \( A(x)p(x) + B(x)q(x) = 1 \).

Thus, by the process of back-substitution in the Euclidean Algorithm, \( A(x) \) and \( B(x) \) can be determined, completing the proof of Little Bezout's Identity.