The Ancient Algorithms Secretly Running the World

Donald Knuth

[The Euclidean algorithm is] the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day.

— The Art of Computer Programming, Vol. 2

We are back at another historical journey of mathematics, with this installment being one of the oldest algorithms we still use today. That’s right: the Euclidean Algorithm, and all of the small discoveries that led to it.

The semi-forgotten history of Reciprocal Subtraction

Suppose you were in the shoes of a Greek mathematician, and you were tasked with finding the circumference of a circle that has the radius of 1 unit. You can empirically measure it and obtain a rough decimal approximation, but what if you wanted to find a close fractional form? We know that the circumference of a circle is: $C=2\cdot \pi \cdot 1\approx 6.283185$. But how can we construct a fraction close to it? Let’s focus in on the decimal part, so we can subtract $6$, so we can reduce the problem to: “What is the closest fraction we can get for $0.283185$“.

The process I will call ‘reciprocal subtraction’ has a long history in mathematics and is closely connected to rational approximation. Variations of the process appear in Euclid’s Elements, but Euclid did not provide a numerical worked example in the modern sense.

Reciprocal Subtraction

Let $n$ be the number you want to approximate. I will denote the ceiling function as $\lceil x\rceil$. Let $a_0=\lceil n\rceil -n$. Define the remaining $a_n$‘s in the following way:

$$\begin{array}{rl}{a}_0& =\lceil n\rceil -n\\ a_1& =\lceil \frac{1}{a_0}\rceil -\frac{1}{a_0}\\ a_2& =\lceil \frac{1}{a_1}\rceil -\frac{1}{a_1}\\ & ⋮\\ a_n& =\lceil \frac{1}{a_{n-1}}\rceil -\frac{1}{a_{n-1}}\end{array}$$

Now we can build our continued fraction as: $\lceil n\rceil -\frac{1}{\lceil \frac{1}{a_0}\rceil -\frac{1}{\lceil \frac{1}{a_1}\rceil -\ddots }}$

Example

$$\begin{array}{rlrl}1-0.283185& =0.716815,& \frac{1}{0.716815}& =1.395060\\ 2-1.395060& =0.604940,& \frac{1}{0.604940}& =1.653056\\ 2-1.653056& =0.346944,& \frac{1}{0.346944}& =2.882309\\ 3-2.882309& =0.117691,& \frac{1}{0.117691}& =8.496826\\ 9-8.496826& =0.503174,& \frac{1}{0.503174}& =1.987384\end{array}$$ $$\begin{array}{rl}1=\frac{1}{1}& =1.0\\ 1-\frac{1}{2}=\frac{1}{2}& =0.5\\ 1-\frac{1}{2-\frac{1}{2}}=\frac{1}{3}& =0.\bar{3}\\ 1-\frac{1}{2-\frac{1}{2-\frac{1}{3}}}=\frac{2}{7}& =0.285714\dots \\ 1-\frac{1}{2-\frac{1}{2-\frac{1}{3-\frac{1}{9}}}}=\frac{16}{70}& =0.28\bar{3}\\ 1-\frac{1}{2-\frac{1}{2-\frac{1}{3-\frac{1}{9-\frac{1}{2}}}}}=\frac{32}{113}& =0.283185\dots \\ & ⋮\\ 2\pi -6& =0.283185840708\end{array}$$

Awesome Coincidence

• If we were to do the following: $\frac{6+32/113}{2}=\frac{355}{113}$ We can stumble upon a pretty famous approximation for $\pi$ that dates back to the fifth century by mathematician Zu Chongzhi. Unfortunately, his exact method of how he obtained that approximation has been lost to history, but many historians suggest that continued fractions could have been how he did it!

Question

• Couldn’t you come up with a rational by adding up all the parts of the decimal?

$$\frac{2}{10}+\frac{8}{100}+\frac{3}{1000}+\frac{1}{10000}+\frac{8}{100000}+\frac{5}{1000000}=\frac{56637}{200000}$$

Yes, but...

• I don’t know about you, but $\frac{32}{113}$ is a much nicer fraction than $\frac{56637}{200000}$. Using it for various calculations would be considerably much easier, even if it’s an over-approximation, it still agrees with $2\pi -6$ to ten decimal places

Here is my favorite computation I've discovered!

$$\begin{array}{rlrl}4-3.14& =0.86,& \frac{1}{0.86}& \approx 1.16\\ 2-1.16& =0.84,& \frac{1}{0.84}& \approx 1.19\\ 2-1.19& =0.81,& \frac{1}{0.81}& \approx 1.23\\ 2-1.23& =0.77,& \frac{1}{0.77}& \approx 1.30\\ 2-1.30& =0.70,& \frac{1}{0.70}& \approx 1.43\\ 2-1.43& =0.57,& \frac{1}{0.57}& \approx 1.75\\ 2-1.75& =0.25,& \frac{1}{0.25}& =4\end{array}$$ $$4-\frac{1}{2-\frac{1}{2-\frac{1}{2-\frac{1}{2-\frac{1}{2-\frac{1}{2}}}}}}=\frac{22}{7}$$

