I knew I had seen this somewhere before: http://en.wikipedia.org/wiki/Euclidean_algorithm

This is such a natural way to introduce it! I remember that I didn't fully grasp the concepts of what a 'base' is until my first year in college.