GCD & LCM Calculator: Euclidean Algorithm, Coprime, Factorization

Compute GCD and LCM of two or more integers with the Euclidean algorithm, Bézout identity, prime factorization and coprime test. Step-by-step results.

Calculation parameters
Was this calculator useful?

Greatest common divisor and least common multiple

The greatest common divisor GCD(a, b) of two integers not both zero is the largest positive integer that divides both a and b without remainder. The least common multiple LCM(a, b) is the smallest positive integer that is a multiple of both a and b. By convention GCD(0, 0) = 0 and LCM(0, x) = 0. For any integers a, b the fundamental identity holds: GCD(a, b) · LCM(a, b) = |a · b|.

The Euclidean algorithm

The Euclidean algorithm, described in Euclid's Elements (Book VII, ca. 300 BCE), computes GCD(a, b) by successive divisions: GCD(a, b) = GCD(b, a mod b), ending with GCD(x, 0) = |x|. Example: GCD(252, 105) = GCD(105, 42) = GCD(42, 21) = GCD(21, 0) = 21. It terminates in O(log(min(a, b))) steps; its worst-case behaviour is tied to consecutive Fibonacci numbers.

Extended Euclidean algorithm and Bézout's identity

The extended Euclidean algorithm produces not only GCD(a, b) = d but also integers s, t such that d = a · s + b · t — Bézout's identity. These coefficients are essential in cryptography (RSA, modular inverse) and for solving linear Diophantine equations ax + by = c (integer solutions exist iff GCD(a, b) | c).

LCM formula

The least common multiple is computed efficiently from the GCD: LCM(a, b) = |a · b| / GCD(a, b). This avoids enumerating multiples. Example: LCM(12, 18) = 12 · 18 / 6 = 36. For three or more numbers, apply recursively: LCM(a, b, c) = LCM(LCM(a, b), c). Same pattern for GCD.

Prime factorization method

An alternative to Euclid is prime factorization. If a = p₁^α₁ · p₂^α₂ · ... and b = p₁^β₁ · p₂^β₂ · ..., then GCD(a, b) = ∏ pᵢ^min(αᵢ, βᵢ) and LCM(a, b) = ∏ pᵢ^max(αᵢ, βᵢ). Intuitive but inefficient for large numbers: factorization is computationally hard and underpins RSA security.

Coprime integers

Two integers a, b are coprime (relatively prime) iff GCD(a, b) = 1. Critical in number theory: the Chinese Remainder Theorem needs coprime moduli; Euler's totient φ(n) counts integers in [1, n] coprime with n; a modular inverse a⁻¹ mod n exists iff GCD(a, n) = 1. Coprime examples: (8, 15), (9, 28), (13, 100).

GCD properties

  • Commutative: GCD(a, b) = GCD(b, a).
  • Associative: GCD(GCD(a, b), c) = GCD(a, GCD(b, c)).
  • Identity: GCD(a, 0) = |a|; GCD(a, 1) = 1.
  • Distributive: GCD(ka, kb) = |k| · GCD(a, b) for k ≠ 0.
  • Fraction reduction: p/q is in lowest terms iff GCD(p, q) = 1.

How to use this calculator

Enter two or more integers separated by commas (e.g. 12, 18, 24). The tool returns GCD and LCM, shows the Euclidean-algorithm steps, computes Bézout coefficients s, t (for two inputs), prime-factorizes each number and tests pairwise coprimality. Accepts positive or negative integers up to Number.MAX_SAFE_INTEGER (±2^53 − 1 in JavaScript).

Applications

GCD and LCM appear in many practical contexts: simplifying fractions (divide numerator and denominator by their GCD), synchronizing periodic events (two lamps blinking every 12 s and 18 s coincide every LCM = 36 s), cryptography (RSA, ElGamal), process scheduling, music theory (harmonic ratios). In computing, GCD also shows up in minimal cyclic permutations and pseudo-random sequence generation.

A 2300-year-old algorithm

The Euclidean algorithm appears in Book VII of the Elements (circa 300 BC) and is considered the oldest non-trivial algorithm still in use. Its efficiency is remarkable: the number of steps never exceeds five times the number of digits of the smaller number (Lamé's theorem, 1844), and the worst case occurs with two consecutive Fibonacci numbers. Donald Knuth called it "the granddaddy of all algorithms".

Where GCD and LCM work today

GCD arithmetic is everywhere in technology: RSA cryptography picks exponents coprime to the totient of the modulus and computes inverses with the extended Euclidean algorithm; mechanical gearboxes use wheels with coprime tooth counts to spread wear evenly; processors and digital transmissions rely on the LCM to synchronise periodic signals.

Updated July 2026

Frequently Asked Questions

How does the Euclidean algorithm work?

Divide the larger number by the smaller and replace the larger with the remainder, repeating until the remainder is zero: the last nonzero divisor is the GCD. For 48 and 18: 48 = 18·2 + 12, then 18 = 12·1 + 6, finally 12 = 6·2 + 0, so GCD = 6. The calculator shows every division step.

What is the relationship between GCD and LCM?

For two numbers the identity GCD(a,b) × LCM(a,b) = a × b holds. With 48 and 18: the GCD is 6, so LCM = 48·18/6 = 144. The calculator uses exactly this identity, which however only holds for pairs: with three or more numbers the result is obtained by iterating pair by pair over the whole list.

What does it mean for two numbers to be coprime?

Coprime (or relatively prime) means GCD = 1: they share no prime factor, like 8 and 15. They need not be prime themselves: 8 = 2³ and 15 = 3·5 are both composite, yet coprime. Coprimality underlies Euler's totient function and the RSA cryptography that protects online communications.

What is Bézout's identity useful for?

It guarantees that integers x and y exist such that ax + by = GCD(a,b): for 48 and 18, 6 = 48·(−1) + 18·3. The calculator derives them with the extended Euclidean algorithm. It is the tool for computing modular inverses, the heart of modular arithmetic, error-correcting codes and public-key cryptography.

How do you compute GCD and LCM by prime factorization?

Factorize the numbers: the GCD takes the common factors with the minimum exponent, the LCM takes all factors with the maximum exponent. For 48 = 2⁴·3 and 18 = 2·3²: GCD = 2·3 = 6 and LCM = 2⁴·3² = 144. The method is great for teaching but slow on large numbers, where Euclid's algorithm remains unbeatable.

What is the LCM used for in practice?

For adding fractions with the least common denominator, for synchronising periodic events (two buses running every 12 and 18 minutes coincide every LCM = 36 minutes) and for designing gears and maintenance cycles. The GCD instead simplifies fractions and splits quantities into the largest equal parts.

Does the calculator accept more than two numbers?

Yes: enter as many numbers as you want, separated by commas, spaces or semicolons. GCD and LCM are computed iteratively over the whole list; the Euclidean steps and Bézout's identity are shown for the first pair. Any negative signs are ignored by taking the absolute value of each number.

Comments (0)

No comments yet. Be the first!