# Euclid’s Algorithm

Euclid’s algorithm is a classic procedure beloved by computer scientists as an elegant example of recursion. While implementing the algorithm is relatively straightforward, understanding why it works it substantially trickier.

The algorithm computes the greatest common divisor (GCD) substantially faster than the naïve approach of factoring both numbers and selecting the largest factor common to both. Factorization is a notoriously slow process and Euclid’s algorithm seems magical in its efficiency.

Algorithm. For $a,b\in \mathbb{Z}$ such that $a<b$.

$gcd(a,b)=\{\begin{array}{cc}b& \text{if a = 0}\\ gcd(bmoda,a)& \text{otherwise}\end{array}$

Proposition. Euclid’s algorithm is correct.

Proof. The strategy Euclid employs here will be familiar if you know recursion. We begin with a problem and reduce it to smaller equivalent problems. We stop at some base case with a trivial solution.

The reduction step occurs in Euclid’s assertion that $gcd(a,b)=gcd(bmoda,a)$. By the Quotient-Remainder Theorem, we know that $bmoda$ is between 0 and $a-1$. Therefore $a$ is the new largest argument in our $gcd$ function. If we repeat this reduction, eventually we will achieve an equivalent form with a $0$ argument which is our base case.

We have to show $gcd(0,b)=b$ (base case) and that $gcd(a,b)=gcd(bmoda,a)$ (reductive step).

The base case is pretty easy. Since every integer divides $0$, the $gcd(0,b)$ is the greatest divisor of $b$ which is simply $b$.

The truth of the reductive step is difficult to see intuitively. To prove $gcd(a,b)=gcd(bmoda,a)$ it is sufficient to show that the set of all common divisors between $a$ and $b$ is the same as that of $bmoda$ and $a$. This would mean their greatest elements (GCDs) are the same.

To show this set equality one must prove:

- Any common divisor of $a$ and $b$ divides $bmoda$.
- Any common divisor of $bmoda$ and $a$ divides $b$.

The following graphic provides some intuition.

- Let $x$ be a common divisor of $a$ and $b$. Consider all of the copies of $x$ which add up to $b$. Take away all the instances of $x$ that evenly cover $a$. What’s left must evenly divide $bmoda$.
- Alternatively, if we consider $x$ to be a common divisor of $bmoda$ and $a$ we can copy it to cover $bmoda$ evenly and $a$ as many times as necessary to add up to $b$. Therefore it evenly divides $b$.

If the visual demonstration is unconvincing, the above can also be shown algebraically using the definition of divisibility.

Let $d$ be the common divisor of $a$ and $b$. We can write $a$ and $b$ as $a=dp$, $b=dq$ for $p,q\in \mathbb{Z}$. By the Quotient-Remainder Theorem, we can also write $b=an+(bmoda)$ for $n\in \mathbb{Z},0\le n<a$. We must show $d$ divides $bmoda$.

- $(bmoda)$
- $=b-an$
- $=\left(dq\right)-\left(dp\right)n$
- $=d(q-pn)$

We must also show that if $d$ is the common divisor of $bmoda$ and $a$, then it divides $b$. Let $(bmoda)=dp$, $a=dq$. Once again we know $b=an+(bmoda)$.

- $b$
- $=dqn+dp$
- $=d(qn+p)$ □