The Euclidean algorithm and finite continued fractions

1 Introduction

Fowler [22]

Measure theory of continued fractions: Einsiedler and Ward [19, Chapter 3] and Iosifescu and Kraaikamp [37, Chapter 1].

In harmonic analysis and dynamical systems, we usually care about infinite continued fractions because we usually care about the Lebesgue measure of a set defined by some conditions on the convergents or partial quotients of a continued fraction. For some questions about functions defined using continued fractions in which we speak about the continuity or differentiability of a particular function, we do indeed care about rational numbers. This paper assembles and comments on the Euclidean algorithm and finite continued fractions in classical Greek and medieval Latin mathematics.

2 Numbers and magnitudes

Plato, Parmenides 140b–c [12, p. 126]:

Further, the One, being such as we have described, will not be either (a) equal or (b) unequal either to itself or to another.
If it is equal, it will have the same number of measures as anything to which it is equal. If greater or less, it will have more or fewer measures than things, less or greater than itself, which are commensurable with it. Or, if they are incommensurable with it, it will have smaller measures in the one case, greater in the other.

Allen [2, pp. 236–241] comments on this passage.

Aristotle, Metaphysics Δ.13, 1020a [56]:

‘Quantum’ means that which is divisible into two or more constituent parts of which each is by nature a ‘one’ and a ‘this’ . A quantum is a plurality if it is numerable, a magnitude if it is measurable. ‘Plurality’ means that which is divisible potentially into non-continuous parts, ‘magnitude’ that which is divisible into continuous parts; of magnitude, that which is continuous in one dimension is length, in two breadth, in three depth. Of these, limited plurality is number, limited length is a line, breadth a surface, depth a solid.
Again, some things are called quanta in virtue of their own nature, others incidentally; e.g. the line is a quantum by its own nature, the musical is one incidentally. Of the things that are quanta by their own nature some are so as substances, e.g. the line is a quantum (for a ‘certain kind of quantum’ is present in the definition which states what it is), and others are modifications and states of this kind of substance, e.g. much and little, long and short, broad and narrow, deep and shallow, heavy and light, and all other such attributes. And also great and small, and greater and smaller, both in themselves and when taken relatively to each other, are by their own nature attributes of what is quantitative; but these names are transferred to other things also. Of things that are quanta incidentally, some are so called in the sense in which it was said that the musical and the white were quanta, viz. because that to which musicalness and whiteness belong is a quantum, and some are quanta in the way in which movement and time are so; for these also are called quanta of a sort and continuous because the things of which these are attributes are divisible. I mean not that which is moved, but the space through which it is moved; for because that is a quantum movement also is a quantum, and because this is a quantum time is one.

Polybius Histories, Book IV, Chapter 40:

For given infinite time and basins that are limited in volume, it follows that they will eventually be filled, even if silt barely trickles in. After all, it is a natural law that, if a finite quantity goes on and on increasing or decreasing – even if, let us suppose, the amounts involved are tiny – the process will necessarily come to an end at some point within the infinite extent of time.

Plato, Laws 819

Diodorus Siculus, 11.25.1 [57, pp. 124–125]:

Gelon after his victory honored with gifts not only those cavalry who had killed Hamilcar, but also others who had distinguished themselves in the battle. He put aside the best of the booty to decorate the temples of Syracuse. Of the remainder, he nailed much of it to the most magnificent temples of Himera and the rest along with the captives he distributed to his allies according to the number of their soldiers who had fought with him.

Definition 4 of Elements V [30, p. 114]:

Magnitudes are said to have a ratio to one another which are capable, when multiplied, of exceeding one another.

For $x,y\in {ℝ}_{>0}$, let

$$T(x,y)=sup(k\in {\mathbb{Z}}_{\ge 0}:x-ky\ge 0),$$

which satisfies

(1)

For $x\in {ℝ}_{>0}$, let

$$\lfloor x\rfloor =sup(n\in \mathbb{Z}:n\le x),$$

which satisfies

Lemma 1.

For $x\mathrm{,}y\mathrm{\in }{ℝ}_{\mathrm{>}\mathrm{0}}$,

$$T(x,y)=\lfloor x/y\rfloor .$$

Proof.

First, $\lfloor x/y\rfloor \in {\mathbb{Z}}_{\ge 0}$. Second, as $\lfloor x/y\rfloor \le x/y$,

$$x-\lfloor x/y\rfloor \cdot y\ge x-(x/y)\cdot y=0.$$

Third, if $x-ky\ge 0$ then , and is equivalent to $k\le \lfloor x/y\rfloor$. Therefore

$$\lfloor x/y\rfloor =sup(k\in {\mathbb{Z}}_{\ge 0}:x-ky\ge 0)=T(x,y).$$

∎

For $x,\mu \in {ℝ}_{>0}$, we say that $\mu$ measures $x$ if $x=T(x,\mu )\cdot \mu$, and write $\mu \mid x$, and write $\mu \nmid x$ if $\mu$ does not measure $x$. We say that $x,y\in {ℝ}_{>0}$ are commensurable if there is some $\mu \in {ℝ}_{>0}$ such that $\mu \mid x$ and $\mu \mid y$, and call $\mu$ a common measure of $x$ and $y$. If $\nu$ is a common measure of $x$ and $y$ and for any common measure $\mu$ of $x$ and $y$ it holds that $\nu \ge \mu$, we say that $\nu$ is a greatest common measure of $x$ and $y$, and write $\nu =\mathrm{gcm}(x,y)$. For $\mu \in {ℝ}_{>0}$,

$$(\mu \mid x)\wedge (\mu \mid y)\iff \mu \mid \mathrm{gcm}(x,y).$$

Definitions 1 and 2 of Elements VII [30, p. 277]:

1. An unit is that by virtue by which each of the things that exist is called one.
2. A number is a multitude composed of units.

We model numbers by elements of ${\mathbb{Z}}_{\ge 2}$. If $p$ is a number then $1\mid p$, and if $p$ and $q$ are numbers then $1$ is a common measure of $p$ and $q$, so any two numbers are commensurable. Definitions 12 and 14 of Elements VII [30, p. 278]:

12. Numbers prime to one another are those which are measured by an unit alone as a common measure.
14. Numbers composite to one another are those which are measured by some number as a common measure.

3 Anthyphaeresis

Aristotle, Topics VIII.3, 158b29–35 [66, pp. 506–507]:

It would seem that in mathematics also some things are not easily proved by lack of a definition, such as the proposition that the straight line parallel to the side which cuts the plane divides in the same way both the line and the area. But when the definition is stated, what was stated becomes immediately clear. For the areas and the lines have the same alternating subtraction (antanairesis); and this is the definition of the same proportion.

Alexander of Aphrodisias, On the Topics, VIII.3:

For likewise when this is stated it is not obvious; but when the definition of proportion is enunciated it becomes obvious that both the line and the area are cut in the same proportion by the line drawn parallel. For the definition of proportions which those of old time used is this: Magnitudes which have the same alternating subtraction (anthyphairesis) are proportional. But he has called anthyphairesis antanairesis.

Fowler [22] is a comprehensive summary of Greek writings about ratios and anthyphaeresis. In Fowler’s formalization, for magnitudes $x,y,x>y$, the anthyphaeresis of the ratio $x:y$ is the sequence $a_n$ formed when applying the Euclidean algorithm with $x$ and $y$.

Mendell [45]

4 The Euclidean algorithm

Weil [72, p. 5, Chap. I, §II]:

Was there originally a relation between the so-called “Euclidean algorithm”, as described in Eucl.VII.1–2, for finding the g.c.d. of two integers, and the theory of the same process (Eucl.X.2) as it applies to possibly incommensurable magnitudes? Has it not often happened that a mathematical process has been discovered twice, in different contexts, long before the substantial identity between the two discoveries came to be perceived? Some of the major advances in mathematics have occured just in this manner.

In his introduction to Book V of Euclid’s Elements, Heath says the following [30, p. 113]:

It is a remarkable fact that the theory of proportions is twice treated in Euclid, in Book V. with reference to magnitudes in general, and in Book VII. with reference to the particular case of numbers. The latter exposition referring only to commensurables may be taken to represent fairly the theory of proportions at the stage which it had reached before the great extension of it made by Eudoxus.

In this paper we talk only about using the Euclidean algorithm with commensurable magnitudes, equivalently, about finite continued fractions. This gives us a chance to become familiar with the Euclidean algorithm just as it occurs in Elements VII.1–2, rather than in Elements VII.1–2 and Elements X.2–3 together. A study of the Euclidean algorithm for not necessarily commensurable magnitudes should involve the following.

1. The regular polygons in Elements IV,VI.30,XII.1,XIII.1–12, XIII.18.

2. The classification of incommensurable lines in Elements X, for which see e.g. Taisbak [64] and the commentary of Pappus of Alexandria [67].

3. Methods for approximating square roots in works like Heron’s Metrica [1], Archimedes’ Measurement of a Circle, and Ptolemy’s Almagest [69].

4. Solving Pell’s equation as in Diophantus, Arithmetica, Lemma to VI.15 [31, p. 238], and side and diagonal numbers as in Proclus, Commentary on Plato’s Republic [21, pp. 133–135] and Theon of Smyrna, Expositio rerum mathematicarum ad legendum Platonem utilium I.XXXI [18, pp. 70–75].

5. Magnitudes and ratios, for which see Knorr [40] on Egyptian and Greek fractions, Larsen [42] and Thorup [68] on pre-Euclidean theories of proportions, Grattan-Guinness [27] for a discussion of numbers, magnitudes and ratios in the Elements, Murdoch [48] for Latin writers, and Plooij [53] and Hogendijk [35] for Arabic writers

6. Infinite divisibility and Zeno’s paradoxes, and philosophical writing about the infinite like in Aristotle’s Physics and Metaphysics, for which see Heath [29] and commentary by Beere [5, pp. 127–129] on anthyphaeresis.

