92 3. Factors and Zeros
~“-1 = br”-2 - urn-l
c,,-2 = br,-3 - ar,,-2
...
c2 = bq - ar2
cl = bra - arl
co = -are.
(c) In (b), suppose that a/b is written in lowest terms. It is known
that a, b and the ci are integers, and also that a I CO and b I cn.
By looking at the equations relating the ri and the ci in turn
from the top, prove that
k-1 is an integer
br,-2 is an integer
b2rn-3 is an integer
...
b”-‘ro is an integer.
and conclude that each ri is a rational whose denominator di-
vides b”-l. Similarly, by looking at the equations in turn from
the bottom, show that each ri is a rational whose denominator
divides an-r. Deduce from this each ri is an integer.
(d) Complete the proof of the result.
- Newton’s Method of Divisors. The set of equations involving ci, ri, a
and b in Exercise 4 is the basis of an algorithm known as Newton’s
Method of Divisors. We wish to check whether a/b is a root of q(t).
Write in a row the coefficients of the polynomial, beginning with the
constant coefficient:
co Cl c2 c3 ... C”.
Divide CO by a. If the result is not an integer, then we do not have a
zero. If the result is an integer, let co/a = so (this is -ro in Exercise
4); write this integer under cr. Draw a line across. Beneath the line,
put the sum of cl1 and bso:
co Cl c2 ...
so
co cl + bso