96 SPECIAL TOPICS IN THEORETICAL ARITHMETIC

shorter than otherwise if we always choose a remainder corre-
sponding to an exact or lower or upper approximate quotient.
For such a choice of quotients we have the following theorem.

227. Th. Having given two numbers a and b, of whichb—= 0,
if we find a series of numbers ry, 72, v3, -+, Such that, starting
with 71, each number in the series

a, b, Ty 2o 1l gy a2
is the remainder got by dividing the predecessor of the preceding
number by the preceding number, choosing always the exact or
lower or upper approximate quotient, then this series will end with
a zero remainder and a (X b will be the numerical value of the
divisor that gives the zero remainder.

We have |b| > || > |r2| > |73 > <= §§ 78, 80.

Hence the remainders will continually decrease in numerical
value and be all numerically less than |b]. ‘

Their number then cannot be greater than the number of
numbers in the natural series of integers

8] — 1, |b] — 2, -+, 2,1,0,
which is |b].

We must therfor, at least as early as in the |b|th division,
find the remainder 0.

Our theorem then follows from the preceding theorem.

For example, if ¢ = 22 and b = — 16, we may work as
follows:

 

In this illustration, when there was a choice, we always
chose the numerically largest remainder.