GCD and LCM Calculator
Instantly compute the Greatest Common Divisor and Least Common Multiple of two integers. Ideal for simplifying fractions, scheduling repeating events, or solving ratio problems.
About this calculator
The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides both without remainder. The Least Common Multiple (LCM) is the smallest positive integer divisible by both. They are linked by the identity: LCM(a, b) = |a × b| / GCD(a, b). The GCD is found using the Euclidean algorithm: GCD(a, b) = GCD(b, a mod b), recursing until the remainder is 0, at which point the last nonzero value is the GCD. For example, GCD(48, 18) → GCD(18, 12) → GCD(12, 6) → GCD(6, 0) = 6. Then LCM(48, 18) = (48 × 18) / 6 = 144. These operations underpin fraction arithmetic, gear-ratio design, and periodic-event scheduling.
How to use
Enter 48 as the First Number and 18 as the Second Number. The calculator applies the Euclidean algorithm: 48 mod 18 = 12, then 18 mod 12 = 6, then 12 mod 6 = 0, so GCD = 6. Next, LCM = |48 × 18| / 6 = 864 / 6 = 144. The result displays as 'GCD: 6, LCM: 144'. This means 6 is the largest number that divides both 48 and 18, and 144 is the smallest number both divide into evenly.
Frequently asked questions
What is the difference between GCD and LCM and when do you use each?
The GCD tells you the largest factor shared by two numbers and is used when simplifying fractions — divide numerator and denominator by their GCD to reach lowest terms. The LCM gives the smallest common multiple and is used when adding fractions with different denominators or finding when two repeating cycles next coincide. For example, if two buses depart every 12 and every 18 minutes, they next leave together after LCM(12, 18) = 36 minutes.
How does the Euclidean algorithm calculate the GCD efficiently?
The Euclidean algorithm repeatedly replaces the larger number with the remainder of dividing the two numbers, until the remainder is zero. The last nonzero remainder is the GCD. This is dramatically faster than listing all divisors, especially for large numbers. It runs in O(log min(a, b)) steps, making it practical even for integers with hundreds of digits. The algorithm was described by Euclid around 300 BCE and remains one of the oldest and most efficient algorithms in mathematics.
Why is the formula LCM(a,b) = |a × b| / GCD(a,b) always correct?
This identity follows from the Fundamental Theorem of Arithmetic. Every integer's prime factorization is unique, and the GCD picks the minimum power of each shared prime while the LCM picks the maximum power. Because minimum + maximum = sum of both exponents, multiplying a and b counts each prime's contribution once for GCD and once for LCM, so dividing their product by the GCD isolates the LCM. This relationship holds for all positive integers and is the standard way to compute LCM from GCD.