GCD & LCM Calculator

Compute Greatest Common Divisor (GCD/GCF/HCF) and Least Common Multiple (LCM) for up to 15 integers with exact Euclidean division tables and prime exponent charts.

Supports up to 15 integers (positive, negative, or zero).
Quick Examples:
Greatest Common Divisor (GCD)
12
Also known as GCF / HCF
Least Common Multiple (LCM)
144
Product / GCD Duality Identity

Step-by-Step Euclidean Algorithm Division Table

The Euclidean algorithm finds the GCD by repeatedly applying division with remainder: Dividend = Quotient × Divisor + Remainder until the remainder reaches exactly 0.

Step 1: GCD(24, 36)
StepDividendDivisorQuotientRemainderDivision Equation
#1243602424 = 0 × 36 + 24
#2362411236 = 1 × 24 + 12
#324122024 = 2 × 12 + 0
Step 2: GCD(12, 48)
StepDividendDivisorQuotientRemainderDivision Equation
#1124801212 = 0 × 48 + 12
#248124048 = 4 × 12 + 0

Prime Factorization Trees & Exponent Chart

The GCD is constructed by taking every shared prime raised to its minimum exponent across all numbers. The LCM is constructed by taking every prime raised to its maximum exponent across all numbers.

Number: 24
23 × 3
Number: 36
22 × 32
Number: 48
24 × 3
Prime Exponent Comparison Table:
Prime Factor (p)Minimum Exponent (min e)GCD Contribution (pmin)Maximum Exponent (max e)LCM Contribution (pmax)
22Math.pow(2, 2) = 44Math.pow(2, 4) = 16
31Math.pow(3, 1) = 32Math.pow(3, 2) = 9
How is this calculated? (View worked mathematical solution)

The Euclidean algorithm evaluates pairwise greatest common divisors without needing prime factorization, while the reduction identity computes exact least common multiples:

1. Greatest Common Divisor (GCD) Step Trace:
Final Evaluated GCD: 12
2. Least Common Multiple (LCM) Identity:
Final Evaluated LCM: 144
Methodology & Mathematical Context

Euclidean Algorithm Efficiency: Discovered around 300 BC by Euclid (Elements, Book VII), the division algorithm computes GCD in logarithmic time proportional to the number of digits (O(log(min(a,b))) steps), making it vastly faster than prime tree decomposition.

Associative Multi-Integer Folding: Because integer ring divisibility is associative over the set of integers Z, lists of three or more integers are evaluated sequentially: GCD(a, b, c) = GCD(GCD(a, b), c).

Zero Divisibility Rule: Since 0 = k × 0 for any integer k, every non-zero integer a divides zero. Therefore, GCD(a, 0) = |a|, while LCM(a, 0) = 0 per NIST DLMF Chapter 27.

About the GCD & LCM Calculator

The Greatest Common Divisor (GCD) — also referred to as Greatest Common Factor (GCF) or Highest Common Factor (HCF) — and the Least Common Multiple (LCM) are foundational pillars of integer number theory and arithmetic. Whether simplifying complex fractions to lowest terms, synchronizing periodic cycles, or finding common grid dimensions, this instrument computes exact GCD and LCM values for up to 15 numbers simultaneously while revealing the underlying step-by-step Euclidean algorithm divisions and prime factorization frequency trees.

Mathematical Formula & Logic

For two positive integers $a$ and $b$, the Euclidean algorithm finds $\text{GCD}(a, b)$ with remarkable speed without requiring prime factorization. By repeatedly applying division with remainder ($a = q \cdot b + r$), the problem reduces to $\text{GCD}(b, r)$ until the remainder $r$ reaches $0$, at which point the last non-zero divisor is the exact GCD. Once the GCD is established, the Least Common Multiple is evaluated via the reduction identity $\text{LCM}(a, b) = \frac{|a \cdot b|}{\text{GCD}(a, b)}$. For lists of three or more integers ($N \ge 3$), computation proceeds associatively by folding the sequence: $\text{GCD}(a, b, c) = \text{GCD}(\text{GCD}(a, b), c)$ and $\text{LCM}(a, b, c) = \text{LCM}(\text{LCM}(a, b), c)$.

Step-by-Step Example

