Skip to main content
ToolSmartly

GCD and LCM Calculator: Find Greatest Common Divisor and Least Common Multiple

Find the GCD and LCM of 2 to 6 whole numbers, with the steps of Euclid’s algorithm, the prime factorisation and a check of the result. Handy for simplifying a fraction or finding a common denominator.

2 numbers
Examples: 12, 18 36, 48 100, 75 12, 18, 24 60, 84, 120 17, 31 (premiers) 1024, 256
↵ Enter to calculate
Enter your numbers and click Calculate.

How to calculate GCD and LCM?

The GCD (Greatest Common Divisor) is the largest integer that divides two or more numbers exactly without a remainder. The LCM (Least Common Multiple) is the smallest positive integer that is a common multiple of all the numbers. These two concepts are fundamental in arithmetic, particularly for simplifying fractions and solving synchronization problems.

The Euclidean algorithm for GCD

The Euclidean algorithm is the most efficient method to calculate GCD. For two numbers a and b, divide a by b and keep remainder r. Then replace a with b and b with r, repeating until the remainder is 0. The last non-zero remainder is the GCD. Example: GCD(48, 18) → 48 = 2×18 + 12 → 18 = 1×12 + 6 → 12 = 2×6 + 0 → GCD = 6.

Relationship between GCD and LCM

For two numbers a and b: GCD(a,b) × LCM(a,b) = a × b. Therefore LCM(a,b) = (a × b) / GCD(a,b). For more than two numbers, GCD and LCM are calculated successively in pairs using the associativity of these operations.

How to find the GCD and LCM

Enter 2 to 6 positive whole numbers. The tool gives the greatest common divisor (GCD, also called HCF) with the steps of Euclid’s algorithm, the least common multiple (LCM), the prime factorisation of each number and a check.

How to use it

  1. Enter at least two whole numbers (six at most); add or remove fields as needed.
  2. Read the GCD and LCM, then the steps: with more than two numbers, the calculation runs pair by pair (partial GCD of the first two, then with the next one…).
  3. The Share button copies a link that reloads the same numbers.

Worked example

For 84 and 126:

  • Euclid: 126 = 1 × 84 + 42, then 84 = 2 × 42 + 0. The last non-zero remainder is 42 = GCD.
  • Prime factors: 84 = 2² × 3 × 7 and 126 = 2 × 3² × 7. The GCD takes the shared factors at their lowest power (2 × 3 × 7 = 42), the LCM every factor at its highest power (2² × 3² × 7 = 252).
  • Check for two numbers: GCD × LCM = 42 × 252 = 10,584 = 84 × 126.

What it is used for

  • Simplifying a fraction: divide the numerator and denominator by their GCD; 84/126 = 2/3.
  • Adding fractions: the lowest common denominator is the LCM of the denominators.
  • Sharing problems: with 84 red and 126 blue marbles, you can make at most 42 identical bags (2 red and 3 blue in each).
  • Timing problems: a bus every 12 minutes and another every 18 minutes leave together every 36 minutes, the LCM of 12 and 18.

Frequently asked questions

What does “coprime” mean?

That the GCD is 1: the numbers share no divisor other than 1, like 17 and 31, or 8 and 15. Their LCM is then simply their product.

Why use Euclid’s algorithm rather than listing divisors?

Because it stays fast even for large numbers: each step replaces the pair by a smaller one, and it never needs to find the prime factors, which becomes slow for big numbers.