GCD and LCM Calculator
Greatest common divisor and least common multiple using the Euclidean algorithm
- Updated
Find
GCD(12, 18)
6
6The greatest common divisor of 12 and 18 is 6, the least common multiple is 36.
How this was calculated
Euclidean algorithm: divide the larger number by the smaller one, then the divisor by the remainder, until the remainder is 0. The last divisor is the GCD.
Using prime factors: the GCD takes each shared factor with the smaller exponent, the LCM takes each factor with the larger one.
Both numbers consist of whole blocks of length 6; no larger common block fits.
- LCM(12, 18)
- 36
RZ-26 · headon.pro
GCD and LCM – basics and applications
Divisors, multiples and the Euclidean algorithm
The greatest common divisor (GCD) and the least common multiple (LCM) are among the most important concepts in elementary number theory. They play a central role in school mathematics, but also in applied mathematics and computer science. The GCD of two numbers a and b is the largest number that divides both without a remainder. The LCM is the smallest number that is divisible by both without a remainder.
Our calculator uses the Euclidean algorithm, one of the oldest algorithms in mathematics (around 300 BC). It calculates the GCD iteratively through repeated division with remainder: GCD(12, 18): 18 mod 12 = 6, then 12 mod 6 = 0 → GCD = 6. The LCM then follows directly from the formula LCM = (a × b) / GCD. For 12 and 18: LCM = (12 × 18) / 6 = 36.
The most important everyday application of the GCD is reducing fractions. To reduce the fraction 18/24: GCD(18, 24) = 6, so 18/24 = 3/4. The LCM is needed when adding fractions with different denominators: 1/4 + 1/6 requires the common denominator LCM(4, 6) = 12. This gives: 3/12 + 2/12 = 5/12. Without the LCM, you would have to work with the product 4 × 6 = 24 and then reduce.
In computer science and cryptography, the GCD is fundamental: the RSA encryption algorithm uses the GCD during key generation (checking for coprimality, the extended Euclidean algorithm) – its security rests on the difficulty of factoring large numbers. Clock frequency synchronization in signal processing uses the LCM of two frequencies. Even in music theory, rhythm corresponds to the LCM of note lengths. The GCD calculator is therefore useful not only for students, but also for engineers and computer scientists.
Calculation example: GCD(12, 18) and LCM(12, 18)
- Step 1: 18 mod 12
- 6
- Step 2: 12 mod 6
- 0 → GCD found
- GCD(12, 18)
- 6
- Formula
- LCM = (a × b) / GCD
- Substitute
- (12 × 18) / 6 = 216 / 6
- LCM(12, 18)
- 36
Frequently asked questions about GCD and LCM
Formulas, algorithms and examples
What is the greatest common divisor (GCD)?
The greatest common divisor (GCD) of two integers a and b is the largest natural number that divides both numbers without a remainder. Example: the divisors of 12 are 1, 2, 3, 4, 6, 12. The divisors of 18 are 1, 2, 3, 6, 9, 18. The greatest common divisor is 6. Applications: reducing fractions, the Euclidean algorithm, cryptography.
What is the least common multiple (LCM)?
The least common multiple (LCM) is the smallest natural number that is divisible by both numbers without a remainder. Example: multiples of 12: 12, 24, 36, 48, … Multiples of 18: 18, 36, 54, … The least common multiple is 36. Applications: adding fractions with different denominators (common denominator = LCM of the denominators).
How does the Euclidean algorithm work?
The Euclidean algorithm calculates the GCD of two numbers a and b efficiently: divide a by b and calculate the remainder r = a mod b. Then set a = b and b = r and repeat. When b = 0, a is the GCD. Example for GCD(12, 18): 18 mod 12 = 6, then 12 mod 6 = 0. GCD = 6. This algorithm is over 2,000 years old and one of the oldest known algorithms.
How do you calculate the LCM from the GCD?
The LCM can be calculated directly from the GCD: LCM(a, b) = |a × b| ÷ GCD(a, b). For a=12 and b=18: LCM = (12 × 18) ÷ 6 = 216 ÷ 6 = 36. This formula is very efficient, since the GCD can be calculated quickly with the Euclidean algorithm, and the LCM then follows as a byproduct. Our calculator uses exactly this method.
Where are GCD and LCM used in everyday life?
The GCD is used to reduce fractions: 12/18 becomes 2/3 by dividing the numerator and denominator by GCD(12,18)=6. The LCM is used when adding fractions with different denominators: 1/4 + 1/6 needs the common denominator LCM(4,6)=12, i.e. 3/12 + 2/12 = 5/12. GCD and LCM are also important tools in computer programming, clock frequency synchronization, and cryptography.