GCD Calculator

Calculate the Greatest Common Divisor of two or more integers. See the step-by-step Euclidean algorithm, prime factorization breakdown, and Bézout coefficients.

How It Works

The Greatest Common Divisor (GCD) — also called the Greatest Common Factor (GCF) or Highest Common Factor (HCF) — is the largest positive integer that divides each of the given numbers without leaving a remainder.

Euclidean Algorithm

This calculator uses the Euclidean algorithm, one of the oldest known algorithms (circa 300 BC). It works by repeatedly replacing the larger number with the remainder of dividing the two numbers, until the remainder is zero. The last non-zero remainder is the GCD.

For example, GCD(48, 18):

1. 48 = 2 × 18 + 12
2. 18 = 1 × 12 + 6
3. 12 = 2 × 6 + 0

The last non-zero remainder is 6, so GCD(48, 18) = 6.

Bézout's Identity

For any two integers a and b, there exist integers x and y such that ax + by = GCD(a, b). The extended Euclidean algorithm finds these coefficients, which are useful in modular arithmetic and cryptography.