SamCalculator

GCD Calculator

Calculate the Greatest Common Divisor (also called HCF or GCF) using the Euclidean algorithm, prime factorisation, or a repeated-division ladder with full step-by-step solutions.

Enter numbers to find the GCD

Accepts comma, space, semicolon, or newline-separated positive whole numbers up to 1,000,000,000,000.

What is the GCD Calculator?

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 every input cleanly. It is the natural answer to questions like 'What is the largest equal share I can make?' or 'What is the simplest form of this ratio?'

This GCD calculator factors each input by trial division, intersects the prime factorisations using the lowest shared exponent, and shows the full Euclidean-algorithm derivation side-by-side. You get the GCD, the list of every common divisor, the prime-factor table, and a step-by-step solution in three independent methods — Prime Factorisation, Euclidean Algorithm, and the Repeated-Division Ladder.

How the GCD Calculator works

Method 1 — Prime factorisation

Factor every input. For each prime that appears in EVERY input, take the LOWEST exponent. Multiply the result to get the GCD.

Method 2 — Euclidean algorithm

Repeatedly replace the larger number by the remainder of dividing it by the smaller. The last non-zero remainder is the GCD. Runs in O(log min(a, b)) steps.

Method 3 — Repeated-division ladder

Stack the inputs in a row. Divide them all by the smallest prime that divides every one. Repeat. When no prime divides every value, multiply the divisors used — that product is the GCD.

Cross-check via the identity

Once you know GCD, LCM × GCD = a × b confirms the value for two-input cases. The calculator runs this check automatically and flags any inconsistency.

GCD formula library

Euclidean algorithm

gcd(a, b) = gcd(b, a mod b)

Replace the larger by the remainder. Terminates in O(log min(a, b)) steps.

LCM × GCD identity

LCM(a, b) × GCD(a, b) = a × b

True for any pair of positive integers. Use it to read one off the other in constant time.

Prime-factor GCD

GCD = p₁^min(e) × p₂^min(e) × …

Take the LOWEST exponent of each prime that appears in EVERY input.

Coprime check

coprime ⟺ gcd(a, b) = 1

Two integers are coprime exactly when their GCD is 1.

When to use the GCD calculator

Simplifying fractions

Divide numerator and denominator by their GCD. The result is in lowest terms in one step.

Reducing ratios

Aspect ratios, recipe scaling, and screen resolutions all reduce by the GCD. 1920 × 1080 simplifies to 16 : 9 because GCD(1920, 1080) = 120.

Modular arithmetic

The modular inverse a⁻¹ mod n exists exactly when gcd(a, n) = 1. The extended Euclidean algorithm computes the inverse in the same number of steps as the plain GCD.

Splitting into equal groups

When you must split multiple quantities into groups of equal size, the LARGEST group size that works is the GCD of the quantities.

Why GCD matters

Euclid's algorithm for the GCD, written down ~300 BC, is the oldest non-trivial algorithm in continuous use. Every modern cryptography library executes some variation of it billions of times a day — for example, every time an RSA public key is generated, GCD is used to verify that the chosen exponent is coprime to the totient of the modulus.

Outside cryptography, GCD shows up wherever 'common factor' is a concept: simplifying fractions, reducing ratios in design and music, normalising sampling rates in audio software, and computing cycle lengths in deterministic finite automata. The classroom and the data centre rely on the same compact recursion.

Frequently Asked Questions

The Greatest Common Divisor (GCD), also called Highest Common Factor (HCF) or Greatest Common Factor (GCF), is the largest positive integer that divides every input without remainder. For example, GCD(12, 18) = 6.

Two classic methods: (1) Prime factorisation — for each prime that appears in EVERY input, take the LOWEST exponent and multiply. (2) Euclidean algorithm — repeatedly replace the larger number by the remainder of dividing it by the smaller until the remainder is zero; the last non-zero remainder is the GCD. The Euclidean algorithm is fastest for large numbers.

An iterative procedure: gcd(a, b) = gcd(b, a mod b). It uses the fact that any common divisor of a and b also divides a − b, hence also a mod b. Iteration terminates when the remainder is zero, and runs in O(log(min(a, b))) steps — fast enough to compute the GCD of two 18-digit numbers in microseconds.

GCD(330, 75, 450, 225) = 15. Prime form: 330 = 2 × 3 × 5 × 11, 75 = 3 × 5², 450 = 2 × 3² × 5², 225 = 3² × 5². Primes 3 and 5 appear in every input; lowest exponent for 3 is 1 (from 330) and for 5 is 1 (from 330). So GCD = 3 × 5 = 15.

Nothing — they are three names for the same number. GCD = Greatest Common Divisor (most common in number theory and computer science), HCF = Highest Common Factor (common in UK/Indian school math), and GCF = Greatest Common Factor (common in US school math). All three refer to the largest integer that divides each input evenly.

When you need the largest equal share: simplifying fractions (divide numerator and denominator by their GCD to reach lowest terms), reducing ratios to their simplest form, splitting a quantity into equal groups while respecting multiple constraints, and in cryptography for computing modular inverses with the extended Euclidean algorithm.

When two or more integers share no common prime factor, they are called coprime (or relatively prime) and their GCD is 1. Example: GCD(15, 28) = 1 because 15 = 3 × 5 and 28 = 2² × 7 share no prime.

Yes. Either take the lowest exponent of each shared prime across all inputs, or fold pairwise: GCD(a, b, c) = GCD(GCD(a, b), c). Both methods agree because GCD is associative.

Simplifying fractions, reducing aspect ratios (e.g. 1920 × 1080 → 16:9 because GCD(1920, 1080) = 120), cryptography (RSA key generation, modular arithmetic), signal processing (sampling-rate conversion), and music theory (finding the rhythmic 'pulse' common to several beats).

For any two positive integers, LCM(a, b) × GCD(a, b) = a × b. This means once you know the GCD, the LCM is just (a × b) / GCD. The identity does NOT extend directly to three or more numbers — you have to apply it pairwise.

Related Calculators

More number-theory and fraction tools that pair with GCD work.