The GCD and LCM Calculator finds both the Greatest Common Divisor (GCD) and the Least Common Multiple (LCM) of two or more integers in one step. These two concepts are foundational in number theory and appear throughout arithmetic, algebra, and everyday problem-solving.
The Greatest Common Divisor (also called Greatest Common Factor or GCF) is the largest number that divides evenly into all the given numbers. The Least Common Multiple is the smallest number that all given numbers divide into evenly. For example, for 12 and 18: GCD = 6 (because 6 is the largest number that divides both), and LCM = 36 (because 36 is the smallest number that both 12 and 18 divide into).
Common uses include simplifying fractions (divide numerator and denominator by their GCD), adding or subtracting fractions with different denominators (use the LCM as the common denominator), scheduling repeating events, and solving word problems involving cycles or groups. This calculator shows the full prime factorization and step-by-step working so you can follow the math.
GCD and LCM Calculator
How GCD and LCM Are Calculated
The calculator uses the Euclidean algorithm to find the GCD, which is one of the oldest and most efficient algorithms in mathematics. It works by repeatedly replacing the larger number with the remainder when the larger is divided by the smaller, until the remainder is zero. The last non-zero remainder is the GCD. Once the GCD is known, the LCM is found using the relationship: LCM(a, b) = (a × b) / GCD(a, b).
Example Calculation
Find GCD and LCM of 48 and 36. Euclidean algorithm: 48 ÷ 36 = 1 remainder 12. 36 ÷ 12 = 3 remainder 0. So GCD = 12. LCM = (48 × 36) / 12 = 1728 / 12 = 144. Verification: 144 ÷ 48 = 3 ✓ and 144 ÷ 36 = 4 ✓.
GCD and LCM Reference Table
| a | b | GCD | LCM |
|---|---|---|---|
| 12 | 18 | 6 | 36 |
| 24 | 36 | 12 | 72 |
| 7 | 13 | 1 | 91 |
| 100 | 75 | 25 | 300 |
Frequently Asked Questions
What is the GCD used for?
The GCD is most commonly used to simplify fractions. Divide both the numerator and denominator by their GCD to get the fraction in its simplest form. For example, 18/24 — GCD is 6, so divide both: 3/4.
What is the LCM used for?
The LCM is used when adding or subtracting fractions with different denominators. The LCM of the denominators becomes the common denominator. For example, to add 1/4 + 1/6, find LCM(4,6) = 12, then convert: 3/12 + 2/12 = 5/12.
What if two numbers share no common factors?
If two numbers have no common factors other than 1, they are called coprime or relatively prime. Their GCD is 1, and their LCM equals their product. For example, GCD(7, 13) = 1 and LCM(7, 13) = 91.
Can GCD and LCM be calculated for more than two numbers?
Yes. For three or more numbers, apply the operation pairwise. For example, GCD(12, 18, 24): first find GCD(12, 18) = 6, then GCD(6, 24) = 6. LCM(12, 18, 24): find LCM(12, 18) = 36, then LCM(36, 24) = 72.
What is the relationship between GCD and LCM?
For any two positive integers a and b: GCD(a,b) × LCM(a,b) = a × b. This relationship is why we can always compute the LCM from the GCD without factoring both numbers separately.