Euclid's algorithm

Many people, hearing the word "algorithm", think about something relatively novel and non-existent before the modern computer era. But one of the most widely used algorithms in today's world (crucial, for example, in cryptographic applications) is, in fact, two thousand years old. A famous computer scientist Donald Knuth called it "the granddaddy of all algorithms". This algorithm was described by an ancient Greek mathematician Euclid and finds the greatest common divisor of two integers. Let's see how it works!

Division with remainder

Firstly, let's recall the procedure known as a division with remainder. Suppose we have two integers $a$ and $b$, such that $b \neq 0$. Marking all multiples of $b$ on a number line, we see that $a$ either coincides with one of them or lies between two marks. If $bq$ is the closest mark to the left from $a$ (possibly coinciding with $a$ itself), the "distance" $r$ from $bq$ to $a$ is strictly less than $b$.

Keeping in mind this picture, we may state the following:

For any integer $a$ and any non-zero integer $b$, there exist uniquely determined integers $q$ and $r$, such that

$$a = bq + r, \quad 0 \leq r < q$$We will say that $a$ divided by $b$ has quotient $q$ and remainder $r$. We will also denote $r$ as $a \bmod b$. Notice that $q = \lfloor a / b\rfloor$, meaning "the greatest integer that is less or equal to $a / b$ " (where $a / b$ is a floating-point result of ordinary division).

For example, $239 = 10 \cdot 23 + 9$, so $239$ divided by $10$ has a remainder $9$ (and we can write that $239 \bmod 10 = 9$).

Euclid's algorithm

Suppose now we want to find the greatest common divisor of two integers $a$ and $b$. Somebody can think the most obvious approach to compute $\gcd(a, b)$ is to firstly represent $a$ and $b$ as products of primes, and then multiply together their common factors. For instance, $15660 = 2^{2} \cdot 3^{3} \cdot 5 \cdot 29$ and $3393 = 3^{2} \cdot 13 \cdot 29$, so their greatest common divisor is $3^{2} \cdot 29 = 261$.

However, despite centuries of effort, nobody has invented an efficient algorithm for factoring. Is there some other way to compute the greatest common divisors? Fortunately, yes. The key fact is that

If $a$ and$b$ are positive integers, and $a \geq b$, then $\gcd(a, b) = \gcd(b, a \bmod b)$

Why is it true? Well, if $a = bq + r$, then $a \bmod b = r = a - qb$, so necessarily any integer that divides both $a$ and $b$ must divide $a \bmod b$. On the other hand, any integer that divides both $a \bmod b$ and $b$ must also divide $a$. So, as the sets of all common divisors coincide, the greatest common divisors also coincide.

Hence we can easily write a recursive algorithm, always coming down to smaller arguments until one of them is zero (and you can easily prove that $\gcd(a, 0) = a$ for any positive integer $a$). Applying it to $a = 210$ and $b = 196$, for example, we obtain

$$\gcd(210, 196) = \gcd(210 \bmod 196, 196) = \gcd(14, 196) = \gcd(14, 196 \bmod 14) = \gcd(14, 0) = 14$$Is it really an efficient algorithm? For the answer, we need to understand how quickly the arguments $a$ and $b$ decrease with each recursive call. In a single round, the pair of arguments $(a, b)$ becomes $(b, a \bmod b)$. Either $b > a/2$ and then $$a \bmod b = a - b < a - a/2 = a/2$$Otherwise, $b \leq a/2$ and then, as $a \bmod b < b$, it follows that $$a \bmod b < b \leq a /2$$In the next round, $(b, a \bmod b)$ will become $(a \bmod b, b \bmod (a \bmod b))$. Here, we always write the greatest of two arguments in the first place. So, after any two consecutive rounds of the algorithm, the greatest of two arguments is at the very least halved in value. That means we will reach zero in at most $2 \log_{2} a$ divisions, which is quite fast — for a 24-digit $a$ (in our ordinary decimal system), there will be less than 170 divisions.

Extended Euclid's algorithm

Tweaking Euclid's algorithm a bit allows us to express $\gcd(a, b)$ as an integer linear combination of $a$ and $b$, that is, in the form

$$\gcd(a, b) = ax + by$$where $x$ and $y$ are some integers. Such a representation is always possible and will help us to do division in modular arithmetic (an operation making possible, for example, the key generation in the famous RSA cryptosystem).

Before giving the general algorithm, we illustrate it with an example. We will compute $\gcd(2024, 748)$: $$2024 = 748 \cdot 2 + 528\\ 748 = 528 \cdot 1 + 220\\ 528 = 220 \cdot 2 + 88\\ 220 = 88 \cdot 2 + 44\\ 88 = 44 \cdot 2 + 0$$We can look at the second line from below and write:$$44 = 220 - 88 \cdot 2$$Then, looking one line up, we notice we can substitute $88$ with an expression $528 - 220 \cdot 2$, so:$$44 = 220 - (528 - 220 \cdot 2) \cdot 2 = 220 \cdot 5 - 528 \cdot 2$$Next, we substitute $220$ with $748 - 528$, hence: $$44 = (748 - 528) \cdot 5 - 528 \cdot 2 = 748 \cdot 5 - 528 \cdot 7$$See the pattern? In the end (check it!) we obtain:$$44 = 2024 \cdot (-7) + 748 \cdot 19$$Proceeding in the same way, we can always express $d = \gcd(a, b)$ in the form $d = ax + by$, where $x$ and $y$ are integers — in other words, as a linear combination of $a$ and $b$. This process can be implemented as a recursive algorithm. Suppose we know the coefficients $x'$ and $y'$ in the representation of $d$ as $d = bx' + (a \bmod b)y'$? Now we can obtain the coefficients $x$ and $y$ in the representation $d = ax + by$. Since $a \bmod b = a - bq$ with $q = \lfloor a / b \rfloor$,

$$d = bx' + (a \bmod b)y' = bx' + (a - bq)y' = ay' + b(x' - qy')$$So, $x = y'$ and $y = x ' - \lfloor a / b \rfloor y'$. The base case for this recursion is again $b = 0$, when $d = a = a \cdot 1 + b \cdot 0$.

Working with non-positive integers

In the previous paragraphs, we discussed finding $\gcd$ only when one integer is strictly positive and another is at least non-negative (the case when it is zero was considered as the base of the recursion). How can we handle negative numbers? Firstly, we notice that flipping the sign of any argument doesn't change the greatest common divisor, so we can always reduce the problem to finding $\gcd$ of two non-negative integers. And then the only case not mentioned before is $\gcd(0, 0)$. Well, there exists a somewhat counterintuitive convention that $\gcd(0, 0) = 0$. Now we can use Euclid's algorithm to find $\gcd$ of any two integers.

Conclusion

In this module, we have explored one of the most important algorithms called Euclid's algorithm. Here are the main take-aways:

• Euclid's algorithm is an effective algorithm for finding the greatest common divisor of two integers.
• It can be written in a recursive way and consists in replacing the greatest of two positive arguments with its remainder modulo another argument
• An extended version of Euclid's algorithm allows us to represent $\gcd$ of two integers as their linear combination.