12

5.2. The division algorithm.

We say that a polynomial g ∈ ℝ[X]  divides a polynomial f ∈ ℝ[X]  (written g∣f  ) if there is a polynomial q ∈ ℝ[X]  such that f = qg  . Notice that if g∣f  then either f = 0  or degg ≤ deg f  . Notice that if fg = 0  then either f = 0  or g = 0  (or both). This means that we can (only) divide by nonzero polynomials.

Problem 5.3. Let f,g ∈ ℝ[X]  be two polynomials. Prove that if f∣g  and g∣f  then degf = degg  .

In fact, there is an analog of long division for polynomials, as there is for integers.

Theorem 5.4. Let f,g ∈ ℝ[X]  be polynomials with g ⁄= 0  . Then there exist unique polynomials q,r ∈ ℝ[X]  such that f = qg+ r  and degr < degg  .

Proof. We first prove existence of q,r  . If deg g > degf  then we set q = 0  and r = f  . Otherwise, degf ≥ degg  . Let

f = a0 + ⋅⋅⋅+ amXm ,    where am ⁄= 0,

and

g = b0 + ⋅⋅⋅+bnXn ,   where bn ⁄= 0.

Define the integer d = m - n ≥ 0  . We will use induction in d  .

Base step: Let d = 0  , then m = n  . We set q = am ∕bm  and r = f - qg  . Notice that q  is well-defined because bm ⁄= 0  and that the coefficient of Xm  in r  vanishes, whence degr < m = degg  .

Induction step: Now we assume that this is true whenever d < k  and let d = k  , so that m  = n+ k  . Let f1 = f - (am∕bn)Xm -ng  . Notice that degf1 < degf  , whence by induction there exist q1,r  with degr < degg  and f1 = q1g +r  . Therefore

        am  m -n   (     am  m -n)
f = f1 + b-X    q =  q1 + b-X      g+ r ,
         n                n

whence define q = q1 + (am∕bn)Xm -n  and the result is true for d = k  .

Finally we prove uniqueness. Suppose that f = qg + r = Qg + R  , with degr < degg  and degR < deg g  . Rearranging, we have R - r = (q- Q)g  , whence g  divides R - r  . Since deg(R - r) < degg  , this can only happen if R - r = 0  , whence R = r  . In this case, g(q- Q) = 0  , which since g ⁄= 0  implies that q- Q = 0  or, equivalently, that Q = q  .□

The polynomials q  and r  in the statement of the theorem are called the quotient and remainder, respectively.

Given f,g ∈ ℝ[X]  we can find q,r  by long division, as the following example shows.

Example 5.5. Let      3    2
f = X + X  - 3X - 3  and      2
g = X + 3X + 2  . Then we let                  2
f1 = f - Xg = - 2X - 5X - 3  . Similarly let f2 = f1 + 2g = X + 1  , whose degree is less than that of g  . Therefore,

f = f1 + Xg = f2 + (X - 2)g = (X - 2)g + (1 + X) ,

whence q = X - 2  and r = 1 + X  .