GCD and LCM Explained: What They Are and How to Find Them
GCD (Greatest Common Divisor) and LCM (Least Common Multiple) are two of the most foundational concepts in number theory, and they show up everywhere from simplifying fractions to solving scheduling word problems. Here is exactly what each one means and how to calculate them.
What Is GCD?
The Greatest Common Divisor (also called Greatest Common Factor, or GCF) of two or more numbers is the largest number that divides evenly into all of them, with no remainder.
Example: The GCD of 12 and 18 is 6, since 6 is the largest number that divides evenly into both (12 / 6 = 2, and 18 / 6 = 3).
What Is LCM?
The Least Common Multiple of two or more numbers is the smallest number that all of them divide into evenly.
Example: The LCM of 4 and 6 is 12, since 12 is the smallest number that both 4 and 6 divide into evenly (12 / 4 = 3, and 12 / 6 = 2).
How to Find GCD: The Euclidean Algorithm
The most efficient method for finding GCD, especially for larger numbers, is the Euclidean algorithm. It works by repeatedly applying this rule:
GCD(a, b) = GCD(b, a mod b), repeated until the remainder is 0. The last non-zero remainder is the GCD.
Worked Example: GCD of 48 and 18
48 / 18 = 2 remainder 12 -> GCD(48, 18) = GCD(18, 12)
18 / 12 = 1 remainder 6 -> GCD(18, 12) = GCD(12, 6)
12 / 6 = 2 remainder 0 -> remainder is 0, so GCD = 6
How to Find LCM Using GCD
Once you know the GCD of two numbers, finding the LCM is straightforward using this relationship:
LCM(a, b) = (a x b) / GCD(a, b)
Worked Example: LCM of 48 and 18
We already found GCD(48, 18) = 6, so:
LCM(48, 18) = (48 x 18) / 6 = 864 / 6 = 144
Finding GCD/LCM for More Than Two Numbers
For three or more numbers, you can apply the same process pairwise: find the GCD (or LCM) of the first two numbers, then find the GCD (or LCM) of that result with the next number, and so on.
Worked Example: GCD of 12, 18, and 24
GCD(12, 18) = 6
GCD(6, 24) = 6
So GCD(12, 18, 24) = 6
Where GCD and LCM Show Up in Practice
- Simplifying fractions: Dividing both numerator and denominator by their GCD reduces a fraction to its lowest terms.
- Adding fractions with different denominators: Finding the LCM of the denominators gives you the least common denominator needed to combine the fractions.
- Scheduling problems: LCM is used to solve problems like "two events repeat every 4 days and every 6 days - when do they next coincide?" (answer: the LCM of 4 and 6, which is 12 days).
Step-by-Step: Finding GCD and LCM Yourself
- Apply the Euclidean algorithm - repeatedly divide and take remainders until you reach 0; the last non-zero remainder is your GCD.
- Use the GCD to calculate LCM with the formula (a x b) / GCD(a, b).
- For more than two numbers, repeat the process pairwise across the full list.
Skip the Manual Math - Use Our Free GCD/LCM Calculator
Our free GCD/LCM Calculator instantly finds both values for any set of numbers - just enter them separated by commas.
Final Thoughts
GCD and LCM are two sides of the same coin: GCD finds the largest shared factor, LCM finds the smallest shared multiple. The Euclidean algorithm makes GCD fast to calculate even for large numbers, and once you have that, LCM follows directly from a simple formula.