Degree and Euclidean division of polynomials

olivierd

Aug 22, 2018 3 min read

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$ .