became the model of logical thinking in Europe. More
than 2,000 different editions of the text have appeared
since the first typeset version produced in the year 1482,
and many great scientists of the West, including S
IR
I
SAAC
N
EWTON
(1642–1627) for instance, described
their mastering the work of Euclid as a significant part
of their development of scientific thinking. Study of The
Elements was an integral part of the standard U.S. high-
school mathematics curriculum up until the 1950s.
Other works attributed to Euclid of Alexandria that
have survived today include Data, on the properties of
figures; On Divisions, studying the geometric theory of
dividing the areas of figures into certain proportions;
and Optics, the first Greek work on the theory of
PER
-
SPECTIVE
. It is also known that Euclid produced at least
five other texts in geometry, including a four-book trea-
tise on
CONICS
, as well as a work on music and another
discussing general scientific principles.
See also E
UCLID
’
S POSTULATES
.
Euclidean algorithm In his third book of T
HE
E
LE
-
MENTS
, E
UCLID
describes a systematic procedure for
finding the
GREATEST COMMON DIVISOR
of any two
positive integers. The method is as follows:
1. Write down the pair of numbers.
2. Subtract the smaller number from the larger.
3. Rewrite the pair of numbers but replace the larger
number with the answer from step two.
4. Repeat steps two and three until you have two iden-
tical numbers. This repeated value is the greatest
common factor of the two original numbers.
As an example, we calculate the greatest common fac-
tor of 42 and 60:
42:60 →42:18 →24:18 →6:18 →6:12 →6:6
Their greatest common factor is 6. Each step of the
procedure produces a pair of numbers with smaller dif-
ference. Eventually, a pair with difference zero will
result. The Euclidean algorithm is therefore sure to
stop after a finite number of calculations.
Why the Algorithm Works
Suppose two numbers aand beventually produce the
value zvia this procedure:
a : b →c : d →… →u : v →z : z
Then it is not too difficult to show that zis indeed the
greatest common factor of aand b.
Firstly, if aand bare both multiples of any number
n, then so is their difference. This means that all the
pairs of numbers produced by this procedure remain
multiples of n. In particular, zis a multiple of n. (In the
example above, both 42 and 60 are multiples of 3, for
example. All the numbers produced via the procedure
remain multiples of 3. They are also multiples of 2 and
of 6.) This establishes that zis at least as large as any
common factor of aand b.
Secondly, working backward through the proce-
dure, we see that the penultimate pair u : v is obtained
from z : z via addition. (Look at the example above.)
Thus both uand vare multiples of z. Working all the
way back, we have in fact that all the numbers appear-
ing in the list must be multiples of z, including both a
and b. Thus zis a common factor.
These two conclusions show that zis indeed the
greatest common factor we seek. As a bonus, the above
two paragraphs also show that the greatest common
factor of two numbers is a multiple of any other com-
mon factor.
Linear Combinations
A surprising consequence of the Euclidean algorithm is
that it also gives a constructive method for writing the
greatest common factor of two positive integers aand b
as a linear combination of the original numbers.
Keeping track of the subtractions performed in the
example above, we have:
42 : 60 →42 : 18 = (42) : (60–42)
→24 : 18 = (42) – (60 – 42) : (60 – 42)
= (2 ×42 – 60) : (60 – 42)
→6 : 18 = (2 ×42 – 60) – (60 – 42) : (60 – 42)
=(3 ×42 – 2 ×60) : (60 – 42)
→6 : 12 = (3 ×42 – 2 ×60) : (60 – 42) –
(3 ×42 – 2 ×60)
= (3 ×42 – 2 ×60) : (3 ×60 – 4 ×42)
→6: 6 = (3 ×42 – 2 ×60) : (3 ×60 – 4 ×42)
– (3 ×42 – 2 ×60)
= (3 ×42 – 2 ×60) : (5 ×60 – 7 ×42)
Thus we can write 6 = 3 ×42 – 2 ×60 (and also 6 = 5 ×
60 – 7 ×42.) In general, this shows that it is always
Euclidean algorithm 169