We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
"The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. "
This is because said difference contains the gcd as well. This visualization helps some:
Leonardo's Prime Factors
You are viewing a single comment's thread. Return to all comments →
https://en.wikipedia.org/wiki/Euclidean_algorithm
"The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. "
This is because said difference contains the gcd as well. This visualization helps some:
https://medium.com/i-math/why-does-the-euclidean-algorithm-work-aaf43bd3288e
Basically, any number larger than the smaller number would no longer be a factor for that number, so you can exclude it (and any multiple of it)