Calculate the Greatest Common Divisor (GCD / HCF) for two or more numbers using the Euclidean algorithm with step-by-step division chains.
Click "Calculate GCD" to evaluate numbers.
A carpenter cuts two wooden planks measuring 48 inches and 180 inches into equal segments without any leftover waste: finding the maximum possible segment length requires calculating GCD(48, 180) = 12 inches. A mathematician reducing a fraction 48 / 180 divides both numerator and denominator by their GCD to simplify the ratio to 4 / 15. A network protocol developer setting synchronization intervals between two periodic pulses computes their GCD.
The Greatest Common Divisor (GCD)—also known as the Highest Common Factor (HCF) or Greatest Common Factor (GCF)—is the largest positive integer that divides two or more numbers without leaving a remainder.
The standard efficient method for computing the GCD is the Euclidean Algorithm, developed by ancient Greek mathematician Euclid of Alexandria around 300 BCE. Rather than listing every divisor, the Euclidean algorithm repeatedly takes remainders until the remainder reaches zero. The last non-zero remainder is the GCD. This tool automates the Euclidean algorithm for multiple inputs, displays division step chains, and computes Bézout's Identity linear combination coefficients. The following sections explain Euclidean division step chains, extended Euclidean algorithms, and practical applications in engineering and fraction simplification.
When numbers are submitted, the engine parses the inputs, removes duplicates, and recursively applies the Euclidean algorithm gcd(a, b) = gcd(b, a % b).
1. Euclidean Algorithm Division Chain:
For two positive integers a and b (with a > b):
Step 1: a = b × q₁ + r₁
Step 2: b = r₁ × q₂ + r₂
Step 3: r₁ = r₂ × q₃ + r₃
Continue until remainder r_k = 0. The last non-zero remainder r_(k-1) is GCD(a, b).
2. Multi-Number Associativity:
For three or more numbers a, b, c:
GCD(a, b, c) = GCD(GCD(a, b), c)
3. Bézout's Identity Coefficients:
By working backward through the Euclidean division steps (the Extended Euclidean Algorithm), integers x and y are found such that:
a × x + b × y = GCD(a, b)
Fraction reduction. Dividing the numerator and denominator by their GCD reduces any rational fraction to lowest terms (e.g. 48/180 → (48/12) / (180/12) = 4/15).
Tiling and dimension packing. Determining the largest square tile size that completely covers a rectangular floor of dimensions L × W without cutting tiles requires computing GCD(L, W).
Cryptography and Modular Inverses. The RSA encryption algorithm relies on coprime integers where GCD(e, φ(N)) = 1, enabling the extended Euclidean algorithm to compute private decryption keys.
Ratio simplification. Aspect ratios in digital displays (e.g., 1920×1080) simplify to standard ratios (16:9) by dividing pixel dimensions by their GCD (120).
You can enter two, three, or more numbers separated by commas or spaces into the input field.
Review the Bézout Identity output for two numbers to obtain linear combination multipliers (ax + by = GCD) used in modular arithmetic homework.
For finding least common multiples, pair this tool with our LCM Calculator. For prime decomposition, use our Prime Factorization Calculator.
The calculation engine runs locally in JavaScript using logarithmic-time Euclidean recursion O(log min(a,b)). Calculations evaluate in under 1 millisecond.
| Feature | This Tool | Hand Division | Prime Factor List |
|---|---|---|---|
| Speed | Instant (<1ms) | 3-10 minutes | 5-15 minutes |
| Algorithm | Euclidean Division Chain | Subtractive division | Prime factorization |
| Multi-number Support | Unlimited numbers | 2 numbers practical | 2-3 numbers |
| Bézout Coefficients | Extended Euclidean (x, y) | Manual back substitution | Not listed |
| Privacy | Client-side browser | Paper | Paper |
| Cost | Free | Free | Free |
If two numbers have a GCD equal to 1, they are called coprime or relatively prime (e.g. 8 and 15). They share no common factors other than 1.
Yes. Greatest Common Divisor (GCD) and Highest Common Factor (HCF) are identical terms used interchangeably across US and UK educational systems.
For any two positive integers a and b, their product equals the product of their GCD and LCM: a × b = GCD(a, b) × LCM(a, b).
LCM Calculator — Computes least common multiples using the GCD relationship.
Prime Factorization — Decomposes integers into prime factor trees.
Fraction Calculator — Adds, subtracts, multiplies, and simplifies fractions.