How this instrument works
The Euclidean algorithm is a procedure, not just an answer: divide a by b and keep only the remainder, then divide b by that remainder and keep the new remainder, and so on, until a division comes out even. The last nonzero remainder in that chain is the greatest common divisor of the original pair. Donald Knuth, in The Art of Computer Programming, called it 'the granddaddy of all algorithms,' since no other procedure from antiquity has stayed in continuous practical use this long — Euclid set down the same steps in Book VII of his Elements roughly twenty-three centuries ago, and a modern computer runs that identical loop billions of times a second.
The step survives unchanged because of one small fact about division: writing a = qb + r means any number dividing both a and b must also divide r, since r is just a minus a multiple of b — and running the equation the other way, any number dividing both b and r must divide a too. The pair (a, b) and the smaller pair (b, r) therefore share the exact same set of common divisors, so swapping to the smaller pair loses nothing. Because the remainders form a strictly decreasing sequence of whole numbers that cannot go below zero, the loop is guaranteed to stop — it just cannot run forever.
The stopping rule doubles as a definition: once a remainder reaches zero, the number it followed divides the previous one exactly, and gcd(n, 0) is defined to equal n, which is exactly the value the loop reports. A genuinely surprising consequence of the same mechanics is which inputs make the loop run longest: not the largest numbers, but consecutive Fibonacci numbers, 13 and 8 or 21 and 13, where every single division has a quotient of 1 and the process grinds through the maximum possible number of steps — a result known as Lamé's theorem.
- Enter a whole number into a.
- Enter a second whole number into b — either field can hold the larger value; the first division sorts that out automatically.
- Read gcd(a, b): the greatest common divisor, equal to the last nonzero remainder the repeated division reaches.
- Change either figure and gcd(a, b) recalculates at once, so you can watch how quickly different pairs settle to their answer.
Worked example — tiling two boards with gcd(48, 18)
A carpenter has two boards, 48 inches and 18 inches long, and wants to cut both into identical square tiles with nothing left over — the longest tile side possible. Set a to 48 and b to 18. First division: 48 mod 18 leaves a remainder of 12, since 18 goes into 48 twice with 12 left. Second division: 18 mod 12 leaves a remainder of 6, since 12 goes into 18 once with 6 left.
Third division: 12 mod 6 leaves a remainder of 0, since 6 divides 12 exactly with nothing left over. That zero ends the loop, and the last nonzero remainder before it, 6, is gcd(48, 18) — matching what this sheet reports for those two inputs. The 48-inch board yields exactly 8 tiles of 6 inches and the 18-inch board yields exactly 3, with no offcut on either piece.
Questions
What exactly does the Euclidean algorithm do?
It replaces a pair of whole numbers with a smaller pair sharing the identical greatest common divisor, over and over, until one number hits zero. Divide the larger by the smaller, keep only the remainder, then repeat with the smaller number and that remainder. For 48 and 18 the remainder chain runs 12, then 6, then 0, so the last nonzero value, 6, is the answer.
Why does replacing (a, b) with (b, a mod b) leave the gcd unchanged?
Write the division as a = qb + r. Any number dividing both a and b must also divide r, since r is simply a minus a multiple of b, and running that equation the other way shows any number dividing both b and r must divide a too. The pairs (a, b) and (b, r) therefore share exactly the same common divisors, so their greatest one never changes as the loop steps forward.
How many steps does the algorithm usually take?
Remarkably few — the number of division steps tracks the digit count of the smaller input, not its size, so even huge numbers resolve in a few dozen steps. The proven worst case, Lamé's theorem, occurs when a and b are consecutive Fibonacci numbers, such as 13 and 8: every single stage then has a quotient of 1, forcing the slowest possible run of the loop.
Does it matter if a is smaller than b?
No. If a is smaller, the first division simply returns a itself as the remainder, since a divided by b gives a quotient of 0, and the next step swaps the pair automatically. The algorithm corrects itself within one extra division, so entering the smaller figure into a costs nothing but a single wasted step.
What is the extended Euclidean algorithm?
A companion procedure that runs the identical divisions while also tracking two extra running numbers, ending with integers x and y such that a·x + b·y = gcd(a, b) — an identity called Bézout's identity. That pair of coefficients underlies modular inverses used in cryptography, a separate calculation from the plain gcd this sheet returns, built from the same loop with one more thing tracked at each step.
How is this different from just stating a greatest common factor?
A greatest common factor is a number; the Euclidean algorithm is the procedure for reaching it without ever listing or comparing factors. That distinction matters at scale: factoring 48 and 18 by hand is trivial, but factoring two forty-digit numbers is currently out of reach, while this same repeated-division loop still finishes in a couple of dozen steps regardless of how stubbornly the numbers factor.