Euclid’s Algorithm Explained

Finding the greatest common divisor (GCD) of two numbers is an operation that most high school math students end up performing. However, most probably don’t learn a fancy algorithm to do it. Euclid’s Algorithm is just this algorithm. Well, maybe it is not fancy, but it is elegant (at least to me).

First things first, this algorithm hinges on one key fact that I will prove to you. If two numbers have a GCD, then the difference of these two numbers has a factor of that GCD. Further, of these three numbers, they all share that same GCD as the first two.

Proof: If two numbers have a GCD, then their difference has a factor of that GCD.

\(GCD(A,B)=d\)

\(\text{Note that A, B, and d are all integers}\)

\(\text{Assume that A>B}\)

\(\text{So integers a and b exist such that}\)

\(A=a\cdot d\)

\(B=b\cdot d \)

\(\text{Let C be as follow}\)

\(C=A-B\)

\(C=a \cdot d-b \cdot d\)

\(C=(a-b) \cdot d\)

\(\text{This shows that the difference of two numbers has a factor of the GCD of those two numbers.}\)

Proof: The GCD of two numbers is the same GCD of those two numbers and the difference of those two numbers

\(\text{Using the previously defined A, B, a, b, and d (all integers)}\)

\(\text{For d to be the GCD(A,B), it must be that the GCD(a,b) must be 1 (aka they have no common factors other than 1)}\)

\(\text{If GCD(a,b) is 1 then GCD(a,b,a-b) must also be 1, since a and b have no common factors to factor out of a-b}\)

\(\text{Thus GCD(A,B,(A-B))=d}\)

Simple form of Euclid’s Algorithm

To find the GCD of two numbers do the following.

1. Take two integers you want to find the GCD of
2. Subtract the two numbers in such a way to get a positive third number
3. Note the two smallest numbers of the three numbers. If they are the same number, you have found the GCD. Otherwise, continue to the next step.
4. take your two lowest numbers and go back to step 2

Note that from the work we did above, we know that every single number produced in this algorithm will have the same GCD as the original two numbers. Because we are subtracting in such a way to yield a smaller positive number, eventually we will get to a subtraction that will yield that very GCD.

Let’s go over a “quick” example. After this example, we will go over a quicker form of the algorithm. We are going to find the GCD of 1488 and 1176.

\(GCD(1488,1176)=?\)

\[
\begin{array}{cr}
&1488\\
-&1176\\
\hline
&312\\
\end{array}
\begin{array}{cr}
&1176\\
-&312\\
\hline
&864\\
\end{array}
\begin{array}{cr}
&864\\
-&312\\
\hline
&552\\
\end{array}
\begin{array}{cr}
&552\\
-&312\\
\hline
&240\\
\end{array}
\begin{array}{cr}
&312\\
-&240\\
\hline
&72\\
\end{array}
\begin{array}{cr}
&240\\
-&72\\
\hline
&168\\
\end{array}
\begin{array}{cr}
&168\\
-&72\\
\hline
&96\\
\end{array}
\begin{array}{cr}
&96\\
-&72\\
\hline
&24\\
\end{array}
\begin{array}{cr}
&72\\
-&24\\
\hline
&48\\
\end{array}
\begin{array}{cr}
&48\\
-&24\\
\hline
&24\\
\end{array}
\begin{array}{cr}
&24\\
-&24\\
\hline
&0\\
\end{array}
\]

\(GCD(1488,1176)=24\)

\(1488=24 \cdot 62\)

\(1176=24 \cdot 49\)

Better form of Euclid’s Algorithm

Ok, let’s make a slight but massive improvement to this algorithm. Hopefully, you noticed that we were subtracting the same number multiple times (312, 72, 24), we will take advantage of this.

1. Take two integers you want to find the GCD of
2. Subtract from the larger number the maximum times of the smaller number while still leaving a third positive result.
3. Note the two smallest numbers of the three numbers. The larger one will be the result of the previous step and the smaller will be the result you just got.
4. If the result you just got is 0, then the smaller of the two numbers is the GCD, otherwise go back to step 2

Let’s do that example again. I will give some commentary as we go.

\(GCD(1488,1176)=?\)

For the first subtraction, we can only subtract once.

\(1488-1 \cdot 1176=1488-1176=312\)

We now have 1176 and 312, and we can subtract 312 three times.

\(1176-3 \cdot 312=1176-936=240\)

We now have 312 and 240, we can only subtract once.

\(312-1 \cdot 240=312-240=72\)

We now have 240 and 72, we can subtract 72 three times.

\(240-3 \cdot 72=240-216=24\)

Finally, we have 72 and 24, we can subtract 24 exactly 3 times.

\(72-3 \cdot 24=72-72=0\)

\(GCD(1488,1176)=24\)

A more formal form of Euclid’s Algorithm

This is more like the version that you would find in a math textbook. It will boil down to finding remainders and quotients.

\(GCD(A,B)=d\)

\(A>B\)

\(Let\)

\(r_0=A\)

\(r_1=B\)

\(Then\)

\(r_0=q_2 \cdot r_1+r_2\)
\(r_1=q_3 \cdot r_2+r_3\)
\(r_2=q_4 \cdot r_3+r_4\)
\(\vdots\)
\(r_n=q_{n+2} \cdot d+0\)

\(\text{Continue until you get a remainder of 0, the remainder before this is the GCD}\)

I will go over our example in this more “formal” way, but it is essentially exactly like the last.

\(GCD(1488,1176)=?\)

\(1488=1 \cdot 1176+312\)

\(1176=3 \cdot 312+240\)

\(312=1 \cdot 240+72\)

\(240=3 \cdot 72+24\)

\(72=3 \cdot 24+0\)

\(GCD(1488,1176)=24\)

Have fun finding GCDs.