Divisibility of polynomials
The divisibility properties and definitions relating to integers extend to polynomials.
Proposition 5.2.1. (Algorithm for the division). Let f(x) and g(x) ∈ ๐[x] two polynomials with g(x) ≠ 0. Then there exist and are uniquely determined two polynomials q(x) and r(x) ∈ ๐[x] such that
f(x) = g(x) ยท q(x) + r(x), with โr(x) < โg(x) or r(x) = 0.
Proof. If f(x) = 0 or โr(x) < โg(x) is enough to set q(x) = 0 and r(x) = f(x). So suppose โg(x) ≤ โf(x). We proceed by induction on n=โf. If n = 0 (hence also โg(x) = 0), we have f(x) = a0 and g(x) = b0, with a0, b0 ∈ ๐, thus
f(x) = a0 = (a0โ b0โ1) b0 + 0
in this case r(x) = 0 and q(x) = a0โ b0โ1.
We suppose the theorem true for polynomials of degree < n and prove it for โf = n. Then โf = n ≥ โg = m. Let
f(x) = a0 + a1 x + ยทยทยท + an xn, g(x) = b0 + b1 x + ยทยทยท + bm xm,
we put
h(x) = f(x) โ an bmโ1 xnโm g(x)
The degree of h(x) is smaller than n, so we may apply to h(x) the induction hypothesis. So there exist q1>(x), r1(x) such that
h(x) = q1(x) g(x) + r1(x), r1(x) < m or โr1(x) = 0.
Then
f(x) โ an bmโ1 xnโm g(x) = h(x) = g(x) q1 + r1(x)
And it is enough to take r(x) = r1(x) and q(x) = q1(x) + (an bmโ1)xnโm.
As to the uniqueness of division, notice that if f(x) = g(x) ยท q1 (x) + r1 (x) = g(x) ยท q2(x) + r2 (x) such that โri(x) < โg(x) or ri(x) = 0 with i = 1, 2, then we would get
g(x)(q1(x) โ q2(x)) = (r2(x) โ r1(x))
If it is the case that q1 > (x) โ q2(x) ≠ 0, the left-hand side would have a greater degree than the second one, which is not possible. So we must have q1(x) = q2 (x), which also implies r2(x) = r1(x).โก
Definition 5.2.2. We say that a polynomial g(x) divides a polynomial f(x) with f,g ∈ ๐[x] and we write g(x)| f(x) if there exists a polynomnial q(x) ∈ ๐[x] such that
f(x) = g(x) ยท q(x)
Definition 5.2.3. An element f(x) ∈ ๐[x] is said invertible if there exists a polynomial g(x) ∈ ๐[x] such that f(x)g(x) = 1.
A polynomial g(x) of degree 1 or higher, in F[x], can never be invertible, because if it had an inverse h(x), then h(x) != 0 so the product g(x) h(x) has degree deg(g) + deg(h) ≥ 1, so this product can't be 1.
Example 5.2.4. Long division of x3 − 8 by x − 2 yields
![example long division](img/long_division_ex.png)
Example 5.2.5. The division of x2 + x + 2 by x โ b, with b a constant, leaves a remainder b2 + b + 2.
![division of x^2+x+2 by x-b](img/poly_division_remainder.png)
At each step we must remove the highest degree term: so in the 1st step we multiply x โ b, by x to remove the x2 and in the 2nd step to remove (b+1)x we multiply x โ b, by b + 1. โ