# 7.5: Divisibility and Polynomials

- Page ID
- 99094

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\id}{\mathrm{id}}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\kernel}{\mathrm{null}\,}\)

\( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\)

\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\)

\( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)We apply some of the ideas on divisibility introduced in earlier sections of this chapter to polynomials with real coefficients, \(\mathbb{R}[x]\). This requires us to treat polynomials algebraically. We begin by formally defining operations on \(\mathbb{R}[x]\). Let \(f, g \in \mathbb{R}[x]\), \[f(x)=\sum_{n=0}^{N} a_{n} x^{n}\] and \[g(x)=\sum_{m=0}^{M} b_{m} x^{m} .\] So \(f\) is a polynomial of degree at most \(N\) and \(g\) is a polynomial of degree at most \(M\). In order to simplify our expressions, we subscribe to the convention that for the polynomials \(f\) and \(g, a_{n}=0\) for all \(n>N\), and \(b_{m}=0\) for all \(m>M\). That is, we may consider a polynomial as a power series in which all but finitely many of the coefficients equal 0 .

REMARK. If a polynomial is identically equal to a non-zero constant, we say that the polynomial has degree zero. If the polynomial is identically zero, we do not define its degree. This is a notational convenience: a polynomial of degree 0 is a non-zero constant.

We define addition and multiplication in \(\mathbb{R}[x]\) by \[f(x)+g(x):=\sum_{i=0}^{\max (M, N)}\left(a_{i}+b_{i}\right) x^{i}\] and \[f(x) \cdot g(x):=\sum_{i=0}^{M+N}\left(\sum_{j=0}^{i} a_{j} \cdot b_{i-j}\right) x^{i} .\] You should confirm that \(0 \in \mathbb{R}[x]\) is the additive identity in \(\mathbb{R}[x]\), and \(1 \in \mathbb{R}[x]\) is the multiplicative identity in \(\mathbb{R}[x]\). You should also verify that addition and multiplication in \(\mathbb{R}[x]\) are

(1) associative

(2) commutative

(3) distributive (i.e. multiplication distributes over addition).

We shall prove that a version of the Division Algorithm holds for polynomials. Indeed, it is the reason that long division of polynomials is essentially similar to division of integers.

THEOREM 7.21. Division Algorithm If \(f, g \in \mathbb{R}[x]\), and \(g \neq 0\), then there are unique polynomials \(q\) and \(r\) such that \[f=q \cdot g+r\] and either \(r=0\) or the degree of \(r\) is less than the degree of \(g\). Discussion. We argue first for the existence of a quotient and remainder satisfying the statement of the theorem. We let \(g\) be an arbitrary real polynomial and argue by induction on the degree of \(f\) - for this particular divisor \(g\). The induction principle will yield the result for the divisor \(g\) and any dividend. Since \(g\) is an arbitrary real polynomial, the existence of a quotient and remainder is guaranteed for any divisor and dividend. Uniqueness is proved directly.

Proof. Let \(g \in \mathbb{R}[x]\). If \(g\) is a constant, then \(q(x)=(1 / g(x))(f(x))\) and \(r=0\) satisfy the statement of the theorem. Furthermore, any remainder must be the zero polynomial, since it is impossible to have degree smaller than the degree of \(g\). Hence, \(q(x)=(1 / g(x))(f(x))\) is the unique quotient which satisfies the Division Algorithm.

Let \(g\) be a polynomial of degree greater than 0 . We prove the result for all possible \(f\) (for this particular \(g\) ) by induction on the degree of \(f\). Let \(M\) be the degree of \(g\) and \(N\) be the degree of \(f\).

Base case: \(N<M\)

Then \(q=0\) and \(r=f\) satisfy the conclusion of the theorem.

Induction step: Let \(N \geq M\) and assume that the result holds for all polynomials of degree less than \(N\). We show that it holds for \(f \in \mathbb{R}[x]\) of degree \(N\). We assume that \[f(x)=\sum_{n=0}^{N} a_{n} x^{n}\] where \(a_{n} \in \mathbb{R}\) (for \(\left.0 \leq n \leq N\right)\) and \(a_{N} \neq 0\). Let \[g(x)=\sum_{m=0}^{M} b_{m} x^{m}\] where \(b_{m} \in \mathbb{R}\) (for \(0 \leq m \leq M\) ) and \(b_{M} \neq 0\). Let \[h(x)=\left(\frac{a_{N}}{b_{M}}\right) x^{(N-M)} .\] Then the degree of \(f-h \cdot g\) is less than \(N\) or \(f-h \cdot g\) is identically 0 . So there is \(s \in \mathbb{R}[x]\) such that \[f=h \cdot g+s\] where \(s=0\) or the degree of \(s\) is less than \(N\). If \(s=0\), then let \(q=h\) and \(r=0\).

Otherwise, by the induction hypothesis, there is some polynomial \(\bar{q}\) such that \[s=\bar{q} \cdot g+r\] where \(r=0\) or the degree of \(r\) is less than \(M\). Thus \[f=h g+s=h g+\bar{q} g+r=(h+\bar{q}) g+r .\] If we let \(q=h+\bar{q}\) then \[f=q g+r .\] So, by the principle of induction, for any \(f \in \mathbb{R}[x]\), there are \(q\) and \(r\) such that \[f=q \cdot g+r .\] Since \(g\) was an arbitrary polynomial of degree greater than 0 , the result holds for all \(f\) and \(g\).

