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.

Published by · Reviewed against primary-source formulas

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.

Methodology & Assumptions

This calculator implements standard formulas drawn from primary-source authorities. Values are point-in-time estimates; consult a licensed professional for high-stakes decisions. See the per-input definitions and source citations below.

How this works

Computations are deterministic and run client-side, no inputs leave your browser. Formulas are derived from standard published formulas for the calculator's domain (mortgage, taxes, energy, conversions, etc.). When the underlying agency publishes updated rates or thresholds we refresh defaults and update the page's lastmod timestamp.

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.

Related Calculators

📊
Math

Percentage Calculator

Calculate percentages, percentage change, and percentage of a number instantly.

🔢
Math

Fraction Calculator

Add, subtract, multiply, and divide fractions with step-by-step solutions.

📉
Math

Average Calculator

Calculate mean, median, mode, and range for any set of numbers.

√
Math

Square Root Calculator

Find square roots, cube roots, and nth roots of any number with decimal precision.

💰
Finance

Loan Calculator

Calculate monthly payments, total interest, and amortization schedule for any loan type.

🏠
Finance

Mortgage Calculator

Estimate monthly mortgage payments including principal, interest, taxes, and insurance.

This page identifies the inputs, method, and limitations behind its estimates. Calculator outputs are not professional advice and should be checked against the relevant primary source for a consequential decision. This calculator's formula and defaults are drawn from standard published sources for its domain, no figure is typed in by an editor. See our editorial standards & corrections policy, the methodology behind these numbers, or report a data error.

Inputs, defaults, and authoritative sources
Input Default Source / authority
All inputs Domain-typical defaults Editorial methodology, CalcMesh 2026