LCM & HCF Calculator

Least common multiple and highest common factor of numbers.

Overview

Finds the Least Common Multiple (LCM) and Highest Common Factor (HCF / GCD) for multiple numbers using prime factorization and the Euclidean algorithm.

Formula & Calculation Method

HCF = gcd(a, b) via Euclidean Algorithm: gcd(a, b) = gcd(b, a mod b) | LCM = (|a × b|) / gcd(a, b)

HCF is the largest integer dividing all numbers without remainder; LCM is the smallest positive integer divisible by all numbers.

Worked Example: LCM and HCF of 24 and 36

Inputs: Number 1 = 24 | Number 2 = 36

  • Prime Factorization: 24 = 2³ × 3¹ | 36 = 2² × 3²
  • HCF (lowest powers): 2² × 3¹ = 4 × 3 = 12
  • LCM (highest powers): 2³ × 3² = 8 × 9 = 72
  • Verification: 24 × 36 = 864; HCF × LCM = 12 × 72 = 864

Summary: Numbers = 24, 36 | HCF (GCD) = 12 | LCM = 72 | Product = 864

Common Use Cases

  • Fraction Arithmetic: Find the Lowest Common Denominator (LCD) to add or subtract fractions with unlike denominators.
  • Event Synchronization: Calculate when two periodic events with different cycle intervals will coincide again.
  • Tiling and Packaging: Determine the largest square tile size that perfectly fits a rectangular floor without cuts.

Frequently Asked Questions

How does the Euclidean algorithm find the HCF?

It repeatedly divides the larger number by the smaller and replaces the larger with the remainder until the remainder is zero.

Why do we need LCM to add fractions?

Because you can only add fractions that share a common unit (denominator); the LCM provides the smallest common denominator.

Can two prime numbers have an HCF greater than 1?

No. The HCF of any two distinct prime numbers is always 1, and their LCM is simply their product.

Related Calculators & Tools