Euclid's shortcut for finding the greatest common divisor still runs inside computers
What is the largest square tile that will cover a 24 by 60 floor with no cutting? The answer, 12, is the greatest common divisor of the two lengths. Listing every divisor gets slow for large numbers, but a trick Euclid described over two thousand years ago finds it in a few quick steps.
The greatest common divisor of two whole numbers is the largest positive number dividing both. For 54 and 24, the shared divisors are 1, 2, 3 and 6, so the answer is 6. It also goes by greatest common factor or highest common factor, and historically greatest common measure. Numbers whose only shared divisor is 1, like 9 and 28, are called coprime. The idea is handy for reducing fractions: since 14 divides both 42 and 56, the fraction 42 over 56 simplifies to 3 over 4.
Euclid's insight was that any number dividing both a and b also divides their difference. So you can keep replacing the larger number with the difference until the two match. For 48 and 18 the pairs run 30 and 18, then 12 and 18, then 12 and 6, and finally 6 and 6, where they meet. That can crawl when one number dwarfs the other, so the usual Euclidean algorithm uses the remainder after division instead, reaching 6 from 48 and 18 in three steps.
Computers often use a binary variant. It repeatedly halves even numbers, which in binary means just dropping the last digit, and checking whether a number is even means looking only at that last digit, making each step very cheap.
Prime factorisation also works, comparing the shared prime powers, but factoring large numbers takes too long for practical use. Edge cases need rules too: the divisor of a number and zero is the number itself, which is how the Euclidean algorithm stops, and many computer algebra systems define the case of zero and zero as zero.
Source: Greatest common divisor
