GCF & LCM Calculator: Find Greatest Common Factor and Least Common Multiple

What is the GCF and LCM?

The greatest common factor (GCF) and least common multiple (LCM) are two fundamental concepts in number theory that every student encounters when working with fractions, ratios, and divisibility problems.

The GCF of two or more numbers is the largest whole number that divides evenly into each of them. Take 48 and 72, for example. The factors of 48 are 1, 2, 3, 4, 6, 8, 12, 16, 24, and 48. The factors of 72 are 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, and 72. The common factors are 1, 2, 3, 4, 6, 8, 12, and 24. The greatest among these is 24, so GCF(48, 72) = 24.

The LCM is the smallest positive number that is a multiple of each given number. For 48 and 72, the multiples of 48 are 48, 96, 144, 192, 240... and the multiples of 72 are 72, 144, 216, 288... The first number appearing in both lists is 144, making LCM(48, 72) = 144.

These calculations aren't just academic exercises. When you simplify the fraction 48/72, you divide both numerator and denominator by their GCF of 24 to get 2/3. When adding fractions like 1/48 + 1/72, you need the LCM of 144 as your common denominator.

How It Works: The Mathematics Behind GCF and LCM

Two primary methods exist for finding the GCF: Euclid's algorithm and prime factorization. Euclid's algorithm is remarkably efficient and has been used for over 2,000 years.

Euclid's Algorithm: This method repeatedly applies division with remainder. To find GCF(48, 72):

• Step 1: Divide 72 by 48, getting quotient 1 and remainder 24 (72 = 48 × 1 + 24)
• Step 2: Divide 48 by 24, getting quotient 2 and remainder 0 (48 = 24 × 2 + 0)
• When the remainder reaches 0, the last non-zero remainder is the GCF: 24

Prime Factorization Method: Break each number into its prime factors:

• 48 = 2 × 2 × 2 × 2 × 3 = 2⁴ × 3¹
• 72 = 2 × 2 × 2 × 3 × 3 = 2³ × 3²
• GCF = product of common primes with smallest exponents = 2³ × 3¹ = 8 × 3 = 24

Once you have the GCF, finding the LCM becomes straightforward using the relationship: LCM(a, b) = |a × b| / GCF(a, b). For our example: LCM(48, 72) = (48 × 72) / 24 = 3,456 / 24 = 144.

This relationship holds because the product of two numbers equals the product of their GCF and LCM. Geometrically, if you imagine a rectangle with dimensions 48 by 72, you can tile it perfectly with squares of side length equal to the GCF (24), and the total number of such squares equals the LCM divided by the GCF.

Step-by-Step Guide: Finding GCF and LCM

Step 1: Identify Your Numbers
Write down the two or more numbers you're working with. For this guide, we'll use 84 and 126. Clear identification prevents confusion when juggling multiple calculations.

Step 2: Choose Your Method
For smaller numbers under 100, prime factorization works well. For larger numbers, Euclid's algorithm saves time. With 84 and 126, both methods are manageable. We'll demonstrate Euclid's approach.

Step 3: Apply Euclid's Algorithm
Divide the larger number by the smaller: 126 ÷ 84 = 1 remainder 42. Then divide the previous divisor (84) by the remainder (42): 84 ÷ 42 = 2 remainder 0. The last non-zero remainder is 42, so GCF(84, 126) = 42.

Step 4: Verify with Prime Factorization (Optional)
Break down both numbers: 84 = 2² × 3 × 7 and 126 = 2 × 3² × 7. Common factors are 2, 3, and 7. Taking the smallest exponent for each: 2¹ × 3¹ × 7¹ = 42. This confirms our GCF.

Step 5: Calculate the LCM
Use the formula: LCM = (84 × 126) / 42 = 10,584 / 42 = 252. Alternatively, using prime factors: LCM = 2² × 3² × 7 = 4 × 9 × 7 = 252.

Step 6: Check Your Work
Verify that 252 is divisible by both 84 (252 ÷ 84 = 3) and 126 (252 ÷ 126 = 2). Also confirm that GCF × LCM = 42 × 252 = 10,584, which equals 84 × 126. This cross-check catches calculation errors.

Real-World Examples with Complete Calculations

Example 1: Simplifying a Complex Fraction
A recipe calls for 168/252 cups of flour. To simplify this fraction, find GCF(168, 252). Using Euclid's algorithm: 252 = 168 × 1 + 84, then 168 = 84 × 2 + 0. The GCF is 84. Divide both numerator and denominator by 84: 168÷84 = 2 and 252÷84 = 3. The simplified fraction is 2/3 cup—a much cleaner measurement for cooking.

Example 2: Scheduling Recurring Events
Two buses leave a station on different schedules. Bus A departs every 15 minutes, and Bus B every 20 minutes. If both leave at 8:00 AM, when will they next depart together? Find LCM(15, 20). Prime factorizations: 15 = 3 × 5 and 20 = 2² × 5. LCM = 2² × 3 × 5 = 60. The buses synchronize every 60 minutes, so they'll both depart at 9:00 AM, 10:00 AM, and so on.

