Mathématiques et Algèbre

LCM & GCD (HCF) Calculator — Prime Factorization & Euclidean Method

Finding common factors and multiples is an essential skill in arithmetic, fraction simplification, modular cryptography, and problem solving. Our free LCM & GCD Calculator computes the Greatest Common Divisor (GCD)—also known as Highest Common Factor (HCF)—and the Least Common Multiple (LCM) for any list of integers. Featuring step-by-step Euclidean algorithm steps and prime factorization tree breakdowns, this tool makes factor math easy to understand.

LCM & GCD (HCF) Calculator

Calculate Greatest Common Divisor, Least Common Multiple & Prime Factorization

Enter Numbers (comma or space separated)

Example presets: | |

Calculated GCD & LCM Results

Greatest Common Divisor (GCD / HCF)

Least Common Multiple (LCM)

144

Prime Factorization Breakdown

2³ × 3

2² × 3²

2⁴ × 3

Step-by-Step Euclidean Algorithm (GCD for 24 & 36)

Step 1: 36 = (24 × 1) + 12

Step 2: 24 = (12 × 2) + 0

Mathematical Formulas & Calculation Methods

GCD and LCM Product Rule

For any two positive integers a and b, the product of their GCD and LCM equals the product of the numbers.

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

Euclidean Algorithm for GCD

Repeatedly replaces (a, b) with (b, a mod b) until the remainder becomes zero. The final non-zero remainder is the GCD.

GCD(a, b) = GCD(b, a mod b)

Prime Factorization Method

Expresses numbers as products of prime factors. GCD takes the lowest power of common primes; LCM takes the highest power of all primes.

GCD = ∏ p_i^(min(a_i, b_i)) | LCM = ∏ p_i^(max(a_i, b_i))

Worked Step-by-Step Examples

Example 1: Finding GCD and LCM of 24 and 36

"Find GCD(24, 36) and LCM(24, 36)."

Steps:

Find prime factors of 24: 2³ × 3¹ = 24.
Find prime factors of 36: 2² × 3² = 36.
Calculate GCD (lowest prime powers): 2² × 3¹ = 4 × 3 = 12.
Calculate LCM (highest prime powers): 2³ × 3² = 8 × 9 = 72.

Result: GCD = 12, LCM = 72

Example 2: Euclidean Algorithm for GCD(1071, 462)

"Use the Euclidean algorithm to calculate GCD(1071, 462)."

Steps:

Step 1: 1071 = (2 × 462) + 147
Step 2: 462 = (3 × 147) + 21
Step 3: 147 = (7 × 21) + 0
Last non-zero remainder is 21.

Result: GCD(1071, 462) = 21

What is Calculateur de LCM & GCD (HCF)?

An LCM and GCD calculator is a number-theory solver that computes common multiplicative properties of integers. The Greatest Common Divisor (GCD), also called Highest Common Factor (HCF), is the largest positive integer that divides all input numbers without leaving a remainder.

The Least Common Multiple (LCM) is the smallest positive integer that is divisible by all input numbers. LCM calculations are essential for finding common denominators when adding or subtracting fractions with different denominators.

When two numbers have a GCD equal to 1 (GCD(a, b) = 1), they are described as coprime or relatively prime. Coprime numbers share no common factors other than 1, meaning their LCM is simply their direct product (a × b).

How to Use Calculateur de LCM & GCD (HCF)

1Enter two or more integers separated by commas into the number input field.
2Click Calculate to view the GCD (HCF) and LCM values instantly.
3Explore the prime factorization breakdown table for each input number.
4Review the Euclidean algorithm step-by-step division process.

Key Features

Multi-number support (calculate GCD & LCM for 2, 3, or more numbers simultaneously).
Prime factorization decomposition trees.
Step-by-step Euclidean algorithm division step viewer.
Coprime (relatively prime) indicator check.
Instant common denominator generator for fractions.

Benefits of Using Calculateur de LCM & GCD (HCF)

Makes fraction addition and subtraction easy by finding the Lowest Common Denominator (LCD).

Automates multi-digit Euclidean divisions without manual scrap paper calculations.

Helps students understand prime factorization concepts visually.

Useful for solving real-world periodic scheduling and gear ratio problems.

Practical Use Cases

Elementary & Middle School Students

Simplify fractions to lowest terms and find least common denominators.

Competitive Programming Students

Solve modular arithmetic, clock sync, and number theory contest problems.

Engineers & Mechanics

Calculate gear teeth mesh ratios and rotational cycle alignments.

Event Coordinators

Determine repeating event cycles and synchronized schedule overlaps.

Frequently Asked Questions

What is the difference between GCD and HCF?

GCD (Greatest Common Divisor) and HCF (Highest Common Factor) are two terms for the exact same mathematical concept: the largest integer that divides all given numbers without a remainder.

What are coprime numbers?

Coprime (or relatively prime) numbers are integers that have a Greatest Common Divisor of 1. For example, 8 and 15 are coprime because their only common factor is 1.

How does the Euclidean algorithm work?

The Euclidean algorithm repeatedly divides the larger number by the smaller number and replaces the pair with (smaller number, remainder) until the remainder reaches zero. The last non-zero remainder is the GCD.

How do you find the LCM of three numbers?

To find the LCM of three numbers (a, b, c), first calculate LCM(a, b) = L1, then calculate LCM(L1, c). Alternatively, use prime factorization by taking the highest power of every prime factor.

Why is GCD useful in real life?

GCD is used to simplify ratios, divide quantities into equal groups without leftover remainders, design floor tiles without cutting, and compute public-key RSA cryptography keys.

Calculateurs Similaires

Math & Algebra