Euclidean Algorithm
Replace (a, b) with (b, a mod b) until b is 0. The last non-zero value is the gcd.
Result · step 2 of 5Number Theory Basics: gcd(48, 18) by Euclid
48 mod 18 = 12. Any divisor of 48 and 18 divides 12 too, so the pair becomes (18, 12).
What you will see
(a, b) -> (b, a mod b); the pair shrinks each step; the last non-zero remainder is the answer.
Cost
| Best | O(1) |
|---|---|
| Average | O(log min(a, b)) |
| Worst | O(log min(a, b)) |
| Space | O(1) |
How you work with it here
play it through, step one change at a time, run it on your own input.
Screen readers: Numbers announce their value and role; each step announces the arithmetic performed.
Reduced motion: Values crossfade; no travelling digits.
Before this
Related
Taught by the same lesson
Number Theory Basics covers these too, in the same run.