GCD & LCM Calculator
How to Use
Enter two numbers to calculate their GCD and LCM. You can also enter multiple comma-separated numbers in the first field to find the GCD/LCM of all of them.
What are GCD and LCM?
The Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF), is the largest positive integer that divides two or more numbers without leaving a remainder. The Least Common Multiple (LCM) is the smallest positive integer that is divisible by all given numbers. These are fundamental concepts in number theory with wide applications in mathematics, science, and engineering. The GCD is efficiently computed using the Euclidean algorithm, one of the oldest known algorithms, dating back to around 300 BC. The relationship between GCD and LCM is expressed as: LCM(a, b) = |a x b| / GCD(a, b).
The Euclidean Algorithm
The Euclidean algorithm finds the GCD by repeatedly dividing the larger number by the smaller one and taking the remainder. For example, GCD(48, 18): 48 / 18 = 2 remainder 12, then 18 / 12 = 1 remainder 6, then 12 / 6 = 2 remainder 0. When the remainder reaches 0, the last non-zero remainder (6) is the GCD. This efficient method works for arbitrarily large numbers.
Common Use Cases
- Fraction simplification — divide numerator and denominator by their GCD to reduce fractions to lowest terms
- Scheduling — use LCM to find when recurring events with different intervals will coincide
- Engineering — calculate gear ratios, signal timing, and resonance frequencies using GCD and LCM
- Music theory — determine rhythmic patterns and time signature relationships
- Tiling and layout — find dimensions that evenly divide a space for uniform tile or grid layouts
Privacy
All processing happens in your browser. No data is sent to any server.