7. Music theory, for which see Huffman [36] and Barker [4], especially making sense of the notion of semitone, e.g., Censorinus, De Dei Natali 10.7 [51, p. 18]: according to Aristoxenus the octave is 6 tones, while according to the Pythagoreans the octave is 5 tones and 2 semitones, “so Pythagoras and the mathematicians, who pointed out that two semi-tones do not necessarily add up to a full tone.”

8. Astronomy and calendars, for which see Neugebauer [50].

The Euclidean algorithm.

Let $x,y\in {ℝ}_{>0}$ be commensurable, with $x>y$: there is some $\mu \in {ℝ}_{>0}$ and some $p,q\in {\mathbb{Z}}_{\ge 1}$ such that $x=p\cdot \mu$ and $y=q\cdot \mu$, $p>q$.

Define

$$v_0=p,v_1=q.$$

Define

$$a_0=T(v_0,v_1),v_2=v_0-a_0{v}_1.$$

From (1) we know , whence

For $m\ge 2$, if $v_m>0$ then define

$$a_{m-1}=T(v_{m-1},v_m),v_{m+1}=v_{m-1}-a_{m-1}{v}_m.$$

From (1) we know , whence

Because $v_0,v_1,v_2,\mathrm{\dots }$ is a strictly decreasing sequence of nonnegative integers, there is some $N\ge 2$ for which

$$v_N>0,v_{N+1}=0.$$

Thus for $0\le m\le N-1$,

$$a_m=T(v_m,v_{m+1}),v_m=a_m{v}_{m+1}+v_{m+2},$$ (2)

and

with

$$v_0=p,v_1=q,v_{N+1}=0.$$

∎

Theorem 2.

For $p\mathrm{>}q$,

$$v_N=\gcd (p,q).$$

Proof.

For $d\in {\mathbb{Z}}_{\ge 1}$, say $d\mid \gcd (p,q)$, and so $d\mid v_0$ and $d\mid v_1$. For $0\le m\le N-1$, suppose that $d\mid v_m$ and $d\mid v_{m+1}$. Then using (2) we get $d\mid v_{m+2}$. By induction, for each $0\le m\le N-1$ it holds that $d\mid v_m$ and $d\mid v_{m+1}$. In particular, for $m=N-1$ it holds that $d\mid v_N$.

Say $d\mid v_N$. By (2) we have $v_{N-1}=a_{N-1}{v}_N+v_{N+1}$, and by definition of $N$ we have $v_{N+1}=0$, whence $d\mid v_{N-1}$. For $0\le m\le N-1$, suppose that $d\mid v_{N-m}$ and $d\mid v_{N-1-m}$. By (2) we have

$$v_{N-1-m}=a_{N-1-m}{v}_{N-m}+v_{N-m+1},$$

from which we get $d\mid v_{N-m+1}$. By induction, for each $0\le m\le N-1$ it holds that $d\mid v_{N-m}$ and $d\mid v_{N-1-m}$. In particular, for $m=N-1$ we get $d\mid v_1$ and $d\mid v_0$, which means $d\mid \gcd (p,q)$. We have established that for $d\in {\mathbb{Z}}_{\ge 1}$, $d\mid \gcd (p,q)$ if and only if $d\mid v_N$, which proves the claim. ∎

Example.

For example, let $p=60$, $q=26$, cf. Fowler [22, pp. 25–28]. Then

$$v_0=60,v_1=26.$$

Then

$$a_0=T(v_0,v_1)=T(60,26)=2$$

and

$$v_2=v_0-a_0{v}_1=60-2\cdot 26=8.$$

Then

$$a_1=T(v_1,v_2)=T(26,8)=3$$

and

$$v_3=v_1-a_1{v}_2=26-3\cdot 8=2.$$

Then

$$a_2=T(v_2,v_3)=T(8,2)=4$$

and

$$v_4=v_2-a_2{v}_3=8-4\cdot 2=0.$$

As $v_0=a_0{v}_1+v_2$,

$$v_0:v_1=a_0+v_2:v_1.$$

As $v_1=a_1{v}_2+v_3$,

$$v_1:v_2=a_1+v_3:v_2.$$

As $v_2=a_2{v}_3+v_4$,

$$v_2:v_3=a_2+v_4:v_3.$$

Thus, as $v_4=0$,

$v_0:v_1$ $=a_0+v_2:v_1$

$=a_0+{(v_1:v_2)}^{-1}$

$=a_0+{(a_1+v_3:v_2)}^{-1}$

$=a_0+{(a_1+{(v_2:v_3)}^{-1})}^{-1}$

$=a_0+{(a_1+{(a_2+v_4:v_3)}^{-1})}^{-1}$

$=a_0+{(a_1+a_2^{-1})}^{-1},$

that is,

$$60:26={(2+{(3+4^{-1})}^{-1})}^{-1}.$$

∎

We can write (2),

$$v_m=a_m{v}_{m+1}+v_{m+2},$$

using matrices:

(3)

with $a_m=T(v_m,v_{m+1})$, for $0\le m\le N-1$. For $0\le n\le N-1$,

in particular, for $n=N-1$ and as $v_{N+1}=0$,

For $0\le n\le N-1$, using (3) and

we get

Define

(4)

so

yielding

$$\left(\begin{array}{c}\hfill p_n\hfill \\ \hfill q_n\hfill \end{array}\right)=\left(\begin{array}{c}\hfill a_n{p}_{n-1}+p_{n-2}\hfill \\ \hfill a_n{q}_{n-1}+q_{n-2}\hfill \end{array}\right).$$

Now,

and

We have

so for $n=N-1$, as $v_0=p$, $v_1=q$, $v_N=\mathrm{gcm}(p,q)$, $v_{N+1}=0$,

(5)

Taking determinants of (4),

$$p_n{q}_{n-1}-p_{n-1}{q}_n={(-1)}^{n+1}.$$ (6)

For $n=N-1$, (5) and (6) we get

$$p{q}_{N-2}-q{p}_{N-2}={(-1)}^N{v}_N.$$ (7)

Finally, (6) tells us

$$\frac{p_n}{q_n}-\frac{p_{n-1}}{q_{n-1}}=\frac{{(-1)}^{n+1}}{q_{n-1}{q}_n},$$

thus by (5),

$$\frac{p}{q}-\frac{p_{n-1}}{q_{n-1}}=\sum _{m=n}^{N-1}\frac{{(-1)}^{m+1}}{q_{m-1}{q}_m}.$$

Christianidis [10] surveys occurences of linear indeterminate equations in Greek mathematics.

The formula (7) shows a connection of the Euclidean algorithm with the kuttaka algorithm of Aryabhata and Bhaskara I for determining, given positive integers $a,b,c$, those positive integers $x$ and $y$ such that

$$ax-by=c.$$

See Datta and Singh [15, II, pp. 87–125, §13], Heath [31, pp. 281–285], and Neugebauer [50, pp. 1117–1120, VI C 4, 2].

5 Elements VII.1–3

Mueller [47, p. 11] explains the format of the propositions in the Elements. A usual proposition has the format protasis, ekthesis, diorismos, kataskeuē, apodeixis, and sumperasma. The protasis is the statement of the proposition. The ekthesis instantiates typical objects that are going to be worked with. The diorismos asserts that to prove the proposition it suffices to prove something about the instantiated objects. The kataskeuē constructs things using the instantiated object. The apodeixis proves the claim of the diorismos. The sumperasma asserts that the proposition is proved by what has been done with the instantiated objects.

Euclid, Elements VII.1 [30, p. 296]:

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.

Proof.

Let $AB,CD\in {\mathbb{Z}}_{\ge 2}$ with $AB>CD$, and suppose that when the less is continually subtracted in turn from the greater, the number that is left never measures the one before it until a unit is left. Suppose by contradiction that the numbers are not relatively prime, with $E=\mathrm{gcm}(AB,CD)\in {\mathbb{Z}}_{\ge 2}$. Let

$$AB=AF+FB=AF+T(AB,CD)\cdot CD,$$ (8)

with . Euclid uses without statement that $AF>1$. Let

$$CD=CG+GD=CG+T(CD,AF)\cdot AF,$$ (9)

with . Euclid uses without statement that $CG>1$. Let

$$AF=AH+HF=AH+T(AF,CG)\cdot CG,$$ (10)

with . Euclid then declares that $AH=1$. Now, because $E\mid AB$ and $E\mid CD$, using (8) it follows that $E\mid AF$. Because $E\mid CD$ and $E\mid AF$, using (9) it follows that $E\mid CG$. Because $E\mid AF$ and $E\mid CG$, using (10) it follows that $E\mid AH$. But $AH=1$ and $E\in {\mathbb{Z}}_{\ge 2}$, so this is false. Therefore the numbers $AB$ and $CD$ are relatively prime. ∎

Elements VII.1 is translated and briefly commented on by Burnyeat [7, pp. 29–31], in an essay about why Plato encouraged studying mathematics.

Euclid, Elements VII.2 [30, p. 298]:

Given two numbers not prime to one another, to find their greatest common measure.

Proof.

Let $AB$ and $CD$ be numbers that are not relatively prime, with $AB>CD$. If $CD\mid AB$ then $\mathrm{gcm}(AB,CD)=CD$.

If $CD\nmid AB$, let

$$AB=AE+EB=AE+T(AB,CD)\cdot CD,$$ (11)

with . As $CD\nmid AB$, $AE\ne 0$, and if $AE=1$ then by Elements VII.1 it follows that $AB$ and $CD$ are relatively prime, contrary to what has been assumed. Therefore $AE\in {\mathbb{Z}}_{\ge 2}$. Furthermore, because $AB$ and $CD$ have some common measure $\mu \in {\mathbb{Z}}_{\ge 2}$, by (11) this $\mu$ is a common measure of $CD$ and $AE$. Let

