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 SIR
ISAAC NEWTON (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. highschool 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 PERSPECTIVE. It is also known that Euclid produced at least
five other texts in geometry, including a four-book treatise on CONICS, as well as a work on music and another
discussing general scientific principles.
See also EUCLID’S POSTULATES.
Euclidean algorithm In his third book of THE ELEMENTS, EUCLID 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 identical numbers. This repeated value is the greatest
common factor of the two original numbers.
As an example, we calculate the greatest common factor 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 difference. 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 a and b eventually produce the
value z via this procedure:
a : b → c : d → … → u : v → z : z
Then it is not too difficult to show that z is indeed the
greatest common factor of a and b.
Firstly, if a and b are 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, z is 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 z is at least as large as any
common factor of a and b.
Secondly, working backward through the procedure, we see that the penultimate pair u : v is obtained
from z : z via addition. (Look at the example above.)
Thus both u and v are multiples of z. Working all the
way back, we have in fact that all the numbers appearing in the list must be multiples of z, including both a
and b. Thus z is a common factor.
These two conclusions show that z is 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 common 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 a and 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
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 SIR
ISAAC NEWTON (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. highschool 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 PERSPECTIVE. It is also known that Euclid produced at least
five other texts in geometry, including a four-book treatise on CONICS, as well as a work on music and another
discussing general scientific principles.
See also EUCLID’S POSTULATES.
Euclidean algorithm In his third book of THE ELEMENTS, EUCLID 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 identical numbers. This repeated value is the greatest
common factor of the two original numbers.
As an example, we calculate the greatest common factor 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 difference. 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 a and b eventually produce the
value z via this procedure:
a : b → c : d → … → u : v → z : z
Then it is not too difficult to show that z is indeed the
greatest common factor of a and b.
Firstly, if a and b are 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, z is 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 z is at least as large as any
common factor of a and b.
Secondly, working backward through the procedure, we see that the penultimate pair u : v is obtained
from z : z via addition. (Look at the example above.)
Thus both u and v are multiples of z. Working all the
way back, we have in fact that all the numbers appearing in the list must be multiples of z, including both a
and b. Thus z is a common factor.
These two conclusions show that z is 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 common 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 a and 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