The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) are fundamental operations in number theory. The GCD of two numbers is the largest number that divides both evenly, while the LCM is the smallest number that both divide into evenly. This calculator uses the efficient Euclidean algorithm and shows every step of the computation, along with prime factorizations and the mathematical relationship between GCD and LCM.
How to Use
Enter two or more positive integers separated by commas. The calculator instantly shows:
- GCD — the largest number dividing all inputs
- LCM — the smallest number divisible by all inputs
- Euclidean steps — the step-by-step division algorithm
- Prime factorization — each number broken into prime factors
The Euclidean Algorithm
The fastest classical algorithm for GCD: repeatedly replace the larger number with the remainder of dividing the two numbers. When the remainder is 0, the other number is the GCD.
Example: gcd(48, 18): 48 = 2×18 + 12, then 18 = 1×12 + 6, then 12 = 2×6 + 0. GCD = 6.
GCD-LCM Relationship
For any two positive integers a and b: GCD(a,b) × LCM(a,b) = a × b. This means once you know the GCD, you can compute LCM = (a × b) / GCD(a,b) without finding prime factors.
Step-by-Step Instructions
- 1Enter two or more numbers separated by commas.
- 2View the GCD and LCM results instantly.
- 3Study the Euclidean algorithm step-by-step breakdown.
- 4Check prime factorizations of each input number.
- 5See the all common factors list.