GCD & LCM Calculator

Calculate GCD and LCM with Euclidean algorithm visualization

Two Numbers

Method:

Multiple Numbers

Related Formulas

GCD × LCM Product Property:
GCD(a, b) × LCM(a, b) = a × b
LCM from GCD:
LCM(a, b) = (a × b) / GCD(a, b)
Bézout's Identity:
For any integers a, b, there exist integers x, y such that:
a × x + b × y = GCD(a, b)
Coprime (Relatively Prime):
GCD(a, b) = 1 means a and b share no common factors

Help

What is GCD?

The Greatest Common Divisor (GCD) is the largest positive integer that divides all given numbers without remainder.

Example: GCD(12, 18) = 6 because 6 is the largest number that divides both 12 and 18.

What is LCM?

The Least Common Multiple (LCM) is the smallest positive integer that is divisible by all given numbers.

Example: LCM(12, 18) = 36 because 36 is the smallest number divisible by both 12 and 18.

How does the Euclidean Algorithm work?

The Euclidean algorithm repeatedly replaces the larger number with the remainder of dividing the larger by the smaller, until the remainder is 0.

Steps for GCD(48, 18):

  1. 48 = 18 × 2 + 12
  2. 18 = 12 × 1 + 6
  3. 12 = 6 × 2 + 0
  4. GCD = 6 (last non-zero remainder)
What is the Extended Euclidean Algorithm?

The Extended Euclidean Algorithm finds integers x and y (Bézout coefficients) such that:

a × x + b × y = GCD(a, b)

This is used in cryptography, modular arithmetic, and solving Diophantine equations.

What is the Binary GCD Algorithm?

Also known as Stein's algorithm, it computes GCD using bit operations (shift and subtract) instead of division, making it faster on modern computers.

It uses the properties:

  • GCD(a, a) = a
  • GCD(2a, 2b) = 2 × GCD(a, b)
  • GCD(2a, b) = GCD(a, b) if b is odd
  • GCD(a, b) = GCD(|a-b|, min(a,b)) if both odd
How to calculate GCD/LCM of multiple numbers?

Apply the algorithm iteratively:

GCD(a, b, c) = GCD(GCD(a, b), c)

LCM(a, b, c) = LCM(LCM(a, b), c)

Both GCD and LCM are associative, so the order doesn't matter.