$$CD=CF+FD=CF+T(CD,AE)\cdot AE.$$ (12)

Euclid uses without statement that $CF\ne 0$. If $CF=1$ then by Elements VII.1, $CD$ and $AE$ are relatively prime, contradicting that $\mu \in {\mathbb{Z}}_{\ge 2}$ is a common measure of them. Euclid then declares that $CF\mid AE$. Now, by (12) we have

$$FD=T(CD,AE)\cdot AE,$$

so $AE\mid FD$, and with $CF\mid AE$ this implies $CF\mid FD$. But $CF+FD=CD$, and because $CF\mid FD$ and $CF\mid CF$ we get $CF\mid CD$. But by (11),

$$EB=T(AB,CD)\cdot CD,$$

so $CD\mid EB$, and with $CF\mid CD$ this implies $CF\mid EB$. Therefore, $CF\mid EB$ and $CF\mid AE$, and with $AB=AE+EB$ this implies $CF\mid AB$. Therefore, $CF\mid AB$ and $CF\mid CD$, namely $CF$ is a common measure of $AB$ and $CD$.

Now suppose by contradiction that $CF$ is not the greatest common measure of $AB$ and $CD$. Then there is some $G\in {\mathbb{Z}}_{\ge 2}$ with $G>CF$ that is a common measure of $AB$ and $CD$. Because $G\mid CD$ and $CD\mid EB$, we get $G\mid EB$. But $AB=AE+EB$, and $G\mid AB$ by hypothesis, so it follows that $G\mid AE$. Now, $AE\mid FD$, so $G\mid FD$. And $CD=CF+FD$, so $G\mid FD$ and $G\mid CD$ together imply $G\mid CF$. This means that the greater measures the less, which is false. Therefore there is no number greater than $CF$ that measures both $AB$ and $CD$, which means that $CF$ is the greatest common measure of $AB$ and $CD$. ∎

The Porism to Elements VII.2 states, “From this it is manifest that, if a number measure two numbers, it will also measure their greatest common measure.”

Proclus, Commentary on the First Book of Euclid’s Elements 301–302 [46, p. 236], calls determining the greatest common measure of two commensurable magnitudes a “porism”:

“Porism” is a geometrical term and has two meanings. We call “porism” a theorem whose establishment is an incidental result of the proof of another theorem, a lucky find as it were, or a bonus for the inquirer. Also called “porisms” are problems whose solution requires discovery, not merely construction or simple theory. We must see that the angles at the base of an isosceles triangle are equal, and our knowledge in such cases is about already existing things. Bisecting an angle, constructing a triangle, taking away or adding a length – all these require us to make something. But to find the center of a given circle, or the greatest common measure of two given commensurable magnitudes, and the like – these lie in a sense between problems and theorems. For in these inquiries there is no construction of the things sought, but a finding of them. Nor is the procedure purely theoretical; for it is necessary to bring what is sought into view and exhibit it before the eyes. Such are the porisms that Euclid composed and arranged in three books.

cf. Commentary 278 [46, p. 217]. Pappus of Alexandria, Collection VII.14 [39, p. 96]:

That the ancients best knew the distinction between these three things, is clear from their definitions. For they said that a theorem is what is offered for proof of what is offered, a problem what is proposed for construction of what is offered, a porism what is offered for the finding of what is offered.

Euclid, Elements VII.3 [30, p. 300]:

Given three numbers not prime to one another, to find their greatest common measure.

Proof.

Let $A,B,C$ be numbers that are not relatively prime. By Elements VII.2, let $D$ be the greatest common measure of $A$ and $B$. Either $D\mid C$ or $D\nmid C$. In the first case, $D\mid C$ and then $D$ measures each of $A,B,C$, hence is a common measure of $A,B,C$. Suppose by contradiction that there is some number $E$ that is a common measure of $A,B,C$ such that $E>D$. As $E$ measures each of $A,B$, by Elements VII.2, Porism $E$ measures their greatest common measure $D$. But then the greater measures the less, which is false. Therefore $D$ is the greatest common measure of $A,B,C$.

In the second case, $D\nmid C$. Because $A,B,C$ are not relatively prime, some number $M\in {\mathbb{Z}}_{\ge 2}$ is their common measure. This number measures $A,B$ hence by Elements VII.2, Porism measures the greatest common measure $D$ of $A,B$. But $M\mid C$ and $M\mid D$ shows, as $M\in {\mathbb{Z}}_{\ge 2}$, that $C$ and $D$ are not relatively prime. By Elements VII.2, let $E$ be the greatest common measure of $C$ and $D$. Because $E\mid D$ and $D\mid A$ it follows that $E\mid A$, and because $E\mid D$ and $D\mid B$ it follows that $E\mid B$. But also $E\mid C$, so $E$ is a common measure of $A,B,C$. Suppose by contradiction that $E$ is not the greatest common measure of $A,B,C$, so there is a number $F$ that is a common measure of $A,B,C$ with $F>E$. Because $F$ measures $A,B,C$, it measures $A,B$ and hence by Elements VII.2, Porism we get that $F$ measures the greatest common measure of $A,B$, i.e. $F\mid D$. But also $F\mid C$, and because $F$ measures $C,D$, by Elements VII.2, Porism we have that $F$ measures the greatest common measure of $C,D$, that is $F\mid E$. But then the greater measures the less, which is false, showing that $E$ is the greatest common measure of $A,B,C$. ∎

Aristotle writes about generalization from a chance case in Posterior Analytics, A.4, 73b32f.

On induction in Euclid, see Mueller [47, pp. 68–69] and Itard [38]. Itard [38, p. 73] writes:

Cependant on peut trouver quelques démonstrations par récurrence ou induction complète. On ne trouvera jamais le leitmotiv moderne, un peu pédant: «  nous avons vérifié la propriété pour 2, nous avons montré que si elle est vraie pour un nombre, elle est vraie pour son suivant, donc elle est générale »et ceux qui ne voient l’induction complète qu’accompagnée de sa rengaine auront le droit de dire qu’on ne la trouve par dans les Eléments.
Pour nous, nous la voyons dans les prop. 3, 27 et 36, VII, 2, 4 et 13, VIII, 8 et 9, IX.

For example, Euclid’s proof of VII.8, VII.12, and VII.14. Euclid’s proof of XI.20 does the case where $A,B,C$ are given prime numbers, and lets $ED$ be the least number measured by $A,B,C$, and takes $EF=ED+DF=ED+1$.

Proclus 381–382 [46, pp. 300–301], on Elements I.32 (Proclus refers to Timaeus 53c):

We can now say that in every triangle the three angles are equal to two right angles. But we must find a method of discovering for all the other rectilineal polygonal figures – for four-angled, five-angled, and all the succeeding many-sided figures – how many right angles their angles are equal to. First of all, we should know that every rectilineal figure may be divided into triangles, for the triangle is the source from which all things are constructed, as Plato teaches us when he says, “Every rectilineal plane face is composed of triangles.” Each rectilineal figure is divisible into triangles two less in number than the number of its sides: if it is a four-sided figure, it is divisible into two triangles; if five-sided, into three; and if six-sided, into four. For two triangles put together make at once a four-sided figure, and this difference between the number of the constituent triangles and the sides of the first figure composed of triangles is characteristic of all succeeding figures. Every many-sided figure, therefore, will have two more sides than the triangles into which it can be resolved. Now every triangle has been proved to have its angles equal to two right angles. Therefore the number which is double the number of the constituent triangles will give the number of right angles to which the angles of a many-sided figure are equal. Hence every four-sided figure has angles equal to four right angles, for it is composed of two triangles; and every five-sided figure, six right angles; and similarly for the rest.

Proclus 422 [46, pp. 334–335], on Elements I.45:

For any rectilineal figure, as we said earlier, is as such divisible into triangles, and we have given the method by which the number of its triangles can be found. Therefore by dividing the given rectilineal figure into triangles and constructing a parallelogram equal to one of them, then applying parallelograms equal to the others along the given straight line – that line to which we made the first application – we shall have the parallelogram composed of them equal to the rectilineal figure composed of the triangles, and the assigned task will have been accomplished. That is, if the rectilineal figure has ten sides, we shall divide it into eight triangles, construct a parallelogram equal to one of them, and then by applying in seven steps parallelograms equal to each of the others, we shall have what we wanted.

Netz [49, pp. 268–269]:

The Greeks cannot speak of ‘$A_1,A_2,\mathrm{\dots },A_n$’. What they must do is to use, effectively, something like a dot-representation: the general set of numbers is represented by a diagram consisting of a definite number of lines. Here the generalisation procedure becomes very problematic, and I think the Greeks realised this. This is shown by their tendency to prove such propositions with a number of numbers above the required minimum. This is an odd redundancy, untypical of Greek mathematical economy, and must represent what is after all a justified concern that the minimal case, being also a limiting case, might turn out to be unrepresentative. The fear is justified, but the case of $n=3$ is only quantitatively different from the case of $n=2$. The truth is that in these propositions Greek actually prove for particular cases, the generalisation being no more than a guess; arithmeticians are prone to guess.
To sum up: in arithmetic, the generalisation is from a particular case to an infinite multitude of mathematically distinguishable cases. This must have exercised the Greeks. They came up with something of a solution for the case of a single infinity. The double infinity of sets of numbers left them defenceless. I suspect Euclid was aware of this, and thus did not consider his particular proofs as rigorous proofs for the general statement, hence the absence of the sumperasma. It is not that he had any doubt about the truth of the general conclusion, but he did feel the invalidity of the move to that conclusion.
The issue of mathematical induction belongs here.
Mathematical induction is a procedure similar to the one described in this chapter concerning Greek geometry. It is a procedure in which generality is sustained by repeatability. Here the similarity stops. The repeatability, in mathematical induction, is not left to be seen by the well-educated mathematical reader, but is proved. Nothing in the practices of Greek geometry would suggest that a proof of repeatability is either possible or necessary. Everything in the practices of Greek geometry prepares one to accept the intuition of repeatability as a substitute for its proof. It is true that the result of this is that arithmetic is less tightly logically principled than geometry – reflecting the difference in their subject matters. Given the paradigmatic role of geometry in this mathematics, this need not surprise us.

