finding the gcd using the euclidean algorithm

Remember the GCD (or GCF) from our younger math days?  The greatest common denominator (or factor) seemed pretty retarded.  We never really used it... especially once we had calculators to guess and check for us (or until we all got our TI-83/84/89's and had a function to do it).

But as I hack and slash my way through the dense, unforgiving jungle of Deskin's Abstract Algebra (you'll remember that Mark gave it to me at my birthday, if you were there), I'm finding more and more reasons to think that basic math is cool.  The book is very hard to get through, extremely exact and unforgivingly precise and verbose... but the subjects are things like counting, finding GCD's and LCM's, and expressing integers.

So anyway, I came across the "Euclidean Algorithm" the other day, which basically helps you calculate the GCD of two numbers.  I'll summarize it here.

So suppose two numbers X and Y, and say that we want to find their greatest common factor.  In order for me to show do a simultaneous example with real numbers, let's call say that they happen to equal the integer values 320 and 144, respectively.

Before we calculate the greatest common factor, I need to make a quick segue and discuss the Divisor Theorem.  Another formalization of 3rd grade math, the Divisor Theorem says that the following expression holds for all integers a, b, q, and r, such that b > a > r:

b = aq + r

In 3rd grade terms, b divided by a equals q remainder r.

So with that in mind, let's return to our original problem.  Suppose X > Y (and it is, as 320 > 144).  Then we can create the expression:

X = Y*q1 + r1   |   320 = 144*q1 + r1

Right?  Of course we can, because those are all integers.  So a little third grade division tells us that our numerical example resolves to:

320 = 144*2 + 32

Now, watch this:  we're going to forget X, make Y the largest number, and make the old remainder the new quotient.  Then we'll add a new remainder:

Y = r1*q2 + r2   |   144 = 32*q2 + r2

Now we just solve this in the same fashion:

144 = 32*4 + 16

We follow the same variable shifting pattern (try writing these equations in order on your paper and using arrows to show how the variables move right to left as you go down.  The arrows should end up being diagonal lines from the top-right to the bottom left.):

r1 = r2*q3 + r3   |   32 = 16*q3 + r3

If you understand the pattern we're following, then good!  You know how to use this algorithm.  If not, you're screwed, because we're basically done.  Note that in the above example q3 = 2 and r3 is exactly 0 (because 16 is a factor of 32).  This means we're done!  The number that q3 is multiplying (here, r2=16) is the greatest common factor of the original numbers.  That's it!

Basically, you would keep following this pattern until you got to evenly dividing numbers such that the new remainder is zero.  The greatest common factor of the original X and Y is exactly the number in the position where Y started out.  When I say exactly, what I'm trying to say is that... that's it!  It's not possibly some multiple of that; that is the answer.

More later on how every integer can be expressed in the form ax + by = c, where all those numbers are integers.  It has a lot to do with greatest common factors.

Final note:  the greatest common factor of two numbers A and B is often expressed as (A, B).  This should be easily distinguishable from an ordered pair by the context it's used in.