Intuition behind the proof of the validity of the Euclidean algorithm As the question title suggests, could anybody explain to me their intuition behind the proof of the validity of the Euclidean algorithm?
 A: 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.
A: 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!
A: Assume that we are working for GCD(a, b) and $a=a' + bq$ for some q. We can know that $d$ divides $a$ and $b$ if and only if it divides $a'$ and $b$. 
That's if that $d$ divides $b$ holds $d$ must divide $bq$, and in addition if that $d$ divides $a$  holds $d$ must also divide $a'$. Thus $\text{GCD}(a, b)$ amounts to $\text{GCD}(b, a')$. We put $a'$ after $b$ because $a'$ is less than $b$. Along the same line, we can reduce the two arguments to be samller and smaller(but non-negative), and hence the second one would evetually be zero and $\text{GCD}(a, b)$ would be equivalent to $\text{GCD}(s, 0)$ which is obviously $s$.  
Reference: Algorithmic Toolbox/Week 2/Efficient Algorithm
A: Intuition.
We start with $a \le b$.
First claim:  we can find an integer $m$ so that $na \le b$ but $a(n+1) > b$.
Why?  Well that's the archimedian principal but intuitively we can keep adding up values of (positive) $a$ to get a larger and larger positive number.  Intuitively these will surpass $b$ and there will be a precise value, $n+1$ where it occurs.
That intuition though, relies on i) the natural are unbounded so $b$ can't be larger than every value of $n*a$ and ii) the Well Ordered principal: Every set of natural numbers has a smallest element.  So there are a bunch of values of $a*k > b$ but ... one of them must be the first.  So $a(n+1) > k$  and $a(n+1)$ is the first that is larger so $a*n \le k$, and $a*n$ is the last.
Claim 2: there is an integer $r:  0 \le r < a$ so that $b = an+r$.  
Well we just figured that $an \le b < a*n + a$ so let $r =b-an$.  Intuition? Well, integers are closed under addition.... we can get from any integer to another by counting...
KEY Intuition:  If $d$ is a common divisor of $a$ and of $b$ then it is a common divisor of $r$.  That is because $r = b-an$ is a linear combination of $b,a$ and whatever divides both $b$ and $a$ will divide any linear combination of $a$ and $b$.  That is: if $b = kd$ and $a = jd$ then $r = b- an = kd - jdn = d(k-jn)$.  So any common divisor of $a$ and $b$ and also of the remainder $r$.
And we can repeat with $b_1 = a;  a_1 = r$ and we can get $b_1 = a_1n_1 + r_1$ to find a new $r_1; 0 \le r_1 < a_1=r$ so that a common divisor, $d$, of $a$ and $b$ (and of $r$ so $d$ is a common divisor of $r_1$).  The intuition is if an argument worked once then it will work a second time and a third time and every time we will be a series of $... < r_m < r_{m-1} < .... < r_1 < r$ and all common divisor $d$ will be a common divisors of $r$.
That FINAL intuition is.... this has got to end.  It can't go on forever.
And that intuition is also the well ordered principal.  Each time we do this step we get a smaller and smaller $r_k$ and there must be a smallest last one we reach before we hit $0$.
So we have right before that the last step we have $b_k = a_kn_k + r_k$ where $d$ is a common divisor of $b_k, a_k, r_k$ and of all the $a_i, b_i, r_i$ that we did before including the very first $a,b$.
The next step is there is an $n_{k+1}$ so that $n_{k+1}r_k \le a_k < n_{k+1}r_k + r_k$.  So we have $a_k = n_{k+1}r_k + R$ for some $0 \le R < r_k$ but we said this is the LAST step so we can't have $R > 0$.  So $R=0$ and $a_k = n_{k+1}r_k$ we've reached the end.  $r_k = d$ is a common divisor of $a$ and $b$ and any every other common divisor of $a$ and $b$ will be a divisor of $r_k =d$.
SO $d$ is the greatest common divisor (as anything that divides it can't be bigger).
