- ANCIENT GREEK NUMBER THEORY 165
of which naturally have 1 as a common divisor. Euclid, on the other hand, does not
confine it to integers, but states the procedure for "magnitudes," which may lack
a common measure. It is significant that the procedure terminates if and only if
there is a common measure, and Euclid makes use of that fact in discussing incom-
mensurables. The algorithm was certainly invented long before the time of Euclid,
however. Zverkina (2000) believes that this procedure could not have arisen intu-
itively, but must have come about as the result of solving specific problems, most
likely the problem of reducing ratios by canceling a common divisor. It is used for
that purpose in Chinese mathematics. What follows is a description of the general
procedure.
For definiteness, we shall imagine that the two quantities whose greatest com-
mon measure is to be found are two lengths, say a and b. Suppose that a is longer
than b. (If the two are equal, their common value is also their greatest common
divisor.) The general procedure is to keep subtracting the smaller quantity from
the larger until the remainder is equal to the smaller quantity or smaller than it. It
is not difficult to show that the smaller quantity and the remainder have the same
common measures as the smaller quantity and the larger. Hence one can start over
with the smaller quantity and the remainder, which is no more than half of the
larger quantity. Either this process terminates with an equal pair, or it continues
and the pairs become arbitrarily small.
An example will make the procedure clear. Let us find the greatest common
measure (divisor) of 26173996849 and 180569389. A common measure does exist:
the integer 1. Since the repeated subtraction process amounts to division with
remainder, we do it this way: 26173996849-r 180569389 is 144 with a remainder of
- We then divide 180569389 by 172004833, getting a quotient of 1 and
a remainder of 8564556. Next we divide 172004833 by 8564556, getting a quotient
of 20 and a remainder of 713713. We then divide 8564556 by 713713 and get a
quotient of 12 with no remainder, so that the greatest common divisor is 713713.
This computation can be arranged as follows:
12 20 1 144
713713)8564556)172004833)180569389)26173996849
8564556 171291120 172004833 26001992016
0 713713 8564556 172004833
2.1. The Arithmetica of Nicomachus. In his first book Nicomachus makes the
elementary distinction between odd and even numbers. Having made this distinc-
tion, he proceeds to refine it, distinguishing between even numbers divisible by 4
(evenly even) and those that are not (doubles of odd numbers). He goes on to
classify odd numbers in a similar way, coming thereby to the concept of prime and
composite numbers. Nicomachus also introduces what we now call pairs of relatively
prime numbers. These are pairs of numbers that have no common prime divisor
and hence no common divisor except 1. The notion of a relational property was
difficult for Greek philosophers, and Nicomachus expresses the concept of relatively
prime numbers in a confused manner, referring to three species of odd numbers:
the prime and incomposite, the secondary and composite, and "the variety which,
in itself is secondary and composite, but relatively is prime and incomposite." This
way of writing seems to imply that there are three kinds of integers, prime and
incomposite, secondary and composite, and a third kind midway between the other
two. It also seems to imply that one can look at an individual integer and classify it