6 Part and parts

Definitions 3–7, 15 and 20 of Elements VII are the following [30, p. 277–278]:

3. A number is a part of a number, the less of the greater, when it measures the greater;
4. but parts when it does not measure it.
5. The greater number is a multiple of the less when it is measured by the less.
6. An even number is that which is divisible into two equal parts.
7. An odd number is that which is not divisible into two equal parts, or that which differs by an unit from an even number.
15. A number is said to multiply a number when that which is multiplied is added to itself as many times as there are units in the other, and thus some number is produced.
20. Numbers are proportional when the first is the same multiple, or the same part, or the same parts, of the second that the third is of the fourth.

Either we define an odd number to be a number that is not even, or we define an odd number as one that differs from an even number by a unit. In the first case, we then prove that an odd number differs from an even number by a unit. In the second case, we then prove that an odd number is not even and that any number is either even or odd.

Euclid, Elements VII.4 [30, p. 303]:

Any number is either a part or parts of any number, the less of the greater.

Taisbak [63, p. 31, Chapter 4] writes,

In order to “save” Euclid I prefer to understand 7.4 as a “nomenclatural” theorem designed to introduce the statement “$a$ is parts of $b$”.

For $A>B$ and $C>D$, we model “$B$ is the same parts of $A$ that $D$ is of $C$” as follow: there are $p,q\in {\mathbb{Z}}_{\ge 2}$, $p>q$, such that

$$A=p\cdot \mathrm{gcm}(A,B),B=q\cdot \mathrm{gcm}(A,B),C=p\cdot \mathrm{gcm}(C,D),D=q\cdot \mathrm{gcm}(C,D).$$

To say that $B$ is parts of $A$ we thus must be given $\mathrm{gcm}(A,B)$.

Proof.

Let $A,BC\in {\mathbb{Z}}_{\ge 2}$ with $A>BC$. Either $A,BC$ are relatively prime or they are not. If they are, $\mathrm{gcm}(A,BC)=1$. ∎

7 Music theory

Philolaus, Fragment 6a [36, pp. 146–147], from Nicomachus, Manual of Harmonics 9:

The magnitude of harmonia (fitting together) is the fourth (syllaba) and the fifth (di’ oxeian). The fifth is greater than the fourth by the ratio $9:8$ [a tone]. For from hypatē [lowest tone] to the middle string (mesē) is a fourth, and from the middle string to neatē [highest tone] is a fifth, but from neatē to the third string is a fourth, and from the third string to hypatē is a fifth. That which is in between the third string and the middle string is the ratio $9:8$ [a tone], the fourth has the ratio $4:3$, the fifth $3:2$, and the octave (dia pasōn) $2:1$. Thus the harmonia is five $9:8$ ratios [tones] and two dieses [smaller semitones]. The fifth is three $9:8$ ratios [tones] and a diesis, and the fourth two $9:8$ ratios [tones] and a diesis.

Huffman [36, p. 164] gives a nihil obstat for the following suggestion of Tannery. From the fifth $3:2$ take away the fourth $4:3$, getting the tone $9:8$, which is lesser than $4:3$. From $4:3$ take away $9:8$, getting $32:27$, which is greater than $9:8$. From $32:27$ take away $9:8$, getting the diesis $256:243$, which is lesser than $9:8$. This procedure can be continued. From $9:8$ take away $256:243$, getting the apotome $2187:2048$, which is greater than $256:243$. From $2187:2048$ take away $256:243$, getting the comma $531441:524288$, which is lesser than $256:243$.

Philolaus, Fragment 6b [36, p. 364], from Boethius, De Institutione Musica III.8 (according to Huffman, it is uncertain if this fragment is genuine):

Philolaus, then, defined these intervals and intervals smaller than these in the following way: diesis, he says, is the interval by which the ratio $4:3$ is greater than two tones. The comma is the interval by which the ratio $9:8$ is greater than two dieses, that is than two smaller semitones. Schisma is half of a comma, diaschisma half of a diesis, that is a smaller semitone.

Plato, Timaeus 36b [11, pp. 71–72]:

And he went on to fill up all the intervals of $\frac{4}{3}$ (i.e. fourths) with the interval $\frac{9}{8}$ (the tone), leaving over in each a fraction. This remaining interval of the fraction had its terms in the numerical proportion of $256$ to $243$ (semitone).

Szabó [62] assembles a philological argument that the Euclidean algorithm was created as part of the Pythagorean theory of music. Szabó [62, p. 136, Chapter 2.8] summarizes, “More precisely, this method was developed in the course of experiments with the monochord and was used originally to ascertain the ratio between the lengths of two sections on the monochord. In other words, successive subtraction was first developed in the musical theory of proportions.” Earlier in this work Szabó [62, pp. 28–29] says, “Euclidean arithmetic is predominantly of musical origin not just because, following a tradition developed in the theory of music, it uses straight lines (originally ‘sections of a string’) to symbolize numbers, but also because it uses the method of successive subtraction which was developed originally in the theory of music. However, the theory of odd and even clearly derives from an ‘arithmetic of counting stones’ (ψῆφοι), which did not originally contain the method of successive subtraction.”

8 Celestial cycles

Heath [28, p. 284] cites statements by Aulus Gellius, Pliny and Censorinus that in Athens, a day was defined to be the period from one sunset to the next. Geminus, Introduction to the Phenomena VIII [28, pp. 284–285]:

The ancients had before them the problem of reckoning the months by the moon, but the years by the sun. For the legal and oracular prescription that sacrifices should be offered after the manner of their forefathers was interpreted by all Greeks as meaning that they should keep the years in agreement with the sun and the days and months with the moon. Now reckoning the years according to the sun means performing the same sacrifices to the gods at the same seasons in the year, that is to say, performing the spring sacrifice always in the spring, the summer sacrifice in the summer, and similarly offering the same sacrifices from year to year at the other definite periods of the year when they fell due. For they apprehended that this was welcome and pleasing to the gods. The object in view, then, could not be secured in any other way than by contriving that the solstices and the equinoxes should occur in the same months from year to year. Reckoning the days according to the moon means contriving that the names of the days of the month shall follow the phases of the moon.

We define a day to be a period from a sunset to the next sunset, a synodic month to be a period from a new moon to the next new moon, and a tropical year to be a period from a vernal equinox and the next vernal equinox. Two days need not have the same number of seconds, but this discrepancy is tiny and we shall model the phenomena by taking the period from any sunset to the next and from any other sunset to the next to be the same, and we call this common period $D$. Likewise, we shall model the phenomena by taking the period from any vernal equinox to the next and from any other vernal equinox to the next to be the same, and we call this common period $Y$. Finally, we shall model the phenomena by taking the period of a large number $N$ of consecutive synodic months to be nearly $N\cdot M$, where $M$ is called the mean synodic month.

Define a hollow month as $H=29D$ and a full month as $F=30D$. Goldstein [24] presents the following derivation of the Metonic cycle. Let us take as given that (i) $Y$ is a little more than $365D$ and (ii) $12M$ is a little more than $354D$. We partition time into hollow and full months, and take as given that (iii) this is done in such a way that among $N$ consecutive synodic months, there are more full months than hollow months. From (iii) we get , i.e.

namely, a mean synodic month is greater than $29⁤1/2$ days and less than 30 days. Assume that $pY$ is nearly $NM$. Let $N=12p+q$, so $NM=12pM+qM$, and now,

so

By (i) and (ii), $Y-12M$ is nearly $11D$. Assume that the difference is small enough that $pY-12pM$ is nearly $11pD$, so $12pM$ is nearly $pY-11pD$, and then

Because $pY$ is nearly $NM$, this yields

and therefore

For , the ratio $(a+c):(b+d)$ is called the mediant of the ratios $a:b,c:d$. It is a fact that the mediant is greater than $a:b$ and less than $c:d$. Following Fowler [22, pp. 42–43], we first check

The mediant of $2:1$ and $3:1$ is . The mediant of $5:2$ and $3:1$ is . The mediant of $8:3$ and $3:1$ is $11:4>30:11$. The mediant of $8:3$ and $11:4$ is $19:7$, which satisfies . Let

$$p=19,q=7,N=12p+q=235.$$

Then in our model of the phenomena, $19Y$ is nearly $235M$. This is the Metonic cycle: in 19 years there are 110 hollow months and 125 full months, and $110H+125F=3190D+3750D=6940D$. See Geminus, Introduction to the Phenomena VIII [20].

Let $s$ be a second and let $d=24\cdot 60\cdot 60s=86400s$, called an ephemeris day. Take as granted that $Y$ is approximately $365.2421897d$ and that $M$ is approximately $29.53059d$. We compute that the anthyphairesis of $365.2421897:29.53059$ is

$$[12,2,1,2,1,1,17,3,\mathrm{\dots }]$$

Now, $[12,2,1,2]=99:8$, which corresponds to the octaeteris cycle of Cleostratus: in $8$ years there are 99 synodic months. Furthermore, $[12,2,1,2,1,1]=235:19$, which corresponds to the Metonic cycle: in 19 years there are 235 synodic months.

Aelian, Varia Historia, 10.7 [73, p. 319]:

The astronomer Oenopides of Chios dedicated at Olympia the famous bronze tablet on which he had inscribed the movements of the stars for fifty-nine years, what he called the Great Year. Note that the astronomer Meton of the deme Leuconoe set up pillars and recorded on them the solstices. He claimed to have discovered the Great Year and said it was nineteen years.

