How to Calculate GCD and LCM
This calculator finds the Greatest Common Divisor (GCD) and the Least Common Multiple (LCM) of two or three positive integers, using Euclid's algorithm.
Euclid's Algorithm
Euclid's algorithm is one of the oldest known mathematical algorithms, described in Book VII of Euclid's Elements (circa 300 BC). The procedure is elegant in its simplicity:
- Divide the larger number by the smaller and take the remainder
- Replace the larger number with the smaller and the smaller with the remainder
- Repeat until the remainder is zero
- The last non-zero divisor is the GCD
For example, GCD(48, 18): 48 = 2 x 18 + 12, then 18 = 1 x 12 + 6, then 12 = 2 x 6 + 0. Therefore GCD = 6.
The Relationship Between GCD and LCM
For two numbers a and b, the fundamental relationship always holds:
GCD(a, b) x LCM(a, b) = |a x b|
This formula makes it easy to calculate the LCM once the GCD is known: LCM(a, b) = |a x b| / GCD(a, b).
Coprime Numbers
Two numbers are called coprime (or relatively prime) when their GCD is 1, meaning they share no common divisors other than 1. For example, 8 and 15 are coprime. In this case, the LCM equals the product of the two numbers.
Practical Applications
- Simplifying fractions: dividing numerator and denominator by the GCD gives the fraction in lowest terms
- Adding fractions: the LCM of the denominators is the smallest common denominator
- Synchronization problems: periodic events align after a time equal to the LCM of the periods
- Cryptography: the GCD is at the heart of the RSA algorithm, fundamental to computer security