Worked Examples: 1. Example 1 (Euclidean Algorithm for Two Numbers: 24 and 36): Divide 36 by 24 to get 1 remainder 12 (36 = 1×24 + 12). Next, divide 24 by 12 to get 2 remainder 0 (24 = 2×12 + 0). Since the remainder is now 0, the last non-zero remainder is 12, so GCD(24, 36) = 12. The LCM is evaluated as |24 × 36| / 12 = 864 / 12 = 72. 2. Example 2 (Three Numbers: 12, 18, and 24): Fold pairwise from left to right. First compute GCD(12, 18) = 6, then GCD(6, 24) = 6, yielding total GCD = 6. For LCM, compute LCM(12, 18) = (12×18)/6 = 36, then LCM(36, 24) = (36×24)/GCD(36, 24) = 864 / 12 = 72. 3. Example 3 (Coprime Numbers: 15 and 28): Applying the Euclidean algorithm: 28 = 1×15 + 13; 15 = 1×13 + 2; 13 = 6×2 + 1; 2 = 2×1 + 0. Since the last non-zero remainder is 1, GCD(15, 28) = 1 (coprime). Therefore, LCM(15, 28) = (15 × 28) / 1 = 420.

Reference Data & Values

rule nameformulaapplicability
Euclidean Algorithm for Pairwise GCDGCD(a, b) = GCD(b, a mod b) repeatedly until the remainder equals 0, at which point the last non-zero divisor is the GCD.Applies to any pair of integers where at least one operand is non-zero.
Pairwise LCM via Product-GCD ReductionLCM(a, b) = |a * b| / GCD(a, b)Applies to non-zero integers a and b. If either a=0 or b=0, LCM(a,b) = 0 by convention.
Associative Multi-Integer GeneralizationFor N integers, compute GCD and LCM sequentially by folding across the sequence: GCD(a, b, c) = GCD(GCD(a, b), c) and LCM(a, b, c) = LCM(LCM(a, b), c).Applies to any finite set of N >= 3 integers.

Frequently Asked Questions

There is no mathematical difference whatsoever. GCF (Greatest Common Factor) is common in American elementary mathematics, HCF (Highest Common Factor) is standard in British and Commonwealth education systems, and GCD (Greatest Common Divisor) is the formal terminology utilized in university-level number theory and computer science.
For any two integers a and b, the product of their Greatest Common Divisor and their Least Common Multiple equals the absolute value of their direct product: GCD(a, b) × LCM(a, b) = |a × b|. This formula allows you to calculate the LCM instantly once the GCD is known without having to list out multiples.
No. By rigorous mathematical definition, every integer divisor of a number occurs in positive and negative pairs (for instance, 12 is divisible by both 4 and -4). The Greatest Common Divisor strictly chooses the largest positive integer from the set of common divisors, so GCD and LCM are always positive regardless of whether the inputs are negative.
Because distinct prime numbers have no positive divisors other than 1 and themselves, they are always mutually coprime. Therefore, the Greatest Common Divisor of two distinct primes p and q is exactly 1 (GCD = 1), and their Least Common Multiple is simply their direct product (LCM = p × q).
While the product reduction formula works perfectly for exactly two numbers, it breaks down for three or more integers because prime factors shared by only a pair of numbers get over-counted or under-counted. For three numbers, you must either fold the calculation pairwise as LCM(LCM(a, b), c) or take the maximum exponent of each prime factor across all three numbers.
Since zero is evenly divisible by every integer (because 0 = k × 0 for any integer k), every number divides zero. Therefore, the greatest common divisor of any non-zero integer a and 0 is simply the absolute value of a itself: GCD(a, 0) = |a|. Consequently, the LCM of any number and zero is 0.
The Euclidean algorithm operates on the principle that the greatest common divisor of two numbers also divides their remainder when one is divided by the other. Starting with numbers a and b, you divide a by b to obtain remainder r. You then replace a with b and b with r, repeating this division until the remainder becomes exactly 0. The last non-zero remainder is the GCD.
First, break every input number down into its prime factors expressed with exponents (for example, 24 = 2^3 × 3^1 and 36 = 2^2 × 3^2). To find the GCD, take each prime factor that is common to all numbers and raise it to the lowest exponent found across the set (2^2 × 3^1 = 12). To find the LCM, take every unique prime factor present anywhere in the set and raise it to the highest exponent found across the set (2^3 × 3^2 = 72).