Using this process, we obtain a finite continued fraction representation for $22/7$, one of the most famous approximations for pi!

The Division Algorithm

Before we talk about the Euclidean Algorithm, it would be helpful to jump a bit into the future to gain some familiarity of Euclid’s Concepts with our more modern way of viewing division.

The Division Algorithm

• Given integers $a$ and $b$, with $b>0$, there exists unique integers $q$ and $r$ satisfying $a=qb+r,0\le r<b$
• where $q$ is usually denoted as the quotient and $r$ is the remainder in the division of $a$ and $b$

Proof

• In order to prove the division algorithm for the integers, we will need to prove the existence and uniqueness of such solutions

Existence

• We will prove by induction on a

$$\begin{array}{rl}a=1,b=1,1& =(1)(1)+0\\ a=2,b=1,2& =(2)(1)+0\\ a=2,b=2,2& =(1)(2)+0\\ a=3,b=1,3& =(3)(1)+0\\ a=3,b=2,3& =(1)(2)+1\\ a=3,b=3,3& =(1)(3)+0\end{array}$$

Induction Step

Suppose that given a fixed positive integer $a$, then for every integer $b$ with $a\ge b>0$ there exists a $q,r\in \mathbb{Z}$ with $a=qb+r,0\le r<b$ Lets consider $a+1\in \mathbb{Z}$, then $a+1=qb+r+1$

Case 1:

If $r+1<b$, then we are done as we can see that $a+1=qb+\stackrel{r^{\prime }}{\overbrace{r+1}}=qb+r^{\prime }$

Case 2:

If $r+1=b$, then $a+1=qb+r+1=qb+b=\stackrel{q^{\prime }}{\overbrace{(q+1)}}b+0=q^{\prime }b+0$

• Hence, we are able to construct $a+1=q^{\prime }b+r^{\prime }$, where $q^{\prime }\in \mathbb{Z}$ and $0\le r^{\prime }<b$

Uniqueness

Suppose that

$$\begin{array}{rl}a& =q_{1}b+r_1\\ a& =q_{2}b+r_2\end{array}$$

Without Loss of generality, assume that $r_2>r_1$, then $r_2-r_1>0$ and $(q_1-q_2)b=r_2-r_1>0$. Since $0\le r_1<b$ and $0\le r_2<b$, then

$$\begin{array}{rl}& 0\le r_2-r_1<b-r_1<b\\ & 0\le (q_1-q_2)b<b\end{array}$$

However, since $q_1-q_2$ is a positive integer, lets call it $k$, however, we run into a problem as there are no positive integers that satisfies the inequality $0\le kb<b$. Leaving us at a contradiction. Therefore, $q_1-q_2=0$ or $q_1=q_2$, therefore $r_1=r_2$

Euclid’s Elements

Unsurprisingly, many elements of the Euclidean Algorithm can be traced back to Euclid’s Elements. The main book we will focus on is Book 7 as Euclid has laid out the foundation to many elements of the Euclidean Algorithm that we currently use.

Good Old Euclid

Book 7, Prop 1

When two unequal numbers are set out, and the less is continually subtracted in turn from the greater, if the number which is left never measures the one before it until a unit is left, then the original numbers are relatively prime.

Modern Interpretation

For positive integers $a>b$, apply the division algorithm in the following way:

$$\begin{array}{rl}a& =q_{0}b+r_0\\ b& =q_1{r}_0+r_1\\ r_0& =q_2{r}_1+r_2\\ & ⋮\\ r_{n-2}& =q_n{r}_{n-1}+r_n\\ r_{n-1}& =q_{n+1}{r}_n\end{array}$$

and $r_n=1$, then $gcd(a,b)=1$

Book 7, Prop 2

Book 7 lays the actual procedure using an example, it is quite long and tedious, so instead I’ll provide a worded example! You can read a translation here if you are really interested!

$gcd(252,105)$

$$\begin{array}{rl}252& =(2)105+42\\ 105& =(2)42+21\\ 42& =(2)21+0\end{array}$$

So $gcd(252,105)=21$. But if you were to slightly adjust the way the operations are done, it will look familiar!

$$\begin{array}{rl}252-(2)105& =42\\ 105-(2)42& =21\\ 42-(2)21& =0\end{array}$$

It looks just like reciprocal subtraction! But maybe this realization will blow your mind. We can distill the problem to just: $gcd(252,105)=gcd(42,105)=gcd(42,21)=21$

What initially appeared as three different abstract mathematical concepts can all be related by underlying process! Isn’t that awesome!

