2.1 How Does the Algorithm Work?

I think it is better to answer this question with the help of an example. Suppose that we wanted to find the greatest common divisor between the integers 383 and 283. If I were to use the Euclidean algorithm, this is what I would do on paper (albeit not so neatly - there is a good reason why \(\LaTeX\) is the “gold” standard for most professional Mathematics literature):

\[\begin{align*} 383 &= 283(1) + 100 \\ 283 &= 100(2) + 83 \\ 100 &= 83(1) + 17 \\ 83 &= 17(4) + 15 \\ 17 &= 15(1) + 2 \\ 15 &= 2(7) + 1 \\ 7 &= 7(1) \end{align*}\]

Hence, the greatest common divisor of 383 and 283 is \(1\) (i.e., both numbers are coprime), but more importantly, how did we get to the answer in the first place?

The Euclidean algorithm is based on the fact that the greatest common divisor of two integers does not change if the larger integer is replaced with its difference with the smaller integer (i.e., the greatest common divisor of 383 and 283 is 1, but the greatest common divisor of 383 and (383 - 283) is also 1 - you can verify this yourself using Python’s “math” module or a method of your choosing). Furthermore, the algorithm also makes use of the fact that a division yields two parts: a quotient and a remainder. In other terms, if we have two integers \(a\) and \(b\) and we plan to calculate \(\displaystyle \frac{a}{b}\), then \(a = kb + r\), where \(k\) is the quotient and \(r\) is the remainder of the division.

For this reason, I can repeat the aforementioned as many times as need be to yield smaller numbers until the number on the left hand side (see the above example) is equal to the number on the right hand side.

The Euclidean algorithm also works in reverse - doing so allows us to express the greatest common divisor as a linear combination of the two integers (i.e., the boxed expression below):

\[\begin{align*} 15 - 7(2) &= 1 \\ 15 - 7(17 - 15) &= 1 \\ 8(15) - 7(17) &= 1 \\ 8(83 - 4(17)) - 7(17) &= 1 \\ 8(83) - 39(17) &= 1 \\ 8(83) - 39(100 - 83) &= 1 \\ 47(83) - 39(100) &= 1 \\ 47(283 - 2(100)) - 39(100) &= 1 \\ 47(283) - 133(100) &= 1 \\ 47(283) - 133(383 - 283) &= 1 \\ &\boxed{180(283) - 133(383) = 1} \end{align*}\]

As a sidenote, the problem of trying to find two integers \(a\) and \(b\) such that \(283a + 133b = 1\) is called a Diophantine equation: a kind of polynomial equation with two or more unknowns whose solutions of interest are integers.