Euclid's Algorithm: An Analysis | Hacker News Reader

Euclid's Algorithm: An Analysis

blog.adamdklein.com

37 pointsaklein8 comments

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

  17 = 51 - (85 - 51)

  17 = 2 * 51 - 85

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

  17 = 2 * 221 - 3 * 85

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

Interesting historical note.

The original importance of Euclid's algorithm was that it made calculations with ratios easier. And the reason why that was important was currency conversions.

It is used today in cryptography, which is used for online financial transactions.

One way or another, it all comes down to money. :-)

Math, counting and numbers in general were developed for trade - so yes it all comes back to "money" (What you really mean to say is trade). When farmers stopped farming for themselves and started trading with others they suddenly had a need to be able to count how much rice and livestock they had.

Nice analysis if you're into juggling formulas and theorems. I prefer a more pictorial argument like:

  a=24: a a a a a a a a a a a a a a a a a a a a a a a a
  b=18: b b b b b b b b b b b b b b b b b b

  d= 2: d d|d d|d d|d d|d d|d d|d d|d d|d d|d d|d d|d d

  d= 3: d d d|d d d|d d d|d d d|d d d|d d d|d d d|d d d|

  d= 4: d d d d|d d d d|d d d d|d d d d|d d d d|... no good;

multiples of d must hit the ends of b and a

  d:   |                                   |           |


  b=18: b b b b b b b b b b b b b b b b b b
  a-b : a a a a a a

  d:   |           |                       |


  b-(a-b): b b b b b b b b b b b b
  a-b    : a a a a a a

  d:      |           |           |


  b-(a-b)-(a-b): b b b b b b
  a-b          : a a a a a a

  d:            |           |

  d=6

Clicking on that link I expected something more than just the kind of information given by every math textbook covering Euclid's algorithm (with a sketch of proof).

Agreed

It is "grand-daddy" of all algorithms! --Don Knuth

Reply on news.ycombinator.com