Basic Euclidean Algorithm

Suppose that you have two distinct positive integers $a$ and $b$ with $a\gt b$, and you would like to find their greatest common factor; that is, the largest positive integer $n$ such that $n \mid a$ and $n \mid b$.

You could solve this problem in a relatively straightforward manner by computing the prime factorization of each number, and by taking the minimum exponent of each prime number.

However, this system is problematic.

Finding prime factorizations of large numbers can be difficult and time-consuming, due to the large amount of trial and error.

For example, supposed you wanted to write a "greatest common factor" algorithm on your computer using some programming language. The problem with using factorization is that the code becomes a lot longer, fixing errors becomes a lot more difficult, and the program becomes slower (although this is hard to notice because computers are amazingly fast).

We would like to search for a method for finding the greatest common factor that has less trial and error and is faster.

The expression $\gcd(a,b)$ is quite unwieldy due to the large numbers. Is there a way we can relate this quantity to some smaller numbers? Take a moment to think about this before moving ahead.

The answer comes from an extremely simple divisibility rule, one that is so obvious that we hardly stop to think about it:

If $n \mid a$ and $n \mid b$, then $n \mid (a+b)$ and $n \mid (a-b)$.

Thus, if $n$ is the greatest common factor of $a$ and $b$, then $n \mid a$ and $n \mid b$, which means that $n \mid (a-b)$!

So we know that $n$ divides both $b$ and $a-b$. Notice that $a-b<a$ and $b\ge b$. Thus, we are clearly well on our way to achieving smaller numbers.

But we have only shown that $\gcd(a-b,b)\ge n$! We have not shown equality!

Fortunately, this is also fairly easy to prove, due to another powerful divisibility rule:

If $n$ divides either $a$ or $b$ but not both, then $n$ does not divide $a+b$.

From this, it easily follows that $\gcd(a-b,b)= n$. Thus, we have $\gcd(a-b,b)=\gcd(a,b)$.

But $a-b$ will typically still be a fairly large number!

We can continue decreasing the numbers as many times as we want, until we hit a limit.

This will occur when we finally get two of the same number, and repeating the process gives us $0$. In this case, the number immediately before $0$ is the greatest common factor.

Alternatively, you can always repeat the process until you feel comfortable enough with the remaining numbers.

In addition, if one number is much larger than another, one may have to subtract a lot of times. Think about how this process may be expedited before moving forward.

We can replace the repeated subtractions with a division, followed by taking the remainder!

With all of this in mind, we can make a precise algorithmic process describing the Euclidean algorithm:

1. Label the larger number $a$ and the smaller number $b$.

2. Divide $a$ by $b$ and let the remainder be $R$.

3. Replace $a$ with $b$, and replace $b$ with $R$.

4. Repeat steps 2-3 until $b=0$.

5. The final number $a$ is the greatest common factor of the two original numbers.