The Euclidean algorithm from Euclid's Elements: the greatest common divisor, in Python
The Euclidean algorithm as Euclid states it in Elements VII.1 and VII.2, by repeated subtraction, then the division form, Lamé's 1844 step bound, and Python.
To reduce 54/15 to lowest terms you need the largest number that divides both, which is 3. The Euclidean algorithm finds it without factoring: divide, keep the remainder, and divide again until nothing is left. It is in Euclid's Elements, Book VII, propositions 1 and 2, written c. 300 BCE, where Euclid states it by repeated subtraction instead of division.
Python's math.gcd returns the same number, and fractions.Fraction calls it to get 18/5. Its extended version gives the private exponent in RSA key generation. I read Euclid's 2 propositions in Greek and in Heath's 1908 translation, coded both forms in Python, and counted the steps each takes. The code is euclid.py on GitHub, and the series is Ancient algorithms, implemented.
What the Euclidean algorithm solves
The greatest common divisor of 2 numbers is the largest number that divides both. For 54 and 15 it is 3. You need it to reduce a fraction to lowest terms, to decide whether a number has an inverse modulo another, and to find when 2 meshed gear wheels with 54 and 15 teeth are back where they started: after 54 × 15 / 3 = 270 teeth, which is 5 turns of the large wheel and 18 of the small one.
The obvious method is to factor both numbers and take the shared primes. That works for 54 and 15. It does not work for 2 numbers of 600 digits each: the largest RSA challenge number factored so far, RSA-250, has 250 digits and was factored in 2020. Euclid's method needs no factoring, and its number of steps grows with the number of digits.
Euclid had a different reason. Greek mathematicians compared lengths, and 2 lengths have a common measure when some third length fits a whole number of times into each. Book VII asks the same question about whole numbers, which Euclid defines as "a multitude composed of units" (Book VII, definition 2).
Who wrote it, and when
- Euclid, in the Elements, 13 books. The usual date, c. 300 BCE, rests on Proclus, writing in the 5th century CE, who places Euclid "in the time of the first Ptolemy" and before Archimedes. Heath notes that Proclus had no direct knowledge of Euclid's birth or death (Heath 1908, vol. 1, chapter 1).
- Earlier sources. Heath argues that Euclid followed earlier models in the arithmetic books. He points to a proof by Archytas (c. 430 to 365 BCE), kept by Boethius, that is substantially the same as a proof in Euclid's music treatise, and concludes that an Elements of arithmetic in Euclid's form existed by Archytas's time (Heath 1908, vol. 2, p. 295).
- The Greek text used here is J. L. Heiberg's edition (Teubner, 1883 to 1888), as given by the Perseus Digital Library. The English is T. L. Heath's, The Thirteen Books of Euclid's Elements (Cambridge, 1908), vol. 2, pp. 296 to 299, which is in the public domain.
The source text
Proposition VII.1
δύο ἀριθμῶν ἀνίσων ἐκκειμένων, ἀνθυφαιρουμένου δὲ ἀεὶ τοῦ ἐλάσσονος ἀπὸ τοῦ μείζονος, ἐὰν ὁ λειπόμενος μηδέποτε καταμετρῇ τὸν πρὸ ἑαυτοῦ, ἕως οὗ λειφθῇ μονάς, οἱ ἐξ ἀρχῆς ἀριθμοὶ πρῶτοι πρὸς ἀλλήλους ἔσονται.
Two unequal numbers being set out, and the less being continually subtracted in turn from the greater, if the number which is left never measures the one before it until an unit is left, the original numbers will be prime to one another.
T. L. Heath (1908), vol. 2, p. 296
My more literal version: "When 2 unequal numbers are set out, and the less is always taken away in turn from the greater, if what is left never measures the one before it until a unit is left, the numbers we started with will be prime to one another."
Proposition VII.2
δύο ἀριθμῶν δοθέντων μὴ πρώτων πρὸς ἀλλήλους τὸ μέγιστον αὐτῶν κοινὸν μέτρον εὑρεῖν.
Given two numbers not prime to one another, to find their greatest common measure.
T. L. Heath (1908), vol. 2, p. 298
The proof of VII.2 gives the method. If the smaller number measures the larger, it is the answer. If not, "the less of the numbers AB, CD being continually subtracted from the greater, some number will be left which will measure the one before it", and that number is the greatest common measure. Euclid then proves no greater number measures both. A porism, a corollary stated after the proof, adds: "if a number measure two numbers, it will also measure their greatest common measure."
Word by word
| Greek | Transliteration | Meaning |
|---|---|---|
| ἀριθμῶν ἀνίσων ἐκκειμένων | arithmōn anisōn ekkeimenōn | numbers, unequal, set out |
| ἀνθυφαιρουμένου | anthyphairoumenou | being taken away in turn; the noun is anthyphairesis |
| ἀεί | aei | always, continually |
| τοῦ ἐλάσσονος ἀπὸ τοῦ μείζονος | tou elassonos apo tou meizonos | the less from the greater |
| ὁ λειπόμενος | ho leipomenos | the one that is left |
| μηδέποτε καταμετρῇ | mēdepote katametrēi | never measures exactly |
| τὸν πρὸ ἑαυτοῦ | ton pro heautou | the one before itself |
| ἕως οὗ λειφθῇ μονάς | heōs hou leiphthēi monas | until a unit is left |
| πρῶτοι πρὸς ἀλλήλους | prōtoi pros allēlous | prime to one another |
| τὸ μέγιστον κοινὸν μέτρον | to megiston koinon metron | the greatest common measure |
"Measures" is Euclid's word for "divides exactly". Book VII, definition 12, in Heath: numbers prime to one another "are measured by an unit alone as a common measure".
What the text leaves open
- Euclid never divides. Each stage of the proof reads "let CD, measuring BE, leave EA less than itself". Heath glosses this as laying CD off along AB as many times as it fits. That is repeated subtraction, and the count of subtractions is the quotient. The code counts both.
- When to stop. Euclid stops when the number left measures the one before it. Testing "measures" with subtraction alone means going on until the 2 numbers are equal. The code stops at that equal pair.
- The unit is not a number. For Euclid a number is a multitude of units, so it starts at 2, and VII.1 ends when "an unit is left". The code accepts 1 so the procedure can end on it.
- No examples. Euclid works with lines labeled AB and CD, never with specific numbers. The worked example below is mine; the numbers 54 and 15 come from Granville's 2024 paper on these propositions.
How the Euclidean algorithm works: a worked example
Take 54 and 15.
Euclid's way, one subtraction at a time:
- 54 - 15 = 39, 39 - 15 = 24, 24 - 15 = 9. 9 is less than 15, so switch.
- 15 - 9 = 6. Switch.
- 9 - 6 = 3. Switch.
- 6 - 3 = 3. The 2 numbers are equal: 3 measures 6, and 3 is the greatest common measure.
That is 6 subtractions. The division form does the same work in 4 divisions, because each run of subtractions is 1 division:
The quotients 3, 1, 1, 2 are the subtraction counts of each stage. Their sum less 1, 6, is the number of subtractions; the last stage stops 1 short because the 2 numbers become equal. The tests check that relation on random pairs.
For VII.1, take 41 and 12, also Granville's example. The remainders are 5, 2 and then 1, a unit, so 41 and 12 are prime to one another.
Why the Euclidean algorithm works
The proof of VII.2 has 2 halves, and both rest on 1 fact: if a number measures 2 numbers, it measures their difference, and their sum.
The last number left measures both. Run the stages backward. 3 measures 6. 9 is 6 + 3, so 3 measures 9. 15 is 9 + 6, so 3 measures 15. 54 is 3 × 15 + 9, so 3 measures 54.
Nothing larger measures both. Run the stages forward. Suppose some number g measures 54 and 15. Then it measures 54 - 3 × 15 = 9. It measures 15 - 9 = 6, and 9 - 6 = 3. So g measures 3, and g is at most 3.
In modern notation, the forward argument says that a and b have the same common divisors as b and a mod b, so
and the remainders shrink until one is 0. That one line is what textbooks call the basic theorem of the Euclidean algorithm.
The backward argument gives more. Write each remainder in terms of the 2 starting numbers, and the last one comes out as a combination of them. For 41 and 12:
Euclid does not write this down. Finding the multipliers 5 and 17 is the extended Euclidean algorithm, and Aryabhata's kuttaka of 499 CE is a way to compute them.
The Python
This is Euclid's subtraction in turn and the division form, with a step counter for each.
def anthyphairesis(a: int, b: int) -> list[tuple[int, int]]:
"""Every pair Euclid's subtraction passes through, from (a, b) to (g, g)."""
pairs = [(a, b)]
while a != b:
if a > b:
a -= b
else:
b -= a
pairs.append((a, b))
return pairs
def division_quotients(a: int, b: int) -> list[int]:
"""Quotients of the division form, larger number first."""
a, b = max(a, b), min(a, b)
quotients = []
while b:
q, r = divmod(a, b)
quotients.append(q)
a, b = b, r
return quotients
pairs = anthyphairesis(54, 15)
print(pairs[-1][0], len(pairs) - 1) # 3 6
print(division_quotients(54, 15)) # [3, 1, 1, 2]
The repo version adds VII.1 as prime_to_one_another, VII.2 as greatest_common_measure, input checks, Lamé's bound and the Fibonacci worst case. Its anthyphairesis yields the pairs 1 at a time, and the counting functions handle each run of subtractions with 1 floor division, so they need no list. The tests check:
- the 54 and 15 run pair by pair, and the 41 and 12 run ending on a unit;
- VII.2's first case, where the smaller number measures the larger;
- against
math.gcdon random pairs up to 10,000, with Hypothesis; - the porism: every common divisor divides the greatest one;
- that the subtraction count equals the sum of the quotients less 1, and that 1012 and 1 count to 999,999,999,999 subtractions in under a second without storing the pairs;
- that the quotients rebuild the ratio as a continued fraction;
- Lamé's bound on random pairs up to 1060 and on a 5,001-digit pair, and the Fibonacci worst case, by brute force below 200.
Subtraction against division
The number of subtractions is the sum of the quotients less 1, so 1 large quotient makes a long run. For 1,000,000 and 1, Euclid's method makes 999,999 subtractions where 1 division does the job.
I ran both on 10,000 random pairs of each size, with the 2 numbers of a pair having the same number of digits:
| Digits | Divisions, median | Divisions, max | Subtractions, median | Subtractions, max |
|---|---|---|---|---|
| 3 | 6 | 12 | 19 | 955 |
| 6 | 12 | 22 | 52 | 21,636 |
| 12 | 23 | 37 | 132 | 185,326 |
| 24 | 46 | 67 | 319 | 397,804 |
The median division count doubles when the digits double. The median subtraction count runs from 19 to 319, and the maximum reaches 397,804 for 24-digit numbers, from pairs with 1 large quotient. The script is benchmarks/euclid_steps.py in the repo, with a fixed random seed.
Lamé's bound and the Fibonacci worst case
On 28 October 1844, Gabriel Lamé presented a short note to the Paris Academy of Sciences. His theorem, in the Comptes rendus:
« Le nombre des divisions à effectuer, pour trouver le plus grand commun diviseur entre deux entiers A, et B < A, est toujours moindre que cinq fois le nombre des chiffres de B. »
G. Lamé, Comptes rendus 19 (1844), p. 867
In English: the number of divisions needed to find the greatest common divisor of 2 whole numbers A and B < A is always less than 5 times the number of digits of B.
Lamé's proof uses the sequence 1, 2, 3, 5, 8, 13, ..., each term the sum of the 2 before, now called the Fibonacci numbers. 2 consecutive terms give quotients of 1 at every step, and that is the slowest the remainders can shrink. Between 1 power of 10 and the next there are at least 4 and at most 5 terms, which is where the 5 comes from.
His own example is 1597 and 987, the 16th and 15th terms of his sequence. He counts 14 divisions against a bound of 15, and notes that the textbook rule of the day, half the smaller number, would allow 493. My code counts 15 for the same pair. Lamé stops at the remainder 1; the code also counts the last division, the one that leaves 0. With that count the bound reads "at most 5 times the digits", and 1597 and 987 reach it.1
The tests check 2 statements:
division_count(a, b) <= 5 * digits(min(a, b))on random pairs up to 1060;- if a pair
a > bneedsndivisions, thena >= F(n+2)andb >= F(n+1), and the pair(F(n+2), F(n+1))needs exactlyn.
Parallels and lineage
- Anthyphairesis outside arithmetic. Book X, proposition 2, applies the same subtraction in turn to magnitudes: if what is left never measures the one before it, "the magnitudes will be incommensurable" (Heath 1908, vol. 3, p. 17). Granville (2024) points to a mention of the procedure in Aristotle's Topics.
- Aryabhata, 499 CE. The kuttaka runs the same chain of divisions and keeps the quotients to solve
ax + c = by. I know of no source that documents a route from Euclid to Aryabhata. - Python.
math.gcdcomputes the greatest common divisor of integers of any size.fractions.Fractioncalls it to reduce every fraction it builds.
What is debated
- Whether Euclid had the identity
a*m - b*n = gcd(a, b). It is usually called Bézout's identity, after Étienne Bézout (18th century). Andrew Granville (2024) argues that it is in Euclid's VII.1 and VII.2 once the propositions are read as statements about lengths laid end to end, and that Euclid did not write the combination out because his notation made it hard. The Elements never states it as a theorem, so this is a reading of Euclid's intent. - How old the method is. Heath's evidence from Archytas shows an arithmetic in Euclid's style before Euclid. Whether the subtraction procedure itself is older than the Elements is a matter of reconstruction. David Fowler's The Mathematics of Plato's Academy (1987) builds a theory of ratio on anthyphairesis; it is a reconstruction, and the surviving texts do not state it.
- Who first bounded the steps. Lamé's 1844 note is the usual citation. The abstract of Jeffrey Shallit's 1994 paper says Reynaud gave a weak bound in 1811, Léger knew Lamé's basic result by 1837, and Finck gave a complete proof in 1841. Peter Schreiber (1995) published a supplement on earlier observations of the Fibonacci worst case.
- The date. c. 300 BCE comes from Proclus, writing about 750 years later.
Key takeaways
- The Euclidean algorithm finds the greatest common divisor without factoring. Euclid states it in Elements VII.1 and VII.2, c. 300 BCE.
- Each division in the modern form does a whole run of Euclid's subtractions, so the 2 forms give the same answer, and subtraction can take far longer: 999,999 steps against 1 for 1,000,000 and 1.
- It works because a number that measures 2 numbers also measures their difference, so
gcd(a, b) = gcd(b, a mod b). - Lamé proved in 1844 that the divisions number fewer than 5 times the digits of the smaller number, counting nonzero remainders. Consecutive Fibonacci numbers are the worst case.
- The code, tests and step counts are in ancient-algorithms.
Sources
- Euclid, Elements, ed. J. L. Heiberg, Teubner, 1883 to 1888. Greek text of VII.1 and VII.2 from the Perseus Digital Library.
- T. L. Heath, The Thirteen Books of Euclid's Elements, vol. 2, Cambridge University Press, 1908. Book VII definitions pp. 277 to 278, VII.1 and VII.2 pp. 296 to 299, historical note p. 295. Vol. 1, chapter 1, on Proclus and the date. Vol. 3, p. 17, for X.2.
- G. Lamé, "Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers", Comptes rendus 19, 1844, pp. 867 to 870.
- A. Granville, "It is not Bézout's identity", arXiv 2406.15642, 2024.
- J. Shallit, "Origins of the analysis of the Euclidean algorithm", Historia Mathematica 21, 1994, pp. 401 to 419.
- P. Schreiber, "A supplement to J. Shallit's paper 'Origins of the analysis of the Euclidean algorithm'", Historia Mathematica 22, 1995, pp. 422 to 424.
- D. Fowler, The Mathematics of Plato's Academy: A New Reconstruction, Oxford University Press, 1987.
Footnotes
-
Lamé's proof bounds the number of nonzero remainders, which is 1 less than the number of divisions when the last division leaves 0. The 2 statements are the same theorem counted 2 ways. ↩
Common questions
What is the Euclidean algorithm?↓
A procedure for the greatest common divisor of 2 whole numbers. Divide the larger by the smaller, replace the larger with the remainder, and repeat until the remainder is 0. The last nonzero remainder is the greatest common divisor. Euclid states it in the Elements, Book VII, propositions 1 and 2, c. 300 BCE, using repeated subtraction in place of division.
What is the basic theorem of the Euclidean algorithm?↓
gcd(a, b) = gcd(b, a mod b). Any number that divides a and b also divides a - q*b, which is the remainder, and any number that divides b and the remainder also divides a. So the 2 pairs have the same common divisors, and the same greatest one.
How do you find the gcd of 2 numbers?↓
Divide the larger by the smaller and keep the remainder. Then divide the smaller by that remainder, and go on until a division leaves 0. The last divisor is the gcd. For 54 and 15: 54 = 3 × 15 + 9, 15 = 1 × 9 + 6, 9 = 1 × 6 + 3, 6 = 2 × 3. The gcd is 3. In Python, math.gcd(54, 15) returns 3.
How many steps does the Euclidean algorithm take?↓
At most 5 times the number of decimal digits of the smaller number. Gabriel Lamé proved this in 1844. The worst case is a pair of consecutive Fibonacci numbers: 1597 and 987 take 15 divisions, and 987 has 3 digits.
Did Euclid know Bézout's identity?↓
The Elements never states that a*m - b*n = gcd(a, b) as a theorem. Andrew Granville argued in 2024 that Euclid's proofs of VII.1 and VII.2, read as statements about lengths, contain it, and that the name Bézout's identity is a misattribution.