Euclid's Algorithm Gives the GCD and the Recipe for Building It
Gepubliceerd op 27-10-2026 · 3 min leestijd · Dagelijkse calculators
Daniel Okonkwo — Front-enddeveloper en techredacteur bij OneKitly
Webprestaties · Bestandsformaten
Getoetst aan 2 bronnen
The ordinary algorithm repeatedly replaces the larger number by its remainder against the smaller: 252 leaves 42 against 105, 105 leaves 21 against 42, and 42 leaves nothing against 21, so 21 is the greatest common divisor. The extended version keeps track of how each remainder was built along the way and returns two whole numbers that combine the originals into the divisor — here −2 and 5, since 252 × (−2) + 105 × 5 = −504 + 525 = 21. That combination always exists, a fact called Bézout's identity, and it is what produces a modular inverse: when the divisor is one, the coefficient on the first number is exactly the inverse of that number modulo the second.
252 and 105 have a greatest common divisor of 21, and the extended version also returns −2 and 5: 252 × (−2) + 105 × 5 = 21 exactly.
Why it finishes so quickly
Each step replaces a pair by a smaller pair, and the shrinkage is fast: after two steps the larger number is at most half what it was, because a remainder is always smaller than the divisor and either the divisor or the remainder must be below half. The number of steps is therefore proportional to the number of digits rather than to the numbers themselves, which is why the method handles values with hundreds of digits without difficulty. The worst case turns out to be consecutive Fibonacci numbers, which is a pleasing detail and also the reason the bound is usually stated in terms of the logarithm.
The coefficients are not unique
For 240 and 46 the algorithm returns −9 and 47, giving 240 × (−9) + 46 × 47 = 2, and that is one answer among infinitely many: adding twenty-three to the first coefficient and subtracting a hundred and twenty from the second gives another valid pair, and so on for ever. The algorithm returns the pair with the smallest magnitudes, which is the useful representative, and any implementation that compares two results has to normalise before deciding they disagree. That is a general hazard with problems whose answers form a family rather than a point.
| Step | Remainder |
|---|---|
| 252 = 2 × 105 + 42 | 42 |
| 105 = 2 × 42 + 21 | 21 |
| 42 = 2 × 21 + 0 | 0 — stop |
Veelgestelde vragen
- How old is this method?
- It appears in Euclid's Elements, written around three hundred years before the common era, which makes it the oldest algorithm still in routine use. Nothing about it has been improved in the sense that matters: variants exist that avoid division or run better on binary hardware, but the number of steps and the underlying idea are unchanged. That a procedure written for geometry on papyrus is inside every device performing public-key cryptography is one of the more striking continuities in the subject.
- What are the coefficients good for besides inverses?
- For solving equations in whole numbers, which is where they were first wanted. An equation asking for whole-number amounts of two quantities that must total a third has a solution exactly when the greatest common divisor of the two divides the third, and the coefficients give one solution directly; the rest follow by adding multiples of a fixed step. That covers making up an amount from two coin denominations, timing two repeating schedules to coincide, and any similar question where fractional answers are not allowed. It is also the machinery behind reconstructing a value from several remainders at once.
Artikelen die je misschien interesseren
Alle gidsen →Vergelijkbare tools
Bronnen
Een fout in dit artikel gezien?