I was a little embarrassed that I’ve never came across Euclid’s GCD algorithm until years after I graduated with Math and Engineering degrees. The descriptions I’ve found online (especially Wikipedia) are convoluted and confusing, and the mechanical description of the algorithm does not shine light to any intuition. Then there comes proofs and abstract algebra properties that even after I followed the reasoning, I’d soon forget after I stop looking at it in a few weeks.
Just by staring at one simple description of the algorithm:
The classic algorithm for computing the GCD, known as Euclid’s algorithm, goes as follows: Let
K.N. King’s C++ Programming (Chapter 6 Exercise 2)and
be variables containing the two numbers, divide
, then stop:
I reversed engineered one line of reasoning how one could come up with the Euclid GCD on his own. Turns out there is one twist/angle that most traditional explanations glossed over: quotients do NOT matter and WHY it does NOT matter!
It goes back to what GCD
stands for: greatest common divisor. You are looking for the largest factor that simultaneously divides 
and 
evenly. If you rethink in terms of multiplication, you are finding the biggest tile size 
that can simultaneously cover and without gaps:
Find s.t. 
and 
where 
are integers.
Imagine you are a lazy and cheap contractor who have unlimited tile samples of all sizes to try before making a large order:
- [Goal] you have to cover with two floors with potentially different sizes and gaplessly
- [Constraint: divisible] your customer won’t let you cut (fractional) tiles because it’s ugly
- [Constraint: common denominator] you can only order ONE tile size to take advantage of bulk discounts
- [Objective: greatest] more tiles means more work to lay it, so you want to shop for the biggest tile size that does the job.
For simplicity of the argument, we also assume the divisor is the smaller number. If is the bigger number, the roles will reverse in the next round because the remainder from dividing by a larger number is the dividend itself, which becomes the divisor in the next round while the old divisor (the larger number) becomes the dividend.
For relatively prime pairs, the algorithm will eventually stop with a GCD of 
because divides all integers.
Here’s the analog of Euclid algorithm:
- start out with 1 big tile covering the entire smaller floor
- see if we can cover without gaps using big tiles of size
- if yes, we are done. , the macro-tile is your GCD (perfect-sized tile).
- if there are gaps (non-zero remainder), pick a tile-size that covers the ugly gap (the remainder becomes the divisor), then repeat the same process above over the last tile size (the divisor becomes the dividend) until there are no gaps (remainder become zero).
The algorithm is taking advantage of the fact the remainder is smaller than the last tile size (divisor) so we can rewrite the last tile size in multiples of the remainder (old gap) plus the new gap. By the time the new gap evenly divides the last tile (the big tile right before it), all numbers before that can be written as multiples of the new gap (i.e. the last gap evenly divides all the numbers in the chain all the way up to and ).
Let’s start with a simple case GCD
that terminates early:
![50 (dividend) = [15+15+15 (divisor)] + 5 (remainder)](https://wonghoi.humgar.com/blog/wp-content/ql-cache/quicklatex.com-e1912abceca1670919e9aa937af0124e_l3.png "Rendered by QuickLaTeX.com")
We focus on the last tile 
and write it in terms of the old remainder 
:
Since the new remainder is , the old remainder divides the last tile . Since we are dividing in terms of the remainder , we have
\begin{aligned}
b &= 15 \\
&= (5+5+5) \\
&= 3r \\
\\
a &= 50 \\
& = (15 + 15 + 15) + 5\\
& = 3b + r\\
&= (5+5+5) + (5+5+5) + (5+5+5) + 5\\
&= 3(3r)+r \\
& = 10r
\end{aligned}So both and can be written in terms of integer multiples of 
right before the algorithm stops.
GCD
takes a few more steps:
\begin{aligned}
b &= 18\\
a &= 50\\
&= (18 + 18) + 14\\
&=2b + r\\
r &= 14 \\
\\
b_1 &= r = 14\\
a_1 &= b = 18\\
&= (14) + 4\\
&= b_1 + r_1\\
r_1 &= 4\\
\\
b_2 &=r_1 = 4\\
a_2 &= b_1 = 14\\
&= (4+4+4)+2\\
&= 3b_2 + r_2\\
r_2 &= 2\\
\\
b_3 &= r_2 = 2\\
a_3 &= b_2 = 4\\
&=(2+2) + 0\\
r_3 &= 0\\
\end{aligned}The algorithms stops at 
which means we successfully divided the last tile 
with 
(logistically stored in 
) with no gaps left. (or is therefore the greatest common factor (divisor) that are shared by all the numbers involved all the way up to and .
This is the beauty of Euclid’s GCD algorithm: once the gap (remainder) is sliced small enough to evenly divide the tile (divisor) right before it, every term before it be can written in terms of integer multiples of the last number that divides the last tile without gap (no more remainder).
In our example, 
can be written as a multiple of 
, aka because integer multiples of numbers that are already integer multiples of can be written in terms of a larger integer multiple of . This is why quotients do not matter in the Euclid GCD algorithm:
\begin{aligned}
b_2 &= 2r_2\\
4 &= (2+2) \\
\\
b_1 &= 3b_2 + r_2\\
&= 3(2r_2) + r_2\\
& = 7r_2\\
14 &= [(4+4+4)+2] \\
&= [(2+2)+(2+2)+(2+2)+2] \\
\\
b &= b_1 + r_1\\
&=7r_2 + 2r_2\\
&=9r_2\\
18 &= 14 + 4 \\
&= [(4+4+4)+2] + 4 \\
&= [(2+2)+(2+2)+(2+2)+2]+[(2+2)] \\
\\
a &= 2b + r\\
&=2(9r_2) + 7r_2\\
&= 25r_2\\
50 & = 18 + 18 + 14 \\
&= [(2+2)+(2+2)+(2+2)+2]+[(2+2)] \cdots \\
&+ [(2+2)+(2+2)+(2+2)+2]+[(2+2)] \cdots \\
&+ [(2+2)+(2+2)+(2+2)+2]
\end {aligned}The spirit of the algorithm is that every time we see a gap, we fill it with a small tile that’s exactly the gap size, and attempt to replace the last tile by covering it in terms of the new smaller tile (that was used to fill the gap). We are recursively slicing the last tile with the gaps produced until there are no gaps left. Once you find the GCD tile, you can replace all the bigger tiles before in terms of it with no gaps.
There’s an interesting perspective of using the Euclid GCD algorithm to solve Diophantine Equations (integer written as a linear combination of integers with integer coefficients): turns if 
in 
is the same as writing 
. We can flip the sign of 
by saying substituting 
.
In summary,
Euclid GCD’s algorithm is sub-dividing the last (or any one) large tile (last divisor) with the gap (last remainder) until there are no gaps left. Then any bigger tiles up the chain can be expressed as an integer multiple of the last piece (the smallest piece searched so far) that fills the last gap.
The first large tile is of course the smaller of the two numbers involved in the gcd calculation. The larger of the two number is the floor to be covered.
The other observation is that when you see the remainder being 1, you already know the two numbers are relatively prime. The last step to get the remainder to 0 is redundant (because it’s a guaranteed last step).
The other observation is that subdividing the last big tile (divisor) with the last gap (remainder) till it’s evenly divided chains up, because everything is an integer multiple of the smallest piece that evenly divides the gap (remainder) and the last big tile (divisor), therefore the algorithm is recursive.
\gcd(r_1,r_2) = \gcd(r_2, r_3) = ... = \gcd(r_{n-1}, r_n)But this kind of recursion is not mandatory. It’s a tail recursion* that can be unrolled into iterations (looping), either by the compiler or the programmer, which is what we initially did.