Example 3: Tiling a Floor
A rectangular room measures 144 inches by 180 inches. You want to use the largest possible square tiles that fit perfectly without cutting. What size tiles should you buy? Find GCF(144, 180). Using Euclid's algorithm: 180 = 144 × 1 + 36, then 144 = 36 × 4 + 0. The GCF is 36 inches. You need 36" × 36" tiles. The room requires (144÷36) × (180÷36) = 4 × 5 = 20 tiles.

Example 4: Adding Fractions in Construction
A carpenter needs to add 5/24 inch and 7/36 inch to determine total wood thickness. Find LCM(24, 36) for the common denominator. Prime factorizations: 24 = 2³ × 3 and 36 = 2² × 3². LCM = 2³ × 3² = 8 × 9 = 72. Convert: 5/24 = 15/72 and 7/36 = 14/72. Sum: 15/72 + 14/72 = 29/72 inch total thickness.

Example 5: Packaging Products
A factory produces widgets in batches of 56 and gadgets in batches of 84. They want to create gift boxes containing equal numbers of each item with no leftovers. What's the minimum production run? Find LCM(56, 84). Using the GCF method: GCF(56, 84) = 28 (since 84 = 56 × 1 + 28, then 56 = 28 × 2 + 0). LCM = (56 × 84) / 28 = 4,704 / 28 = 168. They need 168 widgets (3 batches) and 168 gadgets (2 batches) to make 168 complete gift boxes.

Common Mistakes to Avoid

Mistake 1: Confusing GCF with LCM
Students frequently mix up which value should be larger. Remember: the GCF cannot exceed the smaller of your numbers (it's a factor, after all), while the LCM cannot be smaller than the larger number (it's a multiple). If you calculate GCF(12, 18) and get 36, something's wrong—36 is bigger than both inputs, so it must be the LCM, not the GCF.

Mistake 2: Stopping Euclid's Algorithm Too Early
The algorithm continues until the remainder equals zero. Some students stop at the first remainder they find. With GCF(91, 143): 143 = 91 × 1 + 52, then 91 = 52 × 1 + 39, then 52 = 39 × 1 + 13, then 39 = 13 × 3 + 0. The GCF is 13, not 52 or 39. Keep dividing until you hit that zero remainder.

Mistake 3: Forgetting to Use Absolute Values
When working with negative numbers, the GCF and LCM are always positive. GCF(-48, 72) equals GCF(48, 72) = 24. The formula LCM(a, b) = |a × b| / GCF(a, b) includes absolute value for a reason. Computing LCM(-12, 18): |(-12) × 18| / 6 = 216 / 6 = 36, not -36.

Mistake 4: Misapplying Prime Factorization
When using prime factorization for LCM, take the largest exponent for each prime, not the smallest. For GCF(72, 108): 72 = 2³ × 3² and 108 = 2² × 3³. GCF uses smallest exponents: 2² × 3² = 36. LCM uses largest: 2³ × 3³ = 216. Mixing these rules produces incorrect results.

Pro Tips for Faster Calculations

Tip 1: Recognize Coprime Numbers Instantly
Two numbers are coprime (relatively prime) when their GCF equals 1. This happens when they share no common prime factors. Consecutive integers are always coprime: GCF(17, 18) = 1. When you spot coprime numbers, the LCM is simply their product. LCM(17, 18) = 17 × 18 = 306 with no further calculation needed. Prime numbers are coprime to any number they don't divide.

Tip 2: Use the Division Ladder for Multiple Numbers
Finding GCF of three or more numbers? Use the division ladder method. Write your numbers in a row (say, 24, 36, 60). Divide all by a common prime (2): you get 12, 18, 30. Divide by 2 again: 6, 9, 15. Now divide by 3: 2, 3, 5. No common divisor remains. Multiply the divisors you used: 2 × 2 × 3 = 12. That's your GCF. This visual approach prevents losing track of factors.

Tip 3: Leverage the GCF-LCM Product Relationship
If you know either the GCF or LCM of two numbers, you instantly know the other. Given GCF(56, 98) = 14, find LCM without prime factorization: LCM = (56 × 98) / 14 = 5,488 / 14 = 392. Conversely, if LCM(21, 35) = 105, then GCF = (21 × 35) / 105 = 735 / 105 = 7. This relationship is a powerful verification tool and time-saver.

Tip 4: Memorize Common Pythagorean Triples and Their GCFs
Many textbook problems use numbers from Pythagorean triples. The 3-4-5 triangle scaled by any factor k gives sides 3k, 4k, 5k with GCF = k. A triangle with sides 36-48-60 has GCF = 12 (it's the 3-4-5 triple scaled by 12). Recognizing these patterns—5-12-13, 8-15-17, 7-24-25—helps you spot GCFs immediately in geometry problems.

Tip 5: Apply Divisibility Rules Before Calculating
Quick divisibility tests reveal common factors fast. Both numbers end in even digits? They share a factor of 2. Do their digit sums divide by 3? They share a factor of 3. For 252 and 378: both are even (factor of 2), both have digit sums divisible by 9 (2+5+2=9, 3+7+8=18), so they share at least 2 × 9 = 18. This pre-screening narrows your search before running Euclid's algorithm.

Frequently Asked Questions