[redxaxder]

Euclid's algorithm doesn't make as much sense until you see it done at least once. It's a shame there's no example. Finding the GCD of 85 and 221:

  221 = 2 * 85 + 51

  85 = 51 + 34

  51 = 34 + 17

  34 = 2 * 17 + 0

So our GCD is 17. Why? Well, if we rearrange the parts, we get...

  51 = 34 + 17, so 51 = (2 * 17) + 17 = 3 * 17

  85 = 51 + 34 = (3 * 17) + (2 * 17)

  85 = 5 * 17

  221 = 2 * (5 * 17) + (3 * 17) 

  221 = 13 * 17

So 221 and 85 are both divisible by 17.

Bonus: This also gives us a way to write 17 as an integral combination of 221 and 85. We also get this by rearranging the parts:

  17 = 51 - 34

  34 = 85 - 51

  51 = 221 - 2 * 85

so

  17 = 51 - (85 - 51)

  17 = 2 * 51 - 85

  17 = 2 * (221 - 2 * 85) - 85

  17 = 2 * 221 - 3 * 85

[aklein]

Cool, you're right, examples are good. Thanks for pointing out!