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 relies on the difficulty of calculating the GCD of 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.