linguistic:paraphrasing
Polynomials

Polynomials in a single variable x can be added, multiplied and factored into irreducible polynomials, which are the analogs of the prime numbers for integers. The greatest common divisor polynomial g (x) of two polynomials a (x) and b (x) is defined as the product of their shared irreducible polynomials, which can be identified using the Euclidean algorithm. The basic procedure is similar to that for integers. At each step k, a quotient polynomial q (x) and a remainder polynomial r (x) are identified to satisfy the recursive equation

where r (x) = a (x) and r (x) = b (x). Each quotient polynomial is chosen such that each remainder is either zero or has a degree that is smaller than the degree of its predecessor: deg < deg. Since the degree is a nonnegative integer, and since it decreases with every step, the Euclidean algorithm concludes in a finite number of steps. The last nonzero remainder is the greatest common divisor of the original two polynomials, a (x) and b (x).

For example, consider the following two quartic polynomials, which each factor into two quadratic polynomials

Dividing a (x) by b (x) yields a remainder r (x) = x + (2/3) x + (5/3) x − (2/3). In the next step, b (x) is divided by r (x) yielding a remainder r (x) = x + x + 2. Finally, dividing r (x) by r (x) yields a zero remainder, indicating that r (x) is the greatest common divisor polynomial of a (x) and b (x), consistent with their factorization.

Many of the applications described above for integers carry over to polynomials. The Euclidean algorithm can be used to solve linear Diophantine equations and Chinese remainder problems for polynomials; continued fractions of polynomials can also be defined.

The polynomial Euclidean algorithm has other applications, such as Sturm chains, a method for counting the zeros of a polynomial that lie inside a given real interval. This in turn has applications in several areas, such as the Routh–Hurwitz stability criterion in control theory.

Finally, the coefficients of the polynomials need not be drawn from integers, real numbers or even the complex numbers. For example, the coefficients may be drawn from a general field, such as the finite fields GF(p) described above. The corresponding conclusions about the Euclidean algorithm and its applications hold even for such polynomials.