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 efficiently finds the greatest common divisor (GCD) of two integers — the largest number that divides both without a remainder. This calculator also returns the least common multiple (LCM), which is derived directly from the GCD.
How to Use This Calculator
Enter two whole numbers in the fields above and submit. The calculator uses the absolute values of your inputs, repeatedly applying the rule \(\gcd(a, b) = \gcd(b, a \bmod b)\) until the remainder reaches zero. It then reports both the GCD and the LCM.
The Formula Explained
The core insight is that the GCD of two numbers does not change if you replace the larger number with its remainder when divided by the smaller. Symbolically: $$\gcd(a, b) = \gcd(b, a \bmod b)$$ You keep doing this until \(b = 0\); the last non-zero value is the GCD. The LCM is then computed as $$\operatorname{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}$$ since the product of two numbers equals the product of their GCD and LCM.
Worked Example
Find \(\gcd(48, 36)\): \(48 \bmod 36 = 12\), so \(\gcd(36, 12)\). Then \(36 \bmod 12 = 0\), so the GCD is 12. The LCM is $$\frac{48 \times 36}{12} = \frac{1728}{12} = 144$$
FAQ
What if one number is zero? \(\gcd(a, 0) = a\). The algorithm handles this naturally — the loop stops immediately and returns the non-zero value.
Does the order of a and b matter? No. \(\gcd(a, b) = \gcd(b, a)\); the algorithm self-corrects on the first step.
Can I use negative numbers? Yes. The calculator takes absolute values, since the GCD is conventionally defined as positive.
