Greatest Common Divisor
The largest number that divides both. Euclid finds it in O(log n) steps.
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
Two bars; the GCD is the largest unit that tiles both exactly.
Cost
| 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.
Taught by the same lesson
Number Theory Basics covers these too, in the same run.