GCD and LCM Calculator
Written by Thierno Sadou Diallo, formula verified per our methodology • Last checked on 9/5/2026
The GCD (greatest common divisor) of two numbers is calculated with Euclid's algorithm, and the LCM (least common multiple) follows from LCM = (a × b) ÷ GCD. For 24 and 36, the GCD is 12 and the LCM is 72.
Explanation
The GCD of two integers is the largest number that divides both of them exactly, with no remainder. Euclid's algorithm, one of the oldest known algorithmic methods (described over 2,000 years ago), computes it efficiently through successive divisions: the larger of the two numbers is replaced by the remainder of its division by the smaller one, and the operation is repeated until the remainder reaches zero — the last nonzero remainder is the GCD. The LCM, the smallest number that's a multiple of both, follows directly from the GCD through the relationship GCD × LCM = a × b, which comes from the prime factorization of the two numbers. Both concepts are commonly used to simplify fractions (dividing the numerator and denominator by their GCD) or to bring several fractions to a common denominator (using their LCM). To solve a quadratic equation, see our quadratic equation calculator.
Example: GCD and LCM of 24 and 36
Inputs
First number: 24. Second number: 36.
Calculation
Euclid's algorithm: 36 ÷ 24, remainder 12; 24 ÷ 12, remainder 0. The GCD is therefore 12. LCM = (24 × 36) ÷ 12 = 864 ÷ 12 = 72.
Result
The GCD of 24 and 36 is 12, and their LCM is 72.
Frequently asked questions
What is the GCD used for in practice?
The GCD is mainly used to reduce a fraction to its simplest form: dividing the numerator and denominator by their GCD gives an equivalent fraction with the smallest possible numbers. For example, 24/36 simplifies to 2/3 by dividing both terms by their GCD, 12.
What is the LCM used for in practice?
The LCM is notably used to bring several fractions to a common denominator before adding or subtracting them, using the smallest possible common denominator rather than an unnecessarily large product. It also comes up in periodicity problems, such as calculating when two cyclical events will next coincide.
What happens if the two numbers share no common divisor other than 1?
Two numbers are said to be coprime when their GCD equals 1 — they share no prime factor. In that case, their LCM simply equals the product of the two numbers, as shown by the example of 17 and 5 (coprime, LCM = 85 = 17 × 5).