Greatest common divisor with Euclid's algorithm step by step, and the least common multiple.
Procedure
How it works
The greatest common divisor $\gcd(a, b)$ is the largest number that divides both $a$ and $b$. Euclid’s algorithm finds it without factoring: replace the pair $(a, b)$ by $(b, a \bmod b)$ until the remainder is 0. The gcd never changes along the way, because any common divisor of $a$ and $b$ also divides $a - q \cdot b$.
The algorithm is fast even for numbers with hundreds of digits: the remainders at least halve every two steps.
The least common multiple is the smallest positive number that both divide, and $\operatorname{lcm}(a, b) \cdot \gcd(a, b) = a \cdot b$. Numbers with $\gcd = 1$ are called coprime.
Everything is calculated in your browser. Nothing you type leaves your device.