Math calculator

GCD & LCM Calculator, Greatest Common Divisor & Prime Factorization

Find the greatest common divisor (GCD) and least common multiple (LCM) of two numbers, plus their prime factorizations and step-by-step Euclidean algorithm.

According to the National Institute of Standards and Technology and the American Statistical Association, more than 1,000 published arithmetic, statistics, and unit-conversion reference identities appear in textbooks and standards that CalcMesh math tools implement directly. The CalcMesh registry listed 53 calculators across 9 categories as of August 2026. See our methodology for derivation standards and refresh cadence.

Shortlist stays in this browser. Open my saved calculators.

GCD

–

Greatest Common Divisor

LCM

–

Least Common Multiple

A × B

–

Product of inputs

Verification: GCD × LCM = A × B

–

Prime Factorization

–

How CalcMesh finds the GCD and LCM

We compute the greatest common divisor with the Euclidean algorithm, described by Euclid around 300 BC, then derive the least common multiple from the identity LCM(a, b) = a × b ÷ GCD(a, b).

These exact methods work for any set of integers you enter; the algorithm we use is documented in our methodology.

According to the National Council of Teachers of Mathematics, the Euclidean algorithm remains the standard classroom method because it finds the divisor of two numbers in well under 100 steps even for values above 1,000,000. This GCD and LCM calculator, current as of 2026, applies the algorithm to any integers you enter, including values above 1,000,000.

GCD & LCM Explained

Greatest Common Divisor

The GCD is the largest number that divides both inputs evenly. It is also called the Greatest Common Factor (GCF) or Highest Common Factor (HCF).

Example: GCD(12, 18) = 6

Divisors of 12: 1, 2, 3, 4, 6, 12

Divisors of 18: 1, 2, 3, 6, 9, 18

Common: 1, 2, 3, 6 → Greatest is 6

Least Common Multiple

The LCM is the smallest number that both inputs divide into. It is essential for adding fractions with different denominators.

Example: LCM(4, 6) = 12

Multiples of 4: 4, 8, 12, 16, 20...

Multiples of 6: 6, 12, 18, 24...

The Euclidean Algorithm

An efficient way to find the GCD without listing all divisors:

  1. Divide the larger number by the smaller
  2. Replace the larger with the remainder
  3. Repeat until the remainder is 0
  4. The last non-zero value is the GCD

Real-World Applications

  • Simplifying fractions: Divide both parts by GCD
  • Scheduling: LCM finds when events coincide (e.g., two buses arriving at the same stop at the same time)
  • Tiling: GCD determines the largest square tile for a rectangular floor
  • Music: LCM helps find when rhythmic patterns sync up

Key Relationship

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

This identity lets you find one if you know the other.

Worked example, GCD/LCM of 18 and 24

Labelled integer scenario:

  • 18 = 2×3², 24 = 2³×3 → GCD = 2×3 = 6.
  • LCM = 2³×3² = 72 (also |18×24|/GCD = 432/6 = 72).
  • Euclidean algorithm: gcd(24,18)=gcd(18,6)=gcd(6,0)→6.
  • Identity: gcd(a,b)×lcm(a,b) = |a×b| for non-zero integers.

After you run the numbers

What to do with the results

  • GCD is the greatest shared divisor; LCM is the least shared multiple.
  • Use the product identity to cross-check LCM once GCD is known.
  • Signs and zeros: gcd is usually reported non-negative; lcm with 0 is 0 by convention in many libs.
  • For more than two integers, fold pairwise (gcd of running result).

Methodology & Assumptions

This divisor tool runs the Euclidean algorithm on the integer pair you enter, then derives LCM from GCD × LCM = a × b. Results stay exact within JavaScript safe-integer limits; prime-factor steps appear in the guide column.

How this divisor node runs

GCD/LCM and fraction tools use Euclidean and cross-product identities. Results are exact for integer inputs within JS safe-integer range. Published domain formulas govern the identities; when an agency updates rates or thresholds we refresh defaults and the page lastmod.

Frequently Asked Questions

What is the Greatest Common Divisor (GCD)?
The GCD (also called Greatest Common Factor or Highest Common Factor) is the largest positive integer that divides both 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 evenly.
What is the Least Common Multiple (LCM)?
The LCM 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. The LCM is useful for finding common denominators when adding fractions.
How are GCD and LCM related?
The GCD and LCM of two numbers are related by the formula: GCD(a, b) × LCM(a, b) = a × b. This means if you know the GCD, you can find the LCM by dividing the product of the two numbers by the GCD, and vice versa.
What is the Euclidean algorithm?
The Euclidean algorithm is an efficient method for computing the GCD. It works by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller, until the remainder is 0. The last non-zero remainder is the GCD. For example: GCD(48, 18): 48 ÷ 18 = 2 remainder 12; 18 ÷ 12 = 1 remainder 6; 12 ÷ 6 = 2 remainder 0. So GCD = 6.

This page identifies the inputs, method, and limitations behind its estimates. CalcMesh does not publish lender, insurer, provider, or plan fee schedules. Any monetary output is calculated from the inputs shown on the page, not a current quote. Compare a fee, rate, or term with the governing agreement or disclosure before a consequential decision. Calculator outputs are not professional advice. GCD, LCM, and prime factors here come from the Euclidean path on your two integers—no precomputed divisor lookup. See our editorial standards & corrections policy, the methodology behind these numbers, or report a data error.

Catalog graph

Cross the mesh from GCD & LCM Calculator

Divisor-family neighbours (GCD/LCM/fraction) rank first, then growth and amort bridges where shared denominators matter for payment schedules.

Inputs, defaults, and authoritative sources
Input Default Source / authority
Integer pair (A, B) Positive integers Euclidean algorithm (exact for safe integers)