Why does the Euclidean Algorithm give us the greatest common divisor?

Before we tackle the question, let us generalize the Euclidean Algorithm using notion we are familiar with:

Modern Interpretation

For positive integers $a>b$, apply the division algorithm in the following way:

$$\begin{array}{rl}a& =q_{0}b+r_0\\ b& =q_1{r}_0+r_1\\ r_0& =q_2{r}_1+r_2\\ & ⋮\\ r_{n-2}& =q_n{r}_{n-1}+r_n\\ r_{n-1}& =q_{n+1}{r}_n\end{array}$$

Producing a strictly decreasing sequence of positive integers $b>r_0>r_1>\cdots >r_n>0$,where the algorithm terminates with $r_n$ as the last non-zero remainder and $gcd(a,b)=r_n$

Useful Divisibility Properties that will be useful for our proofs

Let $a,b,d\in \mathbb{Z}$

$$\begin{array}{rl}& a)d\mid a⟹d\mid ab\\ & b)d\mid a,d\mid b⟹d\mid a+b\\ & c)d\mid a,d\mid b⟹d\mid a-b\end{array}$$

Proof

$$\begin{array}{rl}& \text{a)}\\ & d\mid a⟹a=dk\\ & ⟹ab=d(kb)\\ & ⟹d\mid ab\\ & \text{b)}\\ & d\mid a,d\mid b⟹a=dk,b=d\ell \\ & ⟹a+b=d(k+\ell )\\ & ⟹d\mid a+b\\ & \text{c)}\\ & \text{We combine both part a and b!}\\ & d\mid b\stackrel{(a)}{⟹}d\mid (-1)b=d\mid (-b)\\ & d\mid a,d\mid -b\underset{(b)}{⟹}d\mid a+(-b)=d\mid a-b\end{array}$$

The Euclidean Algorithm terminates after at most b steps

Proof

• At every step of the Euclidean Algorithm, the remainders are positive integers strictly smaller than the preceding remainder: $b>r_0>r_1>\cdots >r_n>0$ Since there are only $(b-1)$ positive integers smaller than $(b)$, there can be at most $(b-1)$ nonzero remainders. Therefore, after finitely many steps, the next remainder must be 0, and the algorithm terminates.

The Euclidean Algorithm generates a number that divides both $a$ and $b$

Proof

$$\begin{array}{rlrl}{r}_{n-1}=q_{n+1}{r}_n& ⟹r_n|r_{n-1},& & r_n\mid q_n{r}_{n-1}\\ r_{n-2}=q_n{r}_{n-1}+r_n& ⟹r_n\mid r_{n-2},& & r_n\mid q_{n-1}{r}_{n-2}\\ ⋮& & & \\ b=q_1{r}_0+r_1& ⟹r_n\mid b,& & r_n\mid q_{0}b\\ a=q_{0}b+r_0& ⟹r_n\mid a& & \end{array}$$

Giving us $r_n\mid b$ and $r_n\mid a$

The Euclidean Algorithm generates the greatest common divisor

Proof

• Suppose $d=gcd(a,b)$, hence $d\mid a$ and $d\mid b$ and $d\mid q_{0}b$

$$\begin{array}{rlrlrlr}& d\mid a-q_{0}b& & ⟹d\mid r_0& & & d\mid q_1{r}_0\\ & d\mid b-q_1{r}_0& & ⟹d\mid r_1& & & d\mid q_2{r}_1\\ & d\mid r_0-q_2{r}_1& & ⟹d\mid r_2& & & d\mid q_3{r}_2\\ & & ⋮& & & & \\ & d\mid r_{n-2}-q_n{r}_{n-1}& & ⟹d\mid r_n& & & \end{array}$$

• Clean Conclusion: Since $d\mid r_n$ and is positive, $d\le r_n$. However since $r_n$ divides both $a$ and $b$ and $d$ is their greatest common divisor, $r_n\le d$, thus $d=r_n$, or $r_n$ is our greatest common divisor!

One Final observation and recap

The final proof lays out quite a very important corollary in number theory!

Book 7, Prop 2 Corollary

If a number measures two numbers, then it also measures their greatest common measure.

Modern Interpretation

• If $d\mid a$ and $d\mid b$, then $d\mid gcd(a,b)$

Proof

• This proof follows the exact same procedure as the last proof. You will end off with $d\mid r_n$!

And with that, you now know how to find the greatest common divisors of any two integers and, along the way, a process to find rational approximations of irrational numbers. Now go on with your day and tackle even more math questions!

Resources

• Euclid’s Elements Online Version
• Rational Approximation
• Antenaresis?
• How did archemedes get $\pi$ = 22/7?
• https://maths-from-the-past.org/the-story-of-pi-and-zu-chongzhi/
• www.desmos.com
• Continued Fractions workshop