How to Use the Euclidean Algorithm Step Visualizer
The most efficient way to find the greatest common divisor (GCD) of two whole numbers is the Euclidean algorithm. Enter two numbers and this calculator lays out the entire repeated-division process in a table while computing the final GCD.
The method is simple: divide the larger number a by the smaller number b to get a remainder r, then repeat the same process using b and r as the new pair. The moment the remainder hits 0, the divisor used at that step is the greatest common divisor. For example, 252 and 105 go through 252=105×2+42, 105=42×2+21, and 42=21×2+0, landing on a GCD of 21.
This method dates back to Euclid around 300 BC, yet it's still efficient enough to be used today in fields like cryptography and fraction simplification. Watching exactly how many steps it takes to reach the answer is a great way to build intuition for how the algorithm actually works.
Frequently Asked Questions
To find the greatest common divisor of two numbers a and b, you repeatedly replace b with the remainder of a divided by b until the remainder becomes 0. The divisor at that final step is the greatest common divisor (GCD).
This calculator asks you to enter two nonzero whole numbers. Mathematically gcd(a, 0) = a, but since this tool is built to show the step-by-step division process, entering 0 triggers an error message instead.