What Is Euclid's Algorithm?
Euclid's algorithm is one of the oldest known algorithms, described by the Greek mathematician Euclid around 300 BC. It finds the greatest common divisor (GCD) of two whole numbers — the largest number that divides both of them without leaving a remainder. This calculator applies the algorithm to any two non-negative integers and also returns their least common multiple (LCM).
How to Use It
Enter your two numbers in the fields labelled a and b and submit. The calculator returns the GCD as the main result and the LCM as a secondary value. Order does not matter — \(\gcd(48, 36) = \gcd(36, 48)\). Negative inputs are treated by their absolute value, and if one number is 0 the GCD is simply the other number.
The Formula Explained
The algorithm relies on a simple insight: any common divisor of a and b also divides their remainder a mod b. So we repeatedly replace the larger number with the remainder:
$$\gcd(a,b) = \gcd(b,\, a \bmod b), \quad \gcd(a,0) = a$$
Each step shrinks the numbers quickly, so even huge values resolve in just a handful of iterations. The LCM is then computed as $$\operatorname{lcm}(a,b) = \frac{a \times b}{\gcd(a,b)}$$
Worked Example
Find \(\gcd(48, 36)\):
$$48 \bmod 36 = 12 \to \gcd(36, 12)$$
$$36 \bmod 12 = 0 \to \gcd(12, 0) = 12$$
So the GCD is 12, and the LCM \(= \dfrac{48 \times 36}{12} = \dfrac{1728}{12} = 144\).
FAQ
What if both numbers are 0? The GCD of 0 and 0 is defined here as 0, and the LCM is also 0 since no positive multiple exists.
Why is it faster than listing factors? Instead of finding every divisor, the algorithm uses the remainder shortcut, reducing the problem size dramatically each step — typically logarithmic time.
Can it handle very large numbers? Yes. Euclid's algorithm is efficient even for numbers with many digits, needing only a small number of modulo operations.
