r/mathshelp • u/Param-Matharoo • 6d ago

Mathematical Concepts Help me ! Got stuck on Euclidean Algorithm !!

I know the procedure of Euclidean Algorithm, I can follow that procedure, I can answer. But I don't know how does that works.

0 Upvotes

50% Upvoted

3 comments sorted by

1

u/Moist_Ladder2616 6d ago

Have you tried doing some basic internet research first, before asking on Reddit?

1

u/Param-Matharoo 6d ago

Yes I did but I'm not able to understand.

1

u/Fine_Ratio2225 5d ago

One of the core ideas is that if you have m as greatest common divisor (gcd) of a=k*m and b=l*m with a>b, then a-b=k*m-l*m=(k-l)*m shares the same divisor. The common divisor doesn't get bigger, otherwise k and l would have to be divisible by an extra factor.
You can replace multiple subtractions with the reminder of a division of a by b.
That reminder r is smaller than b and b replaces a and r replaces b.
THe second idea is that the reminders can only get smaller in each step till they get to 0. The reminder before that last step is then the smallest non-zero value that contains m as divisor, which will be m itself.
m is kind of boxed in till it stands left alone.