Euclid's Algorithm

Take two whole numbers — say 48 and 18 — and ask for their greatest common divisor: the largest number that divides both with no remainder. The obvious method is to list every divisor of each and compare. For small numbers that works; for the 600-digit numbers inside an RSA key it is utterly hopeless.

Around 300 BC, in Book VII of his Elements, Euclid wrote down a far better recipe. It is, by common reckoning, the oldest algorithm still in everyday use — and remarkably, it is also one of the fastest things we know how to compute.

The whole idea fits in one sentence: the common divisors of two numbers are the same as the common divisors of the smaller one and the remainder of dividing the larger by it. Keep taking remainders and the numbers shrink astonishingly fast until one of them hits zero. The other is your answer.

Pick any two positive numbers and run the algorithm one step at a time. Each step replaces the larger number by the remainder of dividing the larger by the smaller. Watch the pair collapse toward the answer.

<p class="hint">{{hint}}</p>
<div class="inputs">
  <label>a <input id="a" type="number" min="1" value="48"></label>
  <label>b <input id="b" type="number" min="1" value="18"></label>
</div>
<div class="pair" id="pair"></div>
<div class="status" id="status">{{status_init}}</div>
<table class="log"><tbody id="log"></tbody></table>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.inputs { display: flex; gap: 1rem; margin: .3rem 0 .6rem; }
.inputs label { font: 600 14px system-ui, sans-serif; color: #1d3557; }
.inputs input { width: 90px; font: 600 15px ui-monospace, monospace; padding: .3rem .4rem;
                border: 1px solid #cdd9e3; border-radius: 6px; }
.pair { display: flex; gap: .6rem; align-items: center; font: 700 26px ui-monospace, monospace;
        color: #1d3557; min-height: 1.4em; margin: .3rem 0; }
.pair .num { background: #e8eef3; border: 1px solid #cdd9e3; border-radius: 8px; padding: .15rem .6rem; }
.pair .gcd { background: #0a7d33; border-color: #0a7d33; color: #fff; }
.status { font-size: 1rem; font-weight: 600; margin: .4rem 0; min-height: 1.3em; }
.status.ok { color: #0a7d33; }
.log { border-collapse: collapse; font: 13px ui-monospace, monospace; margin: .3rem 0; }
.log td { border: 1px solid #e0e6ec; padding: .2rem .55rem; }
.log td:first-child { color: #888; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .4rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: default; }

// Code not found

Notice how few steps it takes. Even starting from large, unrelated numbers, the pair shrinks by a lot every couple of steps — never by just one. Try 48 and 18, then try the consecutive Fibonacci numbers 89 and 55: those are the worst case, the inputs that force the most steps, and even they finish in a handful. That is the magic: brute-force divisor hunting would take thousands of checks where Euclid takes single digits.

How fast is Euclid's algorithm, really? It is solved — and the answer is wonderfully good.

• Naive divisor hunting checks numbers up to the smaller input — that is linear in the value of the input, which means exponential in the number of digits. For big numbers it never finishes.
• Euclid's method is logarithmic in the inputs. Each two steps at least halve the larger number, so the number of steps is proportional to the number of digits, not the value. This makes it polynomial time — squarely in the easy class P.
• The worst case is the Fibonacci numbers. In 1844, Gabriel Lamé proved that the inputs forcing the most steps are consecutive Fibonacci numbers, and that the step count never exceeds about 5 times the number of decimal digits of the smaller number. This is the first known application of Fibonacci numbers to algorithm analysis.
• The extended version solves more. A small bookkeeping addition — the extended Euclidean algorithm — also finds the modular inverse, the engine behind public-key cryptography.

That is the punchline: an algorithm written before the printing press, before zero reached Europe, before computers existed, sits comfortably inside the class of efficiently solvable problems — and we have a clean proof of exactly how fast it is.

"Find the greatest common divisor — fast" turns out to be a building block under a surprising amount of modern computing:

• Reducing fractions: every time software simplifies 48/18 to 8/3, it divides both by their GCD.
• Modular inverses and cryptography: the extended Euclidean algorithm computes the inverse keys at the heart of RSA and elliptic-curve schemes — without it, public-key crypto could not generate keys.
• Error-correcting codes: GCD of polynomials decodes Reed–Solomon codes that protect CDs, QR codes and deep-space transmissions.
• Computer algebra: symbolic math systems cancel common factors in polynomials using the same idea Euclid used for integers.

Learn why Euclid's method is fast and you have met the deep theme of complexity: a clever insight can turn an apparently exponential search into a logarithmic stroll — the opposite story to the intractable problems behind P vs NP.

Euclid's algorithm is a quiet marvel: a procedure written around 300 BC that we still run, unchanged in spirit, billions of times a day. It is the oldest algorithm humanity recorded, and far from being a museum piece, it is provably efficient — logarithmic in its inputs, with Lamé's 1844 proof pinning down its worst case exactly.

The lesson outlives the method. Most of the limits of computation are about problems we cannot speed up. Euclid is the cheerful counterexample: sometimes the right idea collapses a hopeless search into a few divisions. Two and a half millennia later, that idea still secures your messages — see how it powers RSA.