ILoveFractions Logo

Search I Love Fractions

Jump to any fraction tool, practice drill, game, or guide.

LCM and GCF Calculator: One Tool for Both

Enter two numbers and get both answers at once: the Least Common Multiple (LCM) and the Greatest Common Factor (GCF, also called the GCD or HCF), with the Euclidean algorithm working shown step by step. If you only need one of them, jump straight to the section you want.

LCM only: how to find the least common multiple GCF only: how to find the greatest common factor

Quick Tips

  • The GCD (Greatest Common Divisor) is the largest number that divides both numbers evenly
  • The LCM (Least Common Multiple) is the smallest number that both numbers divide into evenly
  • The Euclidean algorithm finds the GCD by repeatedly dividing and taking remainders until zero
  • LCM can be calculated using the formula: LCM(a,b) = (a × b) ÷ GCD(a,b)
  • Two numbers with GCD = 1 are called coprime or relatively prime

LCM Only: How to Find the Least Common Multiple

The least common multiple of two numbers is the smallest number that both of them divide into evenly. The LCM of 4 and 6 is 12: the multiples of 4 are 4, 8, 12, 16 and the multiples of 6 are 6, 12, 18, and 12 is the first number that appears in both lists.

Worked example: LCM of 12 and 18

  1. Multiply the two numbers: 12 × 18 = 216.
  2. Find their GCF: the largest number dividing both 12 and 18 is 6.
  3. Divide the product by the GCF: 216 ÷ 6 = 36.
  4. LCM(12, 18) = 36. Check it: 36 ÷ 12 = 3 and 36 ÷ 18 = 2, both exact.

LCM(a, b) = (a × b) ÷ GCF(a, b)

Numbers Product GCF LCM
4 and 624212
12 and 18216636
8 and 1296424
15 and 25375575
7 and 1391191

Reach for the LCM when you need a common denominator for adding or subtracting fractions, or when you need to know when two repeating cycles line up again: two buses leaving every 12 and 18 minutes next depart together after 36 minutes.

GCF Only: How to Find the Greatest Common Factor

The greatest common factor of two numbers is the largest number that divides both of them with no remainder. It goes by three names that all mean the same thing: greatest common factor (GCF), greatest common divisor (GCD), and highest common factor (HCF).

Worked example: GCF of 24 and 36

  1. Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24.
  2. Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36.
  3. Common factors: 1, 2, 3, 4, 6, 12.
  4. The greatest of them is 12, so GCF(24, 36) = 12.

For bigger numbers, use the Euclidean algorithm instead of listing factors. GCF of 180 and 48: 180 ÷ 48 = 3 remainder 36, then 48 ÷ 36 = 1 remainder 12, then 36 ÷ 12 = 3 remainder 0. The last non-zero remainder, 12, is the GCF.

Numbers Common factors GCF
12 and 181, 2, 3, 66
24 and 361, 2, 3, 4, 6, 1212
15 and 251, 55
100 and 751, 5, 2525
7 and 1311 (coprime)

Reach for the GCF when you are simplifying a fraction (divide the numerator and denominator by it) or splitting two quantities into the largest possible equal groups. Try the fraction simplifier if that is what you actually came for: it applies the GCF for you and shows the working.

Understanding GCD and LCM

What is the Greatest Common Divisor (GCD)?

The GCD (also called GCF or HCF) is the largest positive integer that divides two or more numbers without leaving a remainder. It represents the greatest common factor shared by the numbers.

Methods to Find the GCD:

  1. List all factors of both numbers and identify the largest common one
  2. Use prime factorization by finding common prime factors and multiplying them
  3. Use the Euclidean algorithm for a fast and efficient calculation

Pro Tip:

The GCD is the key to simplifying fractions. Divide both the numerator and denominator by their GCD to get the fraction in its simplest form.

The Euclidean Algorithm

The Euclidean algorithm is one of the oldest and most efficient methods for finding the GCD. It was discovered by the ancient Greek mathematician Euclid around 300 BC.

How It Works:

  1. Divide the larger number by the smaller number
  2. Take the remainder from the division
  3. Replace the larger number with the smaller number, and the smaller number with the remainder
  4. Repeat until the remainder is zero
  5. The last non-zero remainder is the GCD

Why It Works:

The algorithm relies on the fact that any common divisor of two numbers also divides their difference (and remainder). By repeatedly reducing the problem to smaller numbers, it efficiently finds the greatest common divisor.

Understanding the Least Common Multiple (LCM)

The LCM is the smallest positive integer that is a multiple of both numbers. It is closely related to the GCD through a simple formula.

The LCM Formula:

LCM(a, b) = (a × b) ÷ GCD(a, b)

This formula shows the relationship between GCD and LCM. The product of two numbers always equals the product of their GCD and LCM.

Pro Tip:

When adding or subtracting fractions with different denominators, the LCM of the denominators gives you the least common denominator, making calculations simpler.

Real-World Applications

GCD and LCM are used in many practical situations beyond the classroom.

  • Simplifying fractions in cooking recipes and measurements
  • Determining gear ratios and planetary alignment in engineering
  • Scheduling repeating events like bus arrivals and work shifts
  • Creating equal-sized groups for events or resource allocation
  • Cryptography and computer science algorithms

Frequently Asked Questions

Common questions about GCD and LCM

The Greatest Common Divisor (GCD), also called the Greatest Common Factor (GCF) or Highest Common Factor (HCF), is the largest positive integer that divides two or more numbers without leaving a remainder. For example, the GCD of 12 and 18 is 6, because 6 is the largest number that divides both 12 and 18 exactly. GCD is found using methods like listing factors, prime factorization, or the Euclidean algorithm.

The Least Common Multiple (LCM) of two numbers is the smallest positive integer that is divisible by both numbers. For example, the LCM of 4 and 6 is 12, because 12 is the smallest number that both 4 and 6 divide into evenly. LCM is useful when adding or subtracting fractions with different denominators, solving scheduling problems, and working with repeating cycles.

The Euclidean algorithm is an efficient method for finding the Greatest Common Divisor (GCD) of two numbers. It works by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller, until the remainder becomes zero. The last non-zero remainder is the GCD. For example, to find GCD(48, 18): 48 ÷ 18 = 2 remainder 12, then 18 ÷ 12 = 1 remainder 6, then 12 ÷ 6 = 2 remainder 0. The GCD is 6. This algorithm has been known since ancient Greece and remains one of the most efficient GCD algorithms.

Use GCD when you need to simplify fractions, divide things into equal groups, or find the largest common factor. Use LCM when you need to find a common denominator for fractions, determine when events will repeat simultaneously (synchronization), or solve problems involving repeating cycles. A helpful way to remember: GCD is about dividing (finding the largest shared divisor), while LCM is about multiplying (finding the smallest shared multiple).

GCD and LCM have many practical applications. GCD is used in simplifying fractions for cooking recipes, dividing items into equal groups, computer graphics for aspect ratios, and cryptography (RSA encryption relies on GCD). LCM is used in scheduling (finding when events align), determining when gears mesh correctly, synchronizing traffic lights, planning manufacturing cycles, and adding or subtracting fractions in construction and measurements.