Zeeman [74] talks about gear ratios of the Antikythera mechanism. There is a sun gear with 64 teeth that meshes with a gear with 38 teeth that is paired with a gear with 48 teeth. The gear with 48 teeth meshes with a gear with 24 teeth that is paired with a gear with 127 teeth. The gear with 127 teeth meshes with a moon gear with 32 teeth. The gear ratios are $64:38$, $48:24$, $127:32$, and

$$\frac{64}{38}\cdot \frac{48}{24}\cdot \frac{127}{32}=\frac{254}{19}.$$

A sidereal year is close to $365.25636d$, and a sidereal month is close to $27.32166d$, and the anthyphairesis of $365.25636:27.32166$ is

$$[13,2,1,2,2,8,\mathrm{\dots }].$$

Now, $[13,2,1,2,2]=254:19$. (It is not a coincidence that $254=235+19$.)

Proclus, Commentary on Plato’s Timaeus IV.91–92 [3, pp. 169–170]:

Following the Demiurgic generation of the spheres and the procession of the seven bodies, and following their ensoulment and the order instituted among them by the Father, and after their various motions and the temporal measures of each of their periods and the differences among the completions of their cycles, the account has proceeded to the monad of time’s plurality and the single number in terms of which every motion is measured – a measure by which all the other measures have been encompassed and in terms of which the entire life of the cosmos has been defined, as well as the diverse articulation of bodies and the universal lifespan that takes place across the all-perfect period. Now this number is one that must not be thought about in a manner that corresponds to opinion – just successively adding ten thousands upon ten thousands – for there are people who are accustomed to speak this way. They take an accurate figure for the completion of the Moon’s cycle and likewise for the Sun and multiply both; then they multiply these by the complete cycle for Mercury on top of this, and then that for Venus on top of these, and then Mars to all that, and then similarly for Jupiter and the remaining cycle for Saturn. On top of all that, they take the complete cycle for the sphere of the fixed stars and make the single and common complete cycle of the planets. Anyway, they could talk about it in this manner, if in fact the times for the completion of the cycles were prime to one another. If, however, they aren’t prime to one another, then they will need to take their common measure and see how many times this number goes into each of the periods it takes for the completion of a cycle. Then, taking the number of times this goes into the smallest one, they multiply the larger number by it. Conversely, taking the number of times this goes into the larger number, they will need to multiply the smaller number by that. By means of both of these operations of multiplication they will arrive at the same period which is common to both of the complete cycles – a period which is thus time measured by both of them. These are the sorts of things that people like that say.

9 Aristarchus

Aristarchus, On the Sizes and Distances of the Sun and Moon, Proposition 13 [28, p. 397] asserts that $7921:4050>88:45$. This can be obtained as follows using continued fractions.

$7921=4050+3871$, $4050=3871+179$, thus $\frac{7921}{4050}=1+\frac{3871}{4050}$ and $\frac{4050}{3871}=1+\frac{179}{3871}$, so

$$\frac{7921}{4050}=1+\frac{3871}{4050}=1+\frac{1}{1+{\displaystyle \frac{179}{3871}}}.$$

Next, $3871=21\cdot 179+112$, $179=112+67$, thus

$$\frac{3871}{179}=21+\frac{112}{179}=21+\frac{1}{1+{\displaystyle \frac{67}{112}}},$$

hence

$$\frac{7921}{4050}=1+\frac{1}{1+{\displaystyle \frac{1}{21+{\displaystyle \frac{1}{1+{\displaystyle \frac{67}{112}}}}}}}$$

Finally, $112=67+45$, whence

$$\frac{7921}{4050}=1+\frac{1}{1+{\displaystyle \frac{1}{21+{\displaystyle \frac{1}{1+{\displaystyle \frac{1}{1+{\displaystyle \frac{45}{67}}}}}}}}}.$$

Then

$$1+\frac{1}{1+{\displaystyle \frac{1}{21+{\displaystyle \frac{1}{1+{\displaystyle \frac{1}{1+0}}}}}}}=\frac{88}{45}$$

is an approximation from below to $\frac{7921}{4050}$.

Proposition 15 [28, p. 407], asserts that $71755875:61735500>43:37$. This can be found as follows.

$$v_0=71755875,v_1=61735500.$$

Then

$$a_0=T(71755875,61735500)=1,v_2=71755875-1\cdot 61735500=10020375.$$

Then

$$a_1=T(61735500,10020375)=6,v_3=61735500-6\cdot 10020375=1613250.$$

Then

$$a_2=T(10020375,1613250)=6,v_4=10020375-6\cdot 1613250=340875.$$

Then

$$[a_0,a_1,a_2]=1+\frac{1}{6+{\displaystyle \frac{1}{6}}}=\frac{43}{37}.$$

On the other hand,

${\displaystyle \frac{71755875}{61735500}}$ $=1+{\displaystyle \frac{1}{6+{\displaystyle \frac{1}{6+{\displaystyle \frac{340875}{1613250}}}}}}.$

10 Ptolemy

Ptolemy, Almagest I.67.22 says the following [17, p. 91, Fragment 41]:

I have taken the arc from the northernmost limit to the most southerly, that is the arc between the tropics, as being always ${47}^{\circ }$ and more than two-thirds but less than three-quarters of a degree, which is nearly the same estimate as that of Eratosthenes and which Hipparchus also used; for the arc between the tropics amounts to almost exactly 11 of the units of which the meridian contains 83.

Theon of Alexandria, Commentary on Ptolemy’s Almagest, writes the following about this passage:

This ratio is nearly the same as that of Eratosthenes, which Hipparchus also used because it had been accurately measured; for Eratosthenes determined the whole circle as being 83 units, and found that part of it which lies between the tropics to be 11 units; and the ratio ${360}^{\circ }:{47}^{\circ }{42}^{\prime }{40}^{\prime \prime }$ is the same as $83:11$.

In fact, ${360}^{\circ }:{47}^{\circ }{\mathrm{\hspace{0.17em}42}}^{\prime }{\mathrm{\hspace{0.17em}40}}^{\prime \prime }=16200:2147$, and using the Euclidean algorithm we get $16200:2147=[7,1,1,5,195]$, from which we get the approximations

$$7,8,15:2,83:11,16200:2147.$$

11 Theon of Alexandria

Theon of Alexandria, in his Commentary on Ptolemy’s Almagest, I.10, writes [66, pp. 50–53]:

Conversely, let it be required to divide a given number by a number expressed in degrees, minutes and seconds. Let the given number be ${1515}^{\circ }{\mathrm{\hspace{0.17em}20}}^{\prime }{\mathrm{\hspace{0.17em}15}}^{\prime \prime }$; and let it be required to divide this by ${25}^{\circ }{\mathrm{\hspace{0.17em}12}}^{\prime }{\mathrm{\hspace{0.17em}10}}^{\prime \prime }$, that is, to find how often ${25}^{\circ }{\mathrm{\hspace{0.17em}12}}^{\prime }{\mathrm{\hspace{0.17em}10}}^{\prime \prime }$ is contained in ${1515}^{\circ }{\mathrm{\hspace{0.17em}20}}^{\prime }{\mathrm{\hspace{0.17em}15}}^{\prime \prime }$.

These numbers are

$${1515}^{\circ }{\mathrm{\hspace{0.17em}20}}^{\prime }{\mathrm{\hspace{0.17em}15}}^{\prime \prime }=1515+20:60+15:{60}^2,{25}^{\circ }{\mathrm{\hspace{0.17em}12}}^{\prime }{\mathrm{\hspace{0.17em}10}}^{\prime \prime }=25+12:60+10:{60}^2.$$

Theon works out the approximation

$${1515}^{\circ }{\mathrm{\hspace{0.17em}20}}^{\prime }{\mathrm{\hspace{0.17em}15}}^{\prime \prime }:{25}^{\circ }{\mathrm{\hspace{0.17em}12}}^{\prime }{\mathrm{\hspace{0.17em}10}}^{\prime \prime }\sim {60}^{\circ }{\mathrm{\hspace{0.17em}7}}^{\prime }{\mathrm{\hspace{0.17em}33}}^{\prime \prime }.$$

We obtain this using the Euclidean algorithm. Theon’s calculation resembles this but is different. We have

$$v_0={1515}^{\circ }{\mathrm{\hspace{0.17em}20}}^{\prime }{\mathrm{\hspace{0.17em}15}}^{\prime \prime },v_1={25}^{\circ }{\mathrm{\hspace{0.17em}12}}^{\prime }{\mathrm{\hspace{0.17em}10}}^{\prime \prime }.$$

$T(v_0,v_1)=60$, and

$v_2$ $=v_0-T(v_0,v_1)\cdot v_1$

$={1515}^{\circ }{\mathrm{\hspace{0.17em}20}}^{\prime }{\mathrm{\hspace{0.17em}15}}^{\prime \prime }-60\cdot ({25}^{\circ }{\mathrm{\hspace{0.17em}12}}^{\prime }{\mathrm{\hspace{0.17em}10}}^{\prime \prime })$

$={1515}^{\circ }{\mathrm{\hspace{0.17em}20}}^{\prime }{\mathrm{\hspace{0.17em}15}}^{\prime \prime }-{1500}^{\circ }-60\cdot ({12}^{\prime }{\mathrm{\hspace{0.17em}10}}^{\prime \prime })$

$={15}^{\circ }{\mathrm{\hspace{0.17em}20}}^{\prime }{\mathrm{\hspace{0.17em}15}}^{\prime \prime }-60\cdot ({12}^{\prime }{\mathrm{\hspace{0.17em}10}}^{\prime \prime })$

$={920}^{\prime }{\mathrm{\hspace{0.17em}15}}^{\prime \prime }-{720}^{\prime }-60\cdot {10}^{\prime \prime }$

