Page 230 - DMTH403_ABSTRACT_ALGEBRA

Unit 23: Division of Algorithm

We shall apply the principle of induction on deg f(x), i.e., n. Notes
If n = 0, then rn = 0, since g(x)  0. Now

f(x) = a,,, g(x) = b,, and hence
f(x) = (a,, b ) b + 0 = q (x) g (x) + r (x), where q(x) = a b and r(x) = 0.
-1
-l
0
0 0
0
Thus,
f(x) = q(x) g(x) + r (x), where deg r(x) < deg g(x).
So the algorithm is true when n = 0. Let us assume that the algorithm is valid for all polynomials
of degree  n – 1 and how to establish that it is true for f(x). Consider the polynomial
f (x) = f(x) – a b x g(x)
-1 n-m
1
n m
= (a,, + a, x +. . .+a x ) – (a b b x n-m +a b b x n-m+1 +...+ a b b x )
-1
-1
-1
n
n
0
n m
n m
n m
n
m
1
Thus, the coefficient of xn in f, (x) is zero; and hence,
deg f, (x)  n-1.
By the induction hypothesis, there exist q, (x) and r (x) in
F[x] such that f, (x) = q, (x) g(x) + r(x), where deg r(x) < deg g(x).
Substituting the value of f,(x), we get
f(x)-a b g(x) = q (x) g(x) + r(x),
-1
1
n m
i.e., f(x) = {a b -1 n-m +q (x)} g(x) + (x)
x
n m
1
= q(x) g(x)+r(x), where q(x) = a b x n-m +q (x)
-1
n m
1
and deg r(x) < deg g(x).
Therefore, the algorithm is true for f(x), and hence for all polynomials in F[x].
(b) Now let us show that q(x) and r(x) are uniquely determined.
If possible, let
f(x) = q (x) g(x) + r (x), where deg r (x) < deg g(x).
1
1
1
and
f(x) =q (x) g(x)+r (x), where deg r (x) < deg g(x).
2
2
2
Then
q (x) g(x)+r (x) = q (x) g(x)+r (x), so that
1
2
1
2
{q (x) – q (x)} g(x) = r (x) – r (x) ...(1)
1
2
1
2
Now if q (x)  q (x), then deg {q (x) – q (x)}  0, so that
1
2
1
2
deg [{q (x) – q (x) g(x)]  deg g(x).
2
1
On the other hand, deg {r (x) - r (x)} < deg g(x), since
2
1
deg r (x) < deg g(x) and deg r (x) < deg g(x).
2
1
But this contradicts Equation (1). Hence. Equation (1) will remain valid only if
q (x) – q (x) = 0. And then r (x) – r (x) = 0,
1
2
2
1
i.e., q (x) = q (x) and r (x) = r (x).
1 2 1 2
LOVELY PROFESSIONAL UNIVERSITY 223