Degree and Euclidean division of polynomials

For the definition and characterization of the polynomials over a field \K, see Polynomials over a field.

Definition of the degree of a polynomial

The degree of a polynomial P, written \deg P, is an element of \{-\infty\} \cup \N. The symbol -\infty is taken to have the usual properties of order and of addition relative to natural numbers.

The family (X^0, X^1, X^2, \ldots) is a \K-vector space basis of \K[X]. For any P \in \K[X], there exists an unique (a_0, a_1, \ldots) \in \K^\N, only finitely many of which are nonzero, such that P = \sum_n a_n X^n. If all the a_n are zero, that is, if P is the zero element of \K[X], then \deg P is defined as -\infty. If not all the a_n are zero, since only finitely many are nonzero, there is a greatest value of n such that a_n \neq 0_\K. Then \deg P is defined as this greatest value.

Elementary properties of the degree

The following are easily checked to hold for any polynomials P and Q (even when one or both are zero):

\deg (P + Q) \le \sup(\deg P, \deg Q)

if \deg P \neq \deg Q, then \deg (P + Q) = \sup(\deg P, \deg Q)

\deg PQ = \deg P + \deg Q

Euclidean division

The notion of the degree of a polynomial allows us to formulate the following property of Euclidean division:

For all polynomials A and B, with B nonzero, there exists exactly one pair of polynomials (Q, R) such that A = Q B + R with \deg R < \deg B.

For the proof, we fix the value of nonzero polynomial B, and recurse over the degree of A.

More specifically, B being given, we consider the following proposition dependent on n \in \{-\infty\} \cup \N:

\mathcal P(n) iff for all polynomials A such that \deg A \le n, there exist polynomials  Q, R, with \deg R < \deg B, such that A = Q B + R.

\mathcal P(-\infty) is trivially true (for \deg A \le -\infty means that A is zero, and Q = 0, R = 0 satisfies A = Q B + R with \deg R < \deg B).

Let us suppose \mathcal P(n) true for some n \in \{-\infty\} \cup \N, and consider a polynomial A the degree of which is less or equal to the successor of n, that is to 0 if n = -\infty, or n+1 otherwise.

If the degree of A is less or equal to n, then \mathcal P(n) applies and there exist the wanted Q and R.

If the degree of A is less than that of B, then we can directly write A = Q B + R with Q = 0 and R = A.

Remains the case in which \deg A is the successor of n.