$={200}^{\prime }{\mathrm{\hspace{0.17em}15}}^{\prime \prime }-60\cdot {10}^{\prime \prime }$

$={200}^{\prime }{\mathrm{\hspace{0.17em}15}}^{\prime \prime }-{10}^{\prime }$

$={190}^{\prime }{\mathrm{\hspace{0.17em}15}}^{\prime \prime }.$

$T(v_1,v_2)=7$, and

$v_3$ $=v_1-T(v_1,v_2)\cdot v_2$

$={25}^{\circ }{\mathrm{\hspace{0.17em}12}}^{\prime }{\mathrm{\hspace{0.17em}10}}^{\prime \prime }-7\cdot ({190}^{\prime }{\mathrm{\hspace{0.17em}15}}^{\prime \prime })$

$={1512}^{\prime }{\mathrm{\hspace{0.17em}10}}^{\prime \prime }-7\cdot {190}^{\prime }-7\cdot {15}^{\prime \prime }$

$={182}^{\prime }{\mathrm{\hspace{0.17em}10}}^{\prime \prime }-{105}^{\prime \prime }$

$={180}^{\prime }{\mathrm{\hspace{0.17em}130}}^{\prime \prime }-{105}^{\prime \prime }$

$={180}^{\prime }{\mathrm{\hspace{0.17em}25}}^{\prime \prime }.$

$T(v_2,v_3)=1$, and

$v_4$ $=v_2-T(v_2,v_3)\cdot v_3$

$={190}^{\prime }{\mathrm{\hspace{0.17em}15}}^{\prime \prime }-1\cdot {180}^{\prime }{\mathrm{\hspace{0.17em}25}}^{\prime \prime }$

$={10}^{\prime }{\mathrm{\hspace{0.17em}15}}^{\prime \prime }-{25}^{\prime \prime }$

$=9^{\prime }{\mathrm{\hspace{0.17em}75}}^{\prime \prime }-{25}^{\prime \prime }$

$=9^{\prime }{\mathrm{\hspace{0.17em}50}}^{\prime \prime }.$

$T(v_3,v_4)=18$, and

$v_5$ $=v_3-T(v_3,v_4)\cdot v_4$

$={180}^{\prime }{\mathrm{\hspace{0.17em}25}}^{\prime \prime }-18\cdot (9^{\prime }{\mathrm{\hspace{0.17em}50}}^{\prime \prime })$

$={18}^{\prime }{\mathrm{\hspace{0.17em}25}}^{\prime \prime }-18\cdot {50}^{\prime \prime }$

$={18}^{\prime }{\mathrm{\hspace{0.17em}25}}^{\prime \prime }-{900}^{\prime \prime }$

$=3^{\prime }{\mathrm{\hspace{0.17em}925}}^{\prime \prime }-{900}^{\prime \prime }$

$=3^{\prime }{\mathrm{\hspace{0.17em}25}}^{\prime \prime }.$

$T(v_4,v_5)=2$, and

$v_6$ $=v_4-T(v_4,v_5)\cdot v_5$

$=9^{\prime }{\mathrm{\hspace{0.17em}50}}^{\prime \prime }-2\cdot (3^{\prime }{\mathrm{\hspace{0.17em}25}}^{\prime \prime })$

$=3^{\prime }.$

$T(v_5,v_6)=1$, and

$v_7$ $=v_5-T(v_5,v_6)\cdot v_6$

$=3^{\prime }{\mathrm{\hspace{0.17em}25}}^{\prime \prime }-1\cdot 3^{\prime }$

$={25}^{\prime \prime }.$

$T(v_6,v_7)=7$, and

$v_8$ $=v_6-T(v_6,v_7)\cdot v_7$

$=3^{\prime }-7\cdot {25}^{\prime \prime }$

$={180}^{\prime \prime }-7\cdot {25}^{\prime \prime }$

$=5^{\prime \prime }.$

$T(v_7,v_8)=5$, and

$v_9$ $=v_7-T(v_7,v_8)\cdot v_8$

$={25}^{\prime \prime }-5\cdot 5^{\prime \prime }$

$=0.$

This shows that

$${1515}^{\circ }{\mathrm{\hspace{0.17em}20}}^{\prime }{\mathrm{\hspace{0.17em}15}}^{\prime \prime }:{25}^{\circ }{\mathrm{\hspace{0.17em}12}}^{\prime }{\mathrm{\hspace{0.17em}10}}^{\prime \prime }=[60,7,1,18,2,1,7,5].$$

Now,

$$[60,7,1,18]=9079:151={60}^{\circ }{\mathrm{\hspace{0.17em}7}}^{\prime }{\mathrm{\hspace{0.17em}32}}^{\prime \prime }{\mathrm{\hspace{0.17em}58}}^{\prime \prime \prime }{\mathrm{\hspace{0.17em}48}}^{\prime \prime \prime \prime }\mathrm{\dots }\sim {60}^{\circ }{\mathrm{\hspace{0.17em}7}}^{\prime }{\mathrm{\hspace{0.17em}33}}^{\prime \prime },$$

the approximation calculated by Theon.

12 Commentators

Nicomachus of Gerasa, Introduction to Arithmetic I.XIII.10–13 [14, pp. 206–207]:

We shall now investigate how we may have a method of discerning whether numbers are prime and incomposite, or secondary and composite, relatively to each other, since of the former unity is the common measure, but of the latter some other number also besides unity; and what this number is.
Suppose there be given us two odd numbers and some one sets the problem and directs us to determine whether they are prime and incomposite relatively to each other or secondary and composite, and if they are secondary and composite what number is their common measure. We must compare the given numbers and subtract the smaller from the larger as many times as possible; then after this subtraction subtract in turn from the other, as many times as possible; for this changing about and subtraction from one and the other in turn will necessarily end either in unity or in some one and the same number, which will necessarily be odd. Now when the subtractions terminate in unity they show that the numbers are prime and incomposite relatively to each other; and when they end in some other number, odd in quantity and twice produced,’ then say that they are secondary and composite relatively to each other, and that their common measure is that very number which twice appears.
For example, if the given numbers were 23 and 45, subtract 23 from 45, and 22 will be the remainder; subtracting this from 23, the remainder is 1, subtracting this from 22 as many times as possible you will end with unity. Hence they are prime and incomposite to one another, and unity, which is the remainder, is their common measure.
But if one should propose other numbers, 21 and 49, I subtract the smaller from the larger and 28 is the remainder. Then again I subtract the same 21 from this, for it can be done, and the remainder is 7. This I subtract in turn from 21 and 14 remains; from which I subtract 7 again, for it is possible, and 7 will remain. But it is not possible to subtract 7 from 7; hence the termination of the process with a repeated 7 has been brought about, and you may declare the original numbers 21 and 49 secondary and composite relatively to each other, and 7 their common measure in addition to the universal unit.

Martianus Capella, The Marriage of Philology and Mercury, VII, 785 [61, p. 306]:

If two numbers are composite to one another, a greater and a smaller, how can their largest and their smallest common measure be found? From the larger number let the smaller be subtracted as often as possible; then let whatever amount is left from the former [larger] number be subtracted from the smaller number as often as possible. The amount of the difference will be the greatest measure of these numbers. Take the numbers 350 and 100. Let one hundred be subtracted as often as possible from 350, which is three times. The remainder is 50. From the other number of the pair, one hundred, let 50 be subtracted; the remainder is 50. This number is the greatest common measure of 350 and 100; for fifty times two is one hundred, and fifty times seven is 350. From this calculation it becomes clear how one finds, of all the numbers which measure two numbers, their greatest common measure.

Iamblichus, Commentary on Nicomachus’s Arithmetic II.98–99 [70, p. 97]:

98. Il est au contraire possible d’être second en soi sans l’être en relation. Si deux impairs sont pris au hasard pour déterminer s’ils sont premiers ou seconds entre eux et, s’ils sont seconds, pour voir quelle mesure leur est commune, nous retrancherons toujours alternativement le petit du grand, autant de fois qu’il est possible, et le nombre restant du petit terme du début, et ainsi de suite, jusqu’à finir soit à l’unité, soit à un nombre quelconque, d’où plus aucune soustraction n’est possible, et ce nombre sera la mesure commune de ceux du début, qui seront dits seconds entre eux, tels 15 envers 35: leur mesure commune est cinq.
99. En revanche, l’unité désigne ces nombres comme premiers et non composés entre eux chaque fois que l’opération s’achève en elle: elle est la seule mesure commune des nombres de ce type.

Domninus of Larissa, Encheiridion 20–31 [54, pp. 111–115]:

