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?