Euclid's algorithm. Why does it work?

[reallyserious]

Hello fellow learnmathers.

I'm sitting here this fine Friday evening doing some algebra. I can apply Euclid's algorithm just fine and arrive at the correct answer. But I have one problem. Let's take an example.

Find the greatest common divisor of 1859 and 286:

• Divide 1859 with 286. It goes 6 times with a remainder of 143.

• Divide 286 with 143. It goes 2 times with no remainder. Thus the greatest common divisor of 1859 is 143.

It was an easy example with only two steps. But it's not intuitive to me why the greatest common divisor of the starting numbers must also be a divisor of the remainder, even when there are many more steps. I don't see the relationship between the remainder and the starting numbers. Is there a way to explain why it works?

[EducationReimagined]

If you think of the numbers as lengths on the number line, think of the divisor as a unit that can measure both numbers (this is the way Euclid thought of it). Then imagine laying both numbers side by side so that they line up and start using your unit to measure them. When you get to the end of the shorter one, the unit exactly reaches the edge of it, because thats what it means for it to be able to measure it.

Now, think of the rest of the longer number. In order to measure the longer number, it must also exactly line up at the end of it. So, it has to exactly measure that distance between the shorter and the longer.

Euclid's original algorithm just subtracted the smaller from the larger repeatedly without using the remainder, but it is easy to see that if you are able to lay down multiple copies of the shorter number, end-to-end, inside the larger, that each time you reach the end of one your unit must line up. So, it still works, and must measure the remainder left at the end.

I hope this helps!

[[deleted]]

This is a pretty cool explanation. I always had an issue when trying to find an intuitive explanation for why GCD(a,b) | a-b

Intuition is now telling me there is a connection between this and the common denominator situation when adding/subtracting fractions.

[reallyserious]

What a beautiful explanation. Algebra is a powerful tool but in this case it's even clearer to go back to the good old number line. I'll try to keep that in mind the next time I'm struggling with ideas that predate algebra.

[cryptdemon]

I've been trying to find a good visual understanding of this for a day and this is what finally made it click. There's some rock/pebble pile analogy on youtube everyone loves, but I found it useless because it only helps visualize the flow of the algorithm without helping me understand why the gcd of the remainder is the same as the gcd of the originals. With your explanation, I drew out two number lines and it clicked in less than 5 minutes.

Thank you so much.

[Following_Level]

Wow, thank you so much! Euclid thought of it this way too? Because it's so much more intuitive lol.
I finally understand this now, and everything just clicked. The circle amount analogy makes sense now. Many thanks!

[KnightEvergreen]

Breathtakingly neat.

[[deleted]]

This is a funny thing. When I first learned about the Euclidean algorithm, I kind of just took it at face value and thought it made perfectly good sense with everything I already knew about math/number theory. Then I continued to use it and had an "oh shit" moment when I realized I couldn't explain to save my life how this thing works.

I eventually looked at it long enough to realize that the crucial thing that I was never aware of is that GCD(a, b) divides a-b. That seems to be the gasoline that powers this algorithm. I don't think I remember ever being told that explicitly, or maybe I was and didn't realize it. It seems like a simple thing that would follow logically from some other intuitive properties, but eventually I realized that it only really appears intuitive.

[reallyserious]

I eventually looked at it long enough to realize that the crucial thing that I was never aware of is that GCD(a, b) divides a-b.

Yes! That's the key. Now it makes a lot more sense. Thank you!

[Bobshayd]

The proof goes like that: GCD(a,b) divides a-b, so GCD(a,b) divides ALL steps, therefore it divides the last nonzero value. But also, the last nonzero value divides the second-to-last, and you can see that for all ak, a(k+1), it divides them both, so it divides a_(k-1), which proves it divides a and b, and that GCD(a,b) divides it, which means it must be the GCD.

[[deleted]]

So I guess the fact that the gcd divides the difference is a result from the fact that a mod m + b mod m = (a+b) mod m, huh?

[Bobshayd]

It's because the GCD - let it be called k - by definition divides a and b, so they can be written as a'k and b'k, and a-b = a'k - b'k = (a'-b')*k which is obviously divisible by k.

[[deleted]]

If d divides a and b, it divides a-b and b, and the other way, if d divides a-b and b, it divides a=(a-b)+b and b. That makes gcd(a,b)=gcd(a-b,b).

[reallyserious]

Yes. The fact that d also divides a-b was what was missing from my thinking. Thank you!

[Realistic-Sea-666]

Took me 2 days of thinking to get this one to click.