20. Every number, when compared to an arbitrary number with regard to the multitude of monads in them, is either equal to it, or unequal. If they are equal to one another, their relationship to one another will be unique and not further distinguishable. For in the case of equality, one thing cannot be in this fashion and the other thing in that fashion, since what is equal is equal in one single and the same way. If, however, they are unequal, ten different relationships can be contemplated concurrently.
21. But before giving an account of these, we must state that it is true for every pair of numbers that the lesser is either a part, or parts, of the greater number, since, if it measures the greater one, it is a part of the greater number, such as in the case of 2 which measures 4 and 6, of which it is a half or a third part, respectively. If it does not measure it, it is parts of it, such as in case of 2, which, not measuring 3, is two thirds of it, or in the case of 9, which, not measuring 15, is three fifths of it.
22. Having stated this as a preliminary, we say that if those two numbers which lie before us for inspection are unequal, the lesser either measures the greater, or it does not.
23. If it measures it, the greater number is a multiple of the lesser one, and the lesser number is a submultiple of the greater one, as in the case of 3 and 9, since 9 is a multiple of 3, being its triple, and 3 is a submultiple of 9, being its subtriple.
24. If it does not measure the greater number, and if one subtracts it from it once or several times, it will leave behind something less than itself whch will, by necessity, be either a part, or parts, of the number. For it will leave behind either a monad or some number.
25. If it leaves behind a monad, it obviously leaves behind a part of itself. For the monad is part of every number, since every number is a combination of monads.
26. If it leaves behind some number, it will be either a part of itself, or parts. For it is true for every pair of numbers that the lesser is either a part, or parts, of the greater.
27. Now then, if the lesser number is subtracted once from the greater, and it leaves behind a number less than itself which is a part of it, then the greater number will be superparticular to the lesser, while the lesser number will be subsuperparticular to the greater, as in the case of 2 and 3. For 3 is superparticular to 2, since it includes it and a half of it (therefore, it is also called sesquialter of it), while 2 is subsesquialter to 3. And the same is the case with 6 and 8, as 8 is sesquitertian to 6, while 6 is subsesquitertian to 8.
28. If the remainder is parts of the lesser number, then the greater number will be superpartient, while the lesser number will be subsuperparticular to the greater, as in the case of 3 and 5. For 5 is superpartient to 3, since it includes it and two thirds of it (therefore, it is also called superbitertian of it), while 3 is subsuperbitertian to 5. And the same is the case with 15 and 24, as 24 is supertriquantan of 15, since it includes it and three fifths of it, while 15 is subsupertriquintan of 24.
29. If the lesser number is subtracted more often than once from the greater, and it leaves behind a number less than itself which is part of it, then the greater number will be multiple-superparticular, while the lesser number will be submultiple-superparticular to the greater, as in the case of 2 and 5. For 5 is multiple-superparticular to 2, since it includes it twice and a half of it (therefore, it is also called duplex-sesquialter of it), while 2 is subduplex-sesquialter to 5. And the same is the case with 6 and 26, as 26 is quadruplex-sesquitertian to 6, while 6 is subquadruplex-sesquitertian to 26.
30. If the remainder is parts of the lesser number, then the greater number is multiple-superpartient, while the lesser number is submultiple-superpartient to the greater, as in the case of 3 and 8. For 8 is duplex-superbitertian to 3, while 3 is subduplex-superbitertian to 8. And the same is the case with 10 and 34, as 34 is triplex-superbiquintan of 10, while 10 is subtriplex-superbiquintan of 34.
31. And these are the so-called ten relationships of inequality, to which the ancients also referred as ratios:

1. multiple,

2. submultiple,

3. superparticular,

4. subsuperparticular,

5. superpartient,

6. subsuperpartient,

7. multiple-superparticular,

8. submultiple-superparticular,

9. multiple-superpartient,

10. submultiple-superpartient.

This is the theory of numbers with regard to one another according to the multitude underlying them.

For example, take $1386$ and $238$. Then $1386=5\cdot 238+196$, in particular $238$ is not part of $1386$. Then $238=1\cdot 196+42$, $196=4\cdot 42+28$, $42=1\cdot 28+14$, $28=2\cdot 14+0$, showing that $\mathrm{gcm}(1386,238)=14$. $1386=99\cdot 7$ and $119=17\cdot 14$, so $119:1386=17:99$.

Boethius De institutione Arithmetica libri duo, Book I, Chapter 18 [26, pp. 21–22, §2], “On finding those numbers that are secondary and composite with respect to each other [and numbers that are] prime and incomposite relative to others”:

The method by which we can find such numbers, if someone proposes them to us and declares that it is not known whether they are commensurable in any measure or [whether] the unit alone measures each, is this. Should two unequal numbers be given, it will be necessary to subtract the smaller from the greater, and if what remains is greater, subtract the smaller from the greater again; [but] if it is smaller, subtract it from the greater [number] that remains, and this should be done until [either] unity finally prevents any further diminution, or, if each of the numbers proposed is odd, some number [is reached that is] necessarily odd; but you will see that the number which is left is equal to that [odd] number. And so it is that if this subtraction should, in turn, reach one, the numbers are said to be prime to each other necessarily and they are conjoined by no other measure except unity alone. If, however, the end of the subtraction arrives at some [odd] number as was said above, it will be a number that measures each sum, and we call the same number that remains the common measure of each.
Take two proposed numbers with respect to which we do not know whether some common measure measures them; let these be $9$ and $29$. Now we make an alternate subtraction. Let the smaller be subtracted from the greater, that is, $9$ from $29$, and $20$ is left; let us now again subtract the smaller, that is, $9$ from $20$, and $11$ is left; I again subtract $9$ from the remainder [i.e., $11$] and $2$ remains. If I subtract this from $9$, $7$ is left, and if I again take $2$ from $7$, $5$ remains; and from this another $2$ and $3$ remains, which after it is diminished by another $2$ leaves only unity. Again, if I subtract one from two, the end of the subtraction is fixed at one, which shows that there is no other common measure of these two numbers, namely $9$ and $29$. Therefore, we will call these numbers prime to each other.
But should other numbers be proposed in the same situation, that is $21$ and $9$, they could be investigated since they would be mutually related. Again I subtract the quantity of the smaller number from the greater, that is, $9$ from $21$, and $12$ remains. From $12$ I take $9$ and $3$ remains, which if subtracted from $9$ leaves $6$; and if $3$ were taken from $6$, $3$ would be left, from which $3$ cannot be subtracted for it is equal to it. For $3$, which was reached by continually subtracting, cannot be subtracted from $3$, since they are equal. Therefore, we shall pronounce them commensurable, and $3$, which is the remainder, is their common measure.

Asclepius of Tralles [65, pp. 44, 78], I.ρε

John Philoponus [34]

Scholia for Book VII [32].

13 Latin writers

Al-Nayrizi, Commentry on Euclid’s Elements, extant in a Latin translation by Gerard of Cremona [13, pp. 190–191], states Elements VII.2.

Gericke [23, p. 105] comments on Campanus, Book VII.

Campanus [9, pp. 230–231], Elements VII, Definitions:

(i) Unitas est qua unaqueque res dicitur una.
(ii) Numerus est multitudo ex unitatibus composita.
(iii) Naturalis series numerorum dicitur in qua secundum unitatis additionem fit ipsorum computatio.
(iv) Differentia numerorum appellatur numerus quo maior habundat a minore.
(v) Numerus primus dicitur, qui sola unitate metitur.
(vi) Numerus compositus dicitur, quem alius numerus metitur.
(vii) Numeri contra se dicuntur primi, qui nullo modo excepta sola unitate numerantur.
(viii) Numeri ad invicem compositi sive communicantes dicuntur, quos alius numerus quam unitas metitur nullusque eorum est ad alium primus.
(ix) Numerus per alium multiplicare dicitur qui totiens sibi coacervatur quotiens in multiplicante est unitas.
(x) Productus vero dicitur qui ex eorum multiplicatione crescit.
(xi) Numerus alium numerare dicitur qui secundum aliquem multiplicatus illum producit.
(xii) Pars est numerus numeri minor maioris cum minor maiorem numerat. Et qui numeratur numerantis multiplex appellatur.
(xiii) Denominans est numerus secundum quem pars sumitur in suo toto.
(xiv) Similes dicuntur partes que ab eodem numero denominantur.
(xv) Prima et simpla numeri pars est unitas.
(xvi) Quando duo numeri partem habuerint communem, tot partes maioris dicetur esse minor quotiens eadem pars fuerit in minore, tote vero quotiens ipsa fuerit in maiore.
(xvii) Numeri ad numerum dicitur proportio minoris quidem ad maiorem in eo quod maioris pars est aut partes. Maioris vero ad minorem secundum quod eum continet et eius partem vel partes.
(xviii) Cum fuerint quotlibet numeri continue proportionales dicetur proportio primi ad tertium sicut primi ad secundum duplicata, ad quartum vero triplicata.
(xix) Cum continuate fuerint eedem vel diverse proportiones, dicetur proportio primi ad ultimum ex omnibus composita.
(xx) Denominatio dicitur proportionis minoris quidem numeri ad maiorem pars vel partes ipsius minoris que in maiore sunt. Maioris autem ad minorem totum vel totum et pars vel partes prout maior superfluit.
(xxi) Similes sive una alii eadem dicuntur proportiones que eandem denominationem recipiunt. Maior vero que maiorem. Minor autem que minorem.
(xxii) Numeri vero quorum proportio una, proportionales appellantur.
(xxiii) Termini sive radices dicuntur quibus in eadem proportione minores sumi impossibile est.

Campanus [9, p. 231], Elements VII.1:

Si a maiore duorum numerorum minor detrahatur donec minus eo supersit, ac deinde de minore ipsum reliquum donecminus eo relinquatur, itemque a reliquo primo reliquum secundum quousque minus eo qui ante relictum numeret usque ad unitatem, eos duos numeros contra se primos esse necesse est.

Campanus [9, p. 232], Elements VII.2:

Propositis duobus numeris ad invicem compositis maximum numerum communem eos numerantem invenire. (Corollarium) Unde manifestum est quia omnis numerus duos numeros numerans numerat numerum maximum ambos numerantem.

Campanus [9, p. 233], Elements VII.3:

Propositis tribus numeris ad invicem compositis maximum numerorum eos communiter numerantium invenire.

Campanus [9, p. 234], Elements VII.4:

Omnium duorum numerorum inequalium minor maioris aut pars est aut partes.

Rommevaux [55]

Jordanus Nemorarius, De elementis arithmetice artis III.14 [8, pp. 87–88]:

Si sint duo numeri contra se primi minorque de maiore aliquotiens detrahatur, aut relinquetur unitas aut numerus ad detractum primus.
Ut $a$ et $b$ sint contra se primi detrahatur $a$ de $b$ quotienslibet sitque detractum $c$ et residuum $d$. Dico quod $d$ est primus ad $a$ vel est unitas. Si enim esset commensurabilis cum $a$, ponatur communis mensura $e$ numerabitque $e$ etiam $c$ per xxiii^am primi. Qui quia numerat $d$ palam quia numerabit et $b$. Sicque $a$ et $b$ erunt communicantes. Quod est contra ypothesim.

