Intuition behind the proof of the validity of the Euclidean algorithm

Question

As the question title suggests, could anybody explain to me their intuition behind the proof of the validity of the Euclidean algorithm?

Answer 1

As I'm sure you know, the Euclidean Algorithm follows from a lemma that "For $a>b$, $a=qb+r$, $0\leq r\leq |b|-1$, gcd($a,b$)=gcd($b,r$). This allows for the manipulation of the Euclidean Algorithm and its ability to yield our desired gcd.

The proof essentially sets up two different sets relating to gcd($a,b$) and gcd($b,r$), respectively. Then, it shows that the two sets contain one another. Whenever two sets contain one another, we say they are equal (ie. they are the same set).

We'll call one set $S=${$xb+yr|xb+yr>0; x,y\in\mathbb{Z}$} and the other set

$T=${$ua+vb|ua+vb>0; u,v\in\mathbb{Z}$}. As I said earlier, $S$ relates to gcd$(b,r)$ and $T$ relates to gcd$(a,b)$. This is because the GCD Theorem tells us that gcd is the smallest positive linear combination of two numbers. Therefore, since $S$ and $T$ are sets of all possible positive linear combinations, we have that gcd$(a,b)$ is the minimum of $T$ and gcd$(b,r)$ is the minimum of $S$.

In the proof we show that $S=T$, as I said earlier. Since the sets are equal, their minimums are actually the same number. That is, gcd$(b,r)=$ gcd$(a,b)$.

Therefore, we can keep applying the algorithm as we need it since we will always have gcd$(a,b)=$ gcd$(b,r)=$gcd$(r,r_1)=$ gcd$(r_1,r_2)...$

http://mathworld.wolfram.com/GreatestCommonDivisorTheorem.html

http://mathworld.wolfram.com/EuclideanAlgorithm.html

Let me know if that helps!

Answer 2

Just to provide a "visual / geometric intuitive" hint in proving the key passage of the algorithm, i.e.
$gcd(a,b)=gcd(b,r)$ as explained in Ethan's answer, consider that you have a sheet of paper, $a \times b$ in whatever length units (cm, in, ..), and with $a$ and $b$ that we can accept even to be rational.
Now you want to draw the minimum number of vertical and horizontal lines to evenly divide the sheet into squares.
Suppose you have found the right measure and drawn the minimum number of lines, as in the sketch.

Clearly if you cut (or fold out) a $b \times b$ piece, you can transfer the problem to the remaining part.
The same if you cut a second, third, .. part, until you cannot cut more (the height of the remaining is less than $b$).

But now, you can rotate the remaining piece and start again.
At the end of the process you will remain with a perfect square, although tiny it might be. That will give you the measure of the max square whose side fits evenly both in $a$ and $b$.
That you end up with a square is clear, because if $a$ and $b$ are rational then their denominators have a LCM, and $1/LCM$ is the side of a square that for sure fullfils the requirements.
If $a$ and $b$ were real, with $a/b$ rational, (commensurable reals), then the process will terminate in a finite number of steps and with a finite side for the square.