Why does the Euclidean algorithm for finding GCD work? I am having trouble understanding why the Euclidean algorithm for finding the GCD of two numbers always works? 
I found some resources here (http://www.cut-the-knot.org/blue/Euclid.shtml), and here(http://sites.math.rutgers.edu/~greenfie/gs2004/euclid.html).
But I am a little confused about how they approach it here. I understand that if we have two numbers, a and b, then the greatest common divisor of a and b has to be less than a, and if a divides b, then a will have to be the GCD. 
But I am confused about what happens when:
b=a*q+r
So now, we are saying that we take a/r, correct? Why should we do this at all?
 A: I will try to explain

why the Euclidean algorithm for finding the GCD of two numbers always
  works

by using a standard argument in number theory: showing that a problem is equivalent to the same problem for smaller numbers.
Start with two numbers $a > b \ge  0$. You want to know two things:


*

*their greatest common divisor $g$, 

*and how to represent $g$ as a combination of $a$ and $b$
It's clear that you know both of these things in the easy special case when $b  = 0$.
Suppose $b > 0$. The divide $a$ by $b$ to get a quotient $q$ and a remainder $r$ strictly smaller than $b$:
$$
a = bq + r. \quad \text{(*)}
$$
Now any number that divides both $a$ and $b$ also divides $r$, so divides both $b$ and $r$. Also any number that divides both $b$ and $r$ also divides $a$, so divides both $a$ and $b$. That means that the greatest common divisor of $a$ and $b$ is the same as the greatest common divisor of $b$ and $r$, so (1) has the same answer $g$ for both those pairs.
Moreover, if you can write $g$ as a combination of $b$ and $r$ then you can write it as a combination of $a$ and $b$ (substitute in (*)). That means if you can solve (2) for the pair $(b,r)$ then you can solve it for the pair $(a,b)$.
Taken together, this argument shows that you can replace your problem for $(a,b)$ by the same problem for the smaller pair $(b,r)$. Since the problem can't keep getting smaller forever, eventually you will reach $(z, 0)$ and you're done.
A: Key to your question is the Well-Ordering Principle. It guarantees the existence of a least element for non-empty subsets of the natural numbers. 
The GCD algorithm comes from two principles, the division algorithm and that given any two integers with a common factor, their sum and difference are both divisible by that common factor. 
Suppose you have two natural numbers x and y each divisible by q. Then x=aq and y=bq for some natural numbers a and b.  x+y = q(a+b), so is divisible by q. (x-y)=q(a-b) and again is divisible by q. 
The Division Algorithm guarantees given  a and b, with ab. So s must be less than b and greater than zero. 
Now suppose you want to find the GCD of a and b. 
By the division algorithm we know for some r and s, a=rb+s. Suppose g divides a and b. Since it divides b, it divides rb. Since it also divides a, it also divides a-rb as proven earlier. s is (a-rb) so we have proven g divides s. Why also have that s is smaller than b. 
By iteration we have that b=ps+q. The division algorithm gives us p and q, with q and b having a common factor. 
At each step, the remainder gets smaller and smaller. 
When the remainder is zero, the previous remainder is the common factor of the original two numbers. 
A: Remember that $\gcd(x, y) \vert (ax+by)$ for any linear combination of x and y, and that the smallest possible positive linear combination will always be the $\gcd$.
The Euclidean algorithm is designed to create smaller and smaller positive linear combinations of $x$ and $y$.  Since any set of positive integers has to have a smallest element, this algorithm eventually has to end.  When it does (i.e., when the next step reaches $0$), you've found your $\gcd$.
