Euclid's algorithm finds the greatest common divisor of two whole numbers by dividing the larger by the smaller, then the smaller by the remainder, until the remainder is 0; each division is a step. We ran it on all 49,985,001 pairs of different whole numbers below 10,000. None needed more than 18 steps. The smallest pair needing 18 is 6765 and 4181, two consecutive Fibonacci numbers, and the average was 7.33. The count grows with the number of digits: about 17 on average for two numbers below a billion, in our sample, and never more than 42 there.
The larger number always goes first, so 3 and 2 take two steps. That is the convention of OEIS A051010, whose listed terms our code reproduced one for one.
Euclid's algorithm crawls at consecutive Fibonacci numbers
Divide 6765 by 4181 and the quotient is 1, leaving 2584. The next quotient is 1 again, and so is every one after it until the last, 2 divided by 1; each remainder is the next Fibonacci number down, so the pair walks down the sequence one rung at a time. Since a quotient cannot be less than 1, no pair of smaller numbers can take as many steps.
At every length from 1 to 18 steps, our brute-force search found the smallest pair needing exactly that many to be a Fibonacci pair. Eighteen pairs below 10,000 need 18 steps, and the other seventeen have a larger number between 9,349 and 9,959. Slow pairs are rare: 186 needed 17 steps, against 9,044,048 at the commonest count, 7.
Lamé's bound outruns every pair longer than three digits
The classic limit is five times the number of digits in the smaller number. We read it in E. Lionnet's 1845 paper in the Nouvelles annales de mathématiques, which proves the bound and credits it, "Telle est la limite donnée par M. Lamé", to a note in the Comptes rendus of 28 October 1844; we did not open Lamé's note. Lionnet's proof runs on the series 1, 2, 3, 5, 8, each term the sum of the two before, without calling them Fibonacci numbers.
The bound held for every pair in our sweep and was reached only when the smaller number was 8, 89 or 987, as with 13 and 8 in 5 steps, 144 and 89 in 10, and 1597 and 987 in 15. From four digits on it is never reached. F21 = 10,946 already has five digits, and each further five steps multiply the Fibonacci numbers by about 11.09, more than 10. A nine-digit smaller number can need at most 43, against a bound of 45.
Lionnet also bounds the variant that keeps each remainder under half the divisor: no more steps than there are terms of 1, 2, 5, 12, 29 … up to the smaller number. Its slowest pairs in our runs, such as 8119 and 5741 in 11 steps, approximate √2 and reach that limit exactly; Lionnet does not name √2.
Typical pairs hurry through in about 0.843 × ln n steps
The average was worked out by Heilbronn, Porter and others, whose papers we could not open. OEIS A086237 gives the constant bearing Porter's name as 1.4670780794…, citing Porter (1975) and Knuth (1976). As usually stated, for a fixed n, averaged over the smaller numbers sharing no factor with it, the steps come to 12 ln 2/π² × ln n plus that constant. The multiplier is 0.8428, on our arithmetic.
Our counts fell one step below the formula. Across every n from 5,000 to 9,999 the shortfall averaged 1.00006 steps, ranging from 0.89 to 1.10; the prime 9,973 averaged 8.23 against a prediction of 9.23. The formula counts one more step than A051010; our unconfirmed guess is an opening division that swaps the pair when the smaller number comes first. In our convention the constant would be 0.467.
A 2020 comment on the same page, by Amiram Eldar, states the average for a coprime pair chosen uniformly between 1 and N, with an error term of O(N^(ε−1/6)). As worded, it fits the fixed-n average. Over all 30,397,485 such pairs up to 10,000 we measured 7.81 steps, a constant of 0.046 in our convention.
Repeated subtraction, Euclid's own method, dawdles more as numbers grow
Euclid did not divide. In Elements VII.2, in D. E. Joyce's online edition at Clark University, the method has "the less of the numbers AB and CD being continually subtracted from the greater". A division with quotient 5 is five subtractions, so Euclid's count is the sum of the quotients, recorded as OEIS A049834.
For coprime pairs up to 10,000 we counted 60.5 subtractions against 7.8 divisions on average, a mean pulled up by pairs like 10000 and 1, which take 10,000 subtractions. The medians are 33 against 8. Up to 1,000 the ratio of means was 6.09; up to 10,000, 7.75. On Fibonacci pairs, where every quotient but the last is 1, the subtractions outnumber the divisions by one: 19 against 18 for 6765 and 4181.
Binary GCD takes shorter strides, halving where Euclid divides
The binary method, usually credited to Stein in 1967 (a paper we could not open), uses only halving and subtraction. It first strips any common factors of 2, then repeatedly halves each number until it is odd and subtracts the smaller from the larger. Counting one shift per bit removed, as our implementation does, 10,000,000 random pairs below a billion took 20.59 subtractions and 39.77 shifts each.
Euclid needed 17.03 divisions on the same pairs. We counted operations and timed nothing; which method finishes first depends on what a division costs on the hardware.
The LCM runs past what ordinary JavaScript numbers hold exactly
The least common multiple is the product of two numbers divided by their GCD. Ordinary JavaScript numbers are exact only up to 2⁵³, a limit our IPv6 guide covers. Within it the GCD stays exact; the LCM does not. The smallest failing pair is 94,906,267 and 94,906,265, with an LCM of 9,007,199,326,062,755; in ordinary numbers it comes out ending …756. Of 100,000 random pairs below a billion, 72% gave a wrong LCM that way. Below ten million, none did.
Until 5 November 2026 our GCD and LCM calculator computed that way. It printed …756 for that pair, read 9007199254740993 as …992, cut 2.5 to 2, dropped zeros without a message and showed no Euclid working. The new version computes exactly for numbers of up to 40 digits. It also refuses decimals, handles zeros correctly, and writes out every division step. Type 6765, 4181 and it shows 18 divisions and names that pair as the smallest needing 18. Within its 40-digit range the most any pair can need is 191 divisions, at F193 and F192.
Every pair of safe integers finishes within 76 divisions
The largest Fibonacci number below 2⁵³ is F78, 8,944,394,323,791,464, and its neighbour F77 is 5,527,939,700,884,757. That pair takes 76 divisions, the most any two numbers up to 2⁵³ − 1 can need, since 77 would take a larger number of at least F79, 14,472,334,024,676,221. On ordinary JavaScript numbers, a 77th division means one of the inputs was already past the exact range.
View author profile → · Editorial policy