Book I, Proposition 23 says that if $b=(1/d)a$ and $c=(1/e)b$ then $c=(1/(d\cdot e))a$.

Jordanus Nemorarius, De elementis arithmetice artis III.15 [8, p. 88]:

Cum fuerint duo numeri contra se primi et minore de maiore quoad potest detracto residuum a prius detracto detrahatur, continua facta dectractione unitatem relinqui est necesse. Quod si unitas residua fuerit, positos numeros incommensurabiles esse conveniet.
Sit maior $a$, detractus $b$, residuus $c$. Qui si fuerit unitas, constat propsitio. Si autem numerus idem detrahatur quotiens potest de $b$ et relinquatur $d$ qui vel erit unitas vel numerus primus ad $c$. Itemque $d$ de $c$ detrahatur quotiens potest eritque residuum minus $d$ sitque $e$ quod vel erit unitas vel numerus primus ad $d$ per premissam. Qui si detrahatur a $d$ remanebit minus eo. Et quia hec diminutio non potest fieri in infinitum quod quidem esst si semper remaneret numerus ad detractum primus, restat ut unitas relinquatur. Patet igitur pars prima. Reliquum indirecte. Si enim ponerentur commensurabiles, numerum eos numerantem unitatem numerare convinceres per xii^am primi.

Johannes de Muris, Quadripartitum numerorum I.8 [41, pp. 154–155]:

Propositis tibi duobus numeris inequalibus, si an eos communis mensura metiatur agnoscere jubearis, sic age:
Aufer minorem de majori, vicibus alternatis, quousque detractio reciproca in aliquo numero steterit, si non usque pervenerit unitatem. Et quicumque numerus relictus fuerit ante nichil, ut nunc unitas numerus permutatur, pro communi maxima mensura procul dubio teneatur. Quod si aliquis numerus preter unitatem subtractionem finierit, ipse mensuram lucratus est et ipsos numeros secundarios et compositos fore non dubites. Si vero sola unitas superstes egreditur, ipsos esse contra se primos omni necessitate conclude.
Aliter ad idem. Cum omnis divisio sit quedam subtractio, non tamen convertitur, sicut omnis multiplicatio additio est et non contra. Datis duobus numeris inequalibus, divide majorem per minorem, et per residuum, si quod fuerit, divide divisorem et iterum residuum per minorem, quousque in tali alternata divisione nichil finaliter restiterit dividendum. Et si perventum fuerit usque ad unum, contra se primi numeri propositi constiterunt. Si vero aliquis numerus ante nichil evaserit, ipsos quidem numeros datos esse ad invicem compositos attestatur.

Theinred of Dover, De legitimis ordinibus pentachordorum et tetrachordorum I.xviii [60, pp. 176–181]

Prosdocimo [33]

Nicole Oresme [25]

14 Leonardo of Pisa

Leonardo of Pisa, The Book of Squares, Proposition 22 [59, p. 93]: “I wish to find in a given ratio the two differences among three squares.” That is, given $a,b\in {\mathbb{Z}}_{\ge 1}$, to find $x,y,z\in {ℝ}_{>0}$ such that

$$\frac{y^2-x^2}{z^2-y^2}=\frac{a}{b};$$

see [59, p. 101]. Suppose that $a$ and $b$ are relatively prime, $b>a$, and let $v,w\in {\mathbb{Z}}_{\ge 1}$ satisfy

$$bv-aw=1;$$

such $v,w$ can be found using (7). Then let

$$u=avw+a\cdot \frac{w(w+1)}{2}-b\cdot \frac{v(v+1)}{2}.$$

As $v$ and $w$ are relatively prime, it follows from this that $u\in \mathbb{Z}$, and one checks that

$$2u=v(aw-1)+(a{w}^2-1).$$

Hence $u\in {\mathbb{Z}}_{\ge 0}$, and if $a>1$ then $u\in {\mathbb{Z}}_{\ge 2}$. Now,

$(u+1)+\mathrm{\cdots }(u+v)$ $={\displaystyle \frac{uv}{bv-aw}}+{\displaystyle \frac{v(v+1)}{2}}$

$={\displaystyle \frac{avw\cdot v+av\cdot \frac{w(w+1)}{2}-bv\cdot \frac{v(v+1)}{2}}{bv-aw}}+{\displaystyle \frac{v(v+1)}{2}}$

$={\displaystyle \frac{avw\cdot v+av\cdot \frac{w(w+1)}{2}-aw\cdot \frac{v(v+1)}{2}}{bv-aw}}$

$={\displaystyle \frac{avw(v+w)}{2}}$

and

thus

$$\frac{a}{b}=\frac{(u+1)+\mathrm{\cdots }(u+v)}{(u+v+1)+\mathrm{\cdots }+(u+v+w)}.$$

But

$${(2p-1)}^2=1+1\cdot 8+2\cdot 8+\mathrm{\cdots }(p-1)\cdot 8,$$

whence

$8\cdot \left((u+1)+\mathrm{\cdots }(u+v)\right)$ $=\left(1+{\displaystyle \sum _{j=1}^{u+v}}8j\right)-\left(1+{\displaystyle \sum _{j=1}^u}8j\right)$

$={[2\cdot (u+v+1)-1]}^2-{[2\cdot (u+1)-1]}^2$

$={(2u+2v+1)}^2-{(2u+1)}^2$

and

Therefore, taking

$$x=2u+1,y=2u+2v+1,z=2u+2v+2w+1,$$

we have

$$\frac{y^2-x^2}{z^2-y^2}=\frac{a}{b}.$$

For $a=5$ and $b=29$, we do the Euclidean algorithm with $v_0=29$ and $v_1=5$. Then

$$a_0=T(29,5)=5,v_2=29-T(29,5)\cdot 5=4.$$

Then

$$a_1=T(5,4)=1,v_3=5-T(5,4)\cdot 4=1.$$

Then

$$a_2=T(4,1)=4,v_4=4-T(4,1)\cdot 1=0,$$

so $N=3$, $v_N=1$, $v_{N+1}=0$. By (4),

and then

and then

But by (7) it holds that $v_0{q}_{N-2}-v_1{p}_{N-2}={(-1)}^N{v}_N$. Here, $p_{N-2}=p_1=6,q_{N-2}=q_1=1$, thus $29\cdot (-1)-5\cdot (-6)=1$, and thus $29\cdot (-1+5)-5\cdot (-6+29)=1$, i.e.

$$bv-aw=1,v=4,w=23.$$

Then

$$u=5\cdot 4\cdot 23+5\cdot \frac{23\cdot 24}{2}-29\cdot \frac{4\cdot 5}{2}=1550.$$

Then

$$x=2u+1=3101,y=2u+2v+1=3109,z=2u+2v+2w+1=3155.$$

Summarizing,

$$\frac{{3109}^2-{3101}^2}{{3155}^2-{3109}^2}=\frac{5}{29}.$$

15 Chinese mathematics

Suan shu shu, problem 7 [16, pp. 111–112]:

The rule for simplifying fractions says: Take the numerator and subtract it (successively) from the denominator; also take the denominator and subtract it (successively) from the numerator; (when) the amounts of the numerator and denominator are equal, this will simplify it (the fraction will be simplified). Another rule for simplifying fractions says: if it can be halved, halve it; if it can be divided by a certain number, divide by it. Yet another rule says: Using the numerator of the fraction, subtract it (successively) from the denominator; using the remainder as denominator, subtract it (successively) from the numerator; use what is equal to (both) numerator and denominator as the divisor; then it is possible to divide both the numerator and denominator by this number. If it is not possible (lit. if there is not enough) to subtract but it can be halved, halve the denominator and also halve the numerator. $162/2016$, simplified, is $9/112$.

The Nine Chapters on the Mathematical Art, I.6 [44, p. 64]:

If [the denominator and numerator] can be halved, halve them. If not, lay down the denominator and numerator, subtract the smaller number from the greater. Repeat the process to obtain the GCD (dengshu). Reduce them by the GCD.

Liu Hui in his commentary writes, “To reduce a fraction by the GCD means to divide. Subtract the smaller number from the greater repeatedly, because the remainders are nothing but the overlaps of the GCD, therefore divide by the GCD.”

On the Chinese remainder theorem see Libbrecht [43].

16 Conclusions

The Euclidean algorithm belongs to the intersection of Books VII–IX and Books V, VI, X of the Elements. We have mentioned works about the second set. For Books VII–IX we have the following to say.

Euclid, Elements VII.20 [30, p. 320]:

The least numbers of those which have the same ratio with them measure those which have the same ratio the same number of times, the greater the greater and the less the less.

Elements VII.20 is equivalent to the statement that if a number measures a product of two numbers and is relatively prime to one of the two numbers then it measures the other number. Taisbak [63, p. 9, Chapter 1] says about Elements VII.20,

as cited above it sounds trivial, at most somewhat impenetrable. Almost all the arithmetical theorems of the Elements have that stamp of impenetrability to a modern reader, and my experience is that they open only to the patient reader and even then only to one who is prepared to give up his preconceived opinions as to what Euclid’s theory of proportions is all about.

Euclid, Elements VII.30 [30, p. 331]:

If two numbers by multiplying make some number, and any prime number measure the product, it will also measure one of the original numbers.

This theorem is commented on by Pengelley and Richman [52].

It would also be worthwhile to survey the occurence of the Euclidean algorithm in Arabic mathematical works. Saidan [58] summarizes the Arithmetic of Abu al-Wafa. Saidan [58, p. 371] states that in Arithmetic II.3 (pp. 160–173 in Saidan’s edition of the Arabic text), the Euclidean algorithm is used to find common denominators of fractions.

Burnett [6]

Vitrac [71]