The Euclidean algorithm, step by step
How the oldest algorithm still in use finds a greatest common divisor with repeated division, and why it stays fast for large numbers.
The idea behind repeated division
The Euclidean algorithm rests on one observation: any number that divides both a and b also divides their difference, and therefore divides the remainder when a is divided by b. So instead of factoring two numbers, you can replace the larger with that remainder and repeat. Each round shrinks the pair while preserving their common divisors. When the remainder finally reaches zero, the last nonzero value is the greatest common divisor. It is remarkable that a method described by Euclid around 300 BC is still the practical way to compute a GCD today.
A worked example with 48 and 36
Start with 48 and 36. Divide 48 by 36 to get a remainder of 12, so the pair becomes 36 and 12. Divide 36 by 12 to get a remainder of 0, and the algorithm stops. The last nonzero remainder was 12, which is the GCD of 48 and 36. Notice how quickly it terminated: two divisions settled a question that would otherwise mean listing every factor of both numbers. This is exactly the sequence the calculator runs internally for that input.
Extending to a whole list
The greatest common divisor of many numbers can be built from the two-number case because the operation is associative. The tool starts with a running result of the first value, then combines it with the next number, then the next, and so on. Because GCD only ever gets smaller or stays equal as you fold in more values, the running result converges quickly. A list of ten numbers is barely more work than a single pair, which is why the calculator feels instant even on long inputs.
Why it stays fast for big numbers
The number of division steps grows only with the number of digits, not with the size of the values themselves. In the worst case the inputs are consecutive Fibonacci numbers, which is where the algorithm does the most work relative to its size, yet even then the step count stays modest. That efficiency is why the same routine underpins fraction simplification, modular arithmetic and parts of public-key cryptography, not just classroom exercises.