We prove that \(q\) and \(r\) are unique. Let \[f=q g+r=\bar{q} g+\bar{r}\] where the remainders, \(r\) and \(\bar{r}\), have degree less than the degree of \(g\) or are the 0 polynomial. Then \[\begin{gathered} q g+r-(\bar{q} g+\bar{r})= \\ (q-\bar{q}) g+(r-\bar{r})=0 . \end{gathered}\] Let \(Q=q-\bar{q}\) and \(R=r-\bar{r}\). Assume that \(Q \neq 0\). Then the degree of \(Q \cdot g\) is no less than the degree of \(g\). However the remainders \(r\) and \(\bar{r}\) have degree less than the degree of \(g\), or are the 0 polynomial. Thus the degree of \(R\) is strictly less than the degree of \(g\), or \(R=0\). The sum of two polynomials of different degree cannot be identically 0 . Hence it is impossible that \(Q \neq 0\). If \(Q=0\) then \(R=0\). Therefore \[q=\bar{q}\] and \[r=\bar{r}\] and the quotient and remainder are unique.

COROLLARY 7.22. If \(f \in \mathbb{R}[x]\) and \(x_{0} \in \mathbb{R}\), then there is \(q \in \mathbb{R}[x]\) such that \[f(x)=\left(x-x_{0}\right) \cdot q(x)+f\left(x_{0}\right) .\] ProOF. Apply the Division Algorithm with \(g(x)=x-x_{0}\). Then the remainder \(r\) is of degree 0 , or identically zero, so is constant, and evaluating \[f(x)=\left(x-x_{0}\right) q(x)+r(x)\] at \(x=x_{0}\) gives \(r(x)=f\left(x_{0}\right)\). Therefore \[f(x)=\left(x-x_{0}\right) q(x)+f\left(x_{0}\right) .\] We use these results to prove an algebraic property of polynomials.

DEFINITION. Ideal If \(I \subseteq \mathbb{R}[x]\) and \(I \neq \emptyset\), then we call \(I\) an ideal of \(\mathbb{R}[x]\) provided the following conditions are satisfied:

(1) If \(f, g \in I\) then \(f+g \in I\).

(2) If \(f \in I\) and \(g \in \mathbb{R}[x]\) then \(f \cdot g \in I\).

An ideal of \(\mathbb{R}[x]\) is a set that is closed under addition of elements in the ideal, and multiplication by all elements of \(\mathbb{R}[x]\), whether or not they are in the ideal. If you look closely at the definition of integer combination (Section 7.1), you will observe that the set of integer combinations of a pair of integers is closed under addition of elements in the set and multiplication by arbitrary integers. Of course this analogy between the integers and the polynomials is not accidental. If you generalize the idea of an integer combination to polynomials, you would say that the polynomial combinations of a pair of polynomials is an ideal of \(\mathbb{R}[x]\). For the integers we were able to prove that the set of integer combinations of a pair of integers is precisely the integer multiples of the greatest common divisor of the integers. Can we prove an analogous result for polynomials? DEFInITION. Principal ideal An ideal \(I\) in \(\mathbb{R}[x]\) is principal if there is \(f \in \mathbb{R}[x]\) such that \[I=\{f \cdot g \mid g \in \mathbb{R}[x]\} .\] In the definition of principal ideal, \(f\) is called a generator of \(I\). Theorem \(7.7\) can be restated to say that the set of integer combinations of a pair of integers is the principal ideal (in \(\mathbb{Z}\) ) generated by the greatest common divisor of the pair.

THEOREM 7.23. Every ideal of \(\mathbb{R}[x]\) is principal.

Proof. Let \(I\) be an ideal of \(\mathbb{R}[x]\). Let \(f\) be a polynomial of lowest degree in \(I\). We prove that \(f\) generates \(I\). Let \(h \in I\). It is sufficient to show that \(h\) is a multiple of \(f\). By Theorem 7.21, there are \(q, r \in \mathbb{R}[x]\), \(r=0\) or the degree of \(r\) less than the degree of \(f\), such that \[h=q f+r .\] Since \(I\) is an ideal and \(f \in I\), \[q f \in I\] and \[h-q f=r \in I .\] By assumption \(f\) is of minimal degree in \(I\), so \(r=0\). Therefore \[h=q f\] and \(f\) generates \(I\).

This program seems to be moving us towards a result for polynomials that is analogous to the Fundamental Theorem of Arithmetic. A polynomial is irreducible if it cannot be written as the product of polynomials of lower degree. We shall prove in Theorem \(9.48\) that every polynomial in \(\mathbb{R}[x]\) factors uniquely into the product of irreducible polynomials (up to the order of factors and multiplication by constants), and moreover that all irreducible polynomials are of degree at most \(2 .\) Studying algebraic properties of polynomials is the most important motivating principle in Algebra. Good texts on Algebra include John Fraleigh’s [2] and Israel Herstein’s [3].