The classic algorithm for computing the GCD, known as Euclid’s algorithm, goes as follows: Let 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<\/strong> it does NOT matter!<\/p>\n\n\n\n <\/p>\n\n\n\n It goes back to what GCD Find Imagine you are a lazy<\/strong> and cheap<\/strong> contractor who have unlimited tile samples of all sizes to try before making a large order:<\/p>\n\n\n\n For simplicity of the argument, we also assume the divisor For relatively prime pairs, the algorithm will eventually stop with a GCD of Here’s the analog of Euclid algorithm:<\/p>\n\n\n\n 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<\/strong><\/span> (i.e. the last gap evenly divides all the numbers in the chain all the way up to Let’s start with a simple case GCD We focus on the last tile Since the new remainder is So both GCD The algorithms stops at 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).<\/p>\n\n\n\n In our example, 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.<\/p>\n\n\n\n There’s an interesting perspective of using the Euclid GCD algorithm to solve Diophantine Equations<\/a> (integer written as a linear combination of integers with integer coefficients): turns if In summary, <\/p>\n\n\n\n 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.<\/p>\n<\/blockquote>\n\n\n\n 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.<\/p>\n\n\n\n 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). <\/p>\n\n\n\n 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.<\/p>\n\n\n\n But this kind of recursion is not mandatory. It’s a tail recursion<\/a>* that can be unrolled<\/a> into iterations (looping), either by the compiler or the programmer, which is what we initially did.<\/p>\n![\"m\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-fdc40b8ad1cdad0aab9d632215459d28_l3.png\" "\\"Rendered")
and ![\"n\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-ec4217f4fa5fcd92a9edceba0e708cf7_l3.png\" "\\"Rendered")
be variables containing the two numbers, divide by . Save the divisor in , and save the remainder in . If is ![\"0\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-8354ade9c79ec6a7ac658f2c3032c9df_l3.png\" "\\"Rendered")
, then stop: contains the GCD. Otherwise repeat the process, starting with division of by .<\/p>\nK.N. King’s C++ Programming (Chapter 6 Exercise 2)<\/cite><\/blockquote>\n\n\n\n![\"(a,b)\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-6086dce942f84541c047c9105b280dd9_l3.png\" "\\"Rendered")
stands for: greatest common divisor. You are looking for the largest factor that simultaneously divides ![\"a\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-0e55b0b3943237ccfc96979505679274_l3.png\" "\\"Rendered")
and ![\"b\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-ad69adf868bc701e561aa555db995f1f_l3.png\" "\\"Rendered")
evenly. If you rethink in terms of multiplication, you are finding the biggest tile size ![\"c\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-276a76eafbebc4494deafceec7cc4ddd_l3.png\" "\\"Rendered")
that can simultaneously cover and without gaps:<\/p>\n\n\n\n s.t. ![\"a = pc\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-277faf1ada2b28493ea22a7cbc0615b2_l3.png\" "\\"Rendered")
and ![\"b= qc\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-b4868377f64f8a7aa5102919e2893fae_l3.png\" "\\"Rendered")
where ![\"p,q\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-b300ac8fbf094ae847c32af05ce7bd2d_l3.png\" "\\"Rendered")
are integers.<\/p>\n\n\n\n\n
and gaplessly<\/strong><\/li>\n\n\n\n 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. <\/p>\n\n\n\n![\"1\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-69a7c7fb1023d315f416440bca10d849_l3.png\" "\\"Rendered")
because divides all integers.<\/p>\n\n\n\n\n
<\/li>\n\n\n\n without gaps using big tiles of size <\/li>\n\n\n\n, the macro-tile is your GCD (perfect-sized tile).<\/li>\n\n\n\n (the divisor becomes the dividend) until there are no gaps (remainder become zero).<\/li>\n<\/ul>\n\n\n\n and ).<\/p>\n\n\n\n![\"(a=50, b=15)\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-e5c8f9911f6042d4dbbc6f8c42c8d8fe_l3.png\" "\\"Rendered")
that terminates early:<\/p>\n\n\n\n![\"50 (dividend) = [15+15+15 (divisor)] + 5 (remainder)\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-e1912abceca1670919e9aa937af0124e_l3.png\" "\\"Rendered")
<\/p>\n\n\n\n![\"15\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-24356614dd1cedf9fcb381d867965978_l3.png\" "\\"Rendered")
and write it in terms of the old remainder ![\"5\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-48348ef601c56286abf49bafe09c7af1_l3.png\" "\\"Rendered")
:<\/p>\n\n\n\n![\"15 = (5+5+5) + 0\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-2453399e6a26ded4a9b8d61d76c6b56f_l3.png\" "\\"Rendered")
<\/p>\n\n\n\n, the old remainder divides the last tile . Since we are dividing in terms of the remainder , we have<\/p>\n\n\n\n\\begin{aligned}\nb &= 15 \\\\\n&= (5+5+5) \\\\\n&= 3r \\\\\n\\\\\na &= 50 \\\\\n& = (15 + 15 + 15) + 5\\\\\n& = 3b + r\\\\\n&= (5+5+5) + (5+5+5) + (5+5+5) + 5\\\\\n&= 3(3r)+r \\\\\n& = 10r\n\\end{aligned}<\/pre><\/div>\n\n\n\n and can be written in terms of integer multiples of ![\"r\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-01bcf7e9e043561da78fecf715c8a46e_l3.png\" "\\"Rendered")
right before the algorithm stops.<\/p>\n\n\n\n
\n\n\n\n![\"(50, 18)\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-65b806f6dd70ded864919cd6904bdcd3_l3.png\" "\\"Rendered")
takes a few more steps: <\/p>\n\n\n\n\\begin{aligned}\nb &= 18\\\\\na &= 50\\\\\n&= (18 + 18) + 14\\\\\n&=2b + r\\\\\nr &= 14 \\\\\n\\\\\nb_1 &= r = 14\\\\\na_1 &= b = 18\\\\\n&= (14) + 4\\\\\n&= b_1 + r_1\\\\\nr_1 &= 4\\\\\n\\\\\nb_2 &=r_1 = 4\\\\\na_2 &= b_1 = 14\\\\\n&= (4+4+4)+2\\\\\n&= 3b_2 + r_2\\\\\nr_2 &= 2\\\\\n\\\\\nb_3 &= r_2 = 2\\\\\na_3 &= b_2 = 4\\\\\n&=(2+2) + 0\\\\\nr_3 &= 0\\\\\n\n\\end{aligned}<\/pre><\/div>\n\n\n\n![\"r_3=0\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-97d9d003ff489e46eaed4c9d602dbae9_l3.png\" "\\"Rendered")
which means we successfully divided the last tile ![\"a_3\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-d11f2cadbba6177eeab8e4d2c74271e7_l3.png\" "\\"Rendered")
with ![\"r_2\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-ef5e0c80de86e7b70c0b6fe84ed0cdf5_l3.png\" "\\"Rendered")
(logistically stored in ![\"b_3\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-f1671db5ba535ae3df5ba6c13b8237e0_l3.png\" "\\"Rendered")
) 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 .<\/p>\n\n\n\n![\"4, 14, 18, 50\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-9753824a1c0669e0017f9739db4ff980_l3.png\" "\\"Rendered")
can be written as a multiple of ![\"2\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-8c267d62c3d7048247917e13baec69a5_l3.png\" "\\"Rendered")
, 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:<\/p>\n\n\n\n\\begin{aligned}\nb_2 &= 2r_2\\\\\n4 &= (2+2) \\\\\n\\\\\nb_1 &= 3b_2 + r_2\\\\\n&= 3(2r_2) + r_2\\\\\n& = 7r_2\\\\\n14 &= [(4+4+4)+2] \\\\\n&= [(2+2)+(2+2)+(2+2)+2] \\\\\n\n\\\\\nb &= b_1 + r_1\\\\\n&=7r_2 + 2r_2\\\\\n&=9r_2\\\\\n18 &= 14 + 4 \\\\\n&= [(4+4+4)+2] + 4 \\\\\n&= [(2+2)+(2+2)+(2+2)+2]+[(2+2)] \\\\\n\\\\\na &= 2b + r\\\\\n&=2(9r_2) + 7r_2\\\\\n&= 25r_2\\\\\n50 & = 18 + 18 + 14 \\\\\n&= [(2+2)+(2+2)+(2+2)+2]+[(2+2)] \\cdots \\\\\n&+ [(2+2)+(2+2)+(2+2)+2]+[(2+2)] \\cdots \\\\\n&+ [(2+2)+(2+2)+(2+2)+2]\n\\end {aligned}<\/pre><\/div>\n\n\n\n![\"x=1\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-5214b37d702dddb0b65242ec8abf41fd_l3.png\" "\\"Rendered")
in ![\"c=ax-by\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-32900b83a1f005e4c8f35becb128d08d_l3.png\" "\\"Rendered")
is the same as writing ![\"a = by+r\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-a97adadd89cf8180e6ba20a02e89dbff_l3.png\" "\\"Rendered")
. We can flip the sign of ![\"y\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-38461fc041e953482219abf5d4cce1cb_l3.png\" "\\"Rendered")
by saying substituting ![\"y'=-y\"](\"https:\/\/wonghoi.humgar.com\/blog\/wp-content\/ql-cache\/quicklatex.com-2f02f6bd6435228aa1b4a02b1742e41b_l3.png\" "\\"Rendered")
.<\/p>\n\n\n\n\n
\\gcd(r_1,r_2) = \\gcd(r_2, r_3) = ... = \\gcd(r_{n-1}, r_n)<\/pre><\/div>\n\n\n\n