Greatest Common Divisor

In this section, we will explain how to find the greatest common divisor of two integers $a$ and $b$, a task that we used to factor $N$ back in The RSA Algorithm. Of course, you could always use “brute force” methods and first find all the divisors of the first integer—looking for integers that divide a with no remainder. Then, do the same for $b$. Then, look at those divisors to find the divisors that are common to both and select from that subset the one that is the greatest. This works fine for relatively small numbers. But it takes a long time for larger numbers.

A more efficient way makes use of what is called Euclid’s algorithm (or the Euclidean algorithm), which was written up more than 2,000 years ago in Euclid’s famous book Elements. Many authors claim that this algorithm is the oldest known algorithm, but there is no historical evidence that Euclid himself invented it. What is important is that he made it readily available to subsequent generations of mathematicians. As we mentioned before, greatest-common-divisor functions are available in most programming languages and spreadsheets.

Here is how the algorithm works:

1. Let $a$ be the larger of the two integers, $a$ and $b$. Then, find the remainder $r_1$ from dividing $a$ by $b$. If the remainder is $0$, then $b$ is the greatest common divisor of $a$ and $b$. If it is not, go to step 2.

2. Divide $b$ by $r_1$ to find the remainder $r_2$. If $r_2$ is not equal to $0$, proceed to step 3.

3. Divide $r_1$ by $r_2$ to find a new remainder $r_3$.

4. Continue these steps until the remainder is $0$. The next-to-last remainder (the one that is non-zero) is the largest common divisor of $a$ and $b$.