GCD Calculator

The Biggest Number That Fits Into Both, Evenly

The greatest common divisor (GCD) — also called the highest common factor (HCF) — of two numbers is the largest number that divides into both of them without leaving a remainder. For 12 and 18, several numbers divide both (1, 2, 3, 6), but 6 is the biggest one, so GCD(12, 18) = 6.

It sounds like a small, self-contained idea, but the GCD is quietly load-bearing across a surprising amount of math and computing. It's what makes fraction simplification possible, it underpins parts of modern cryptography, and it's one of the oldest algorithms still taught and used almost unchanged after more than two thousand years.

At a glance:
• The GCD of two numbers is always a divisor of both
• GCD(a, 0) = a for any number a
• If the GCD of two numbers is 1, they're called "coprime" or "relatively prime"
• The fastest reliable way to find it is the Euclidean algorithm, not listing every factor

GCD Calculator

Euclidean Algorithm Steps

Tiling Visualization

The Euclidean Algorithm, Explained

Why It Works

Any number that divides both a and b evenly must also divide their difference evenly. Since "a mod b" is really just the remainder left after repeatedly subtracting b from a, that remainder shares the exact same set of common divisors as the original pair. So the problem keeps shrinking to a smaller, equivalent one, until it collapses down to the answer.

Worked Example

Given: a = 48, b = 18

Step 1: 48 mod 18 = 12 (since 48 = 2 × 18 + 12) → now find GCD(18, 12)
Step 2: 18 mod 12 = 6 (since 18 = 1 × 12 + 6) → now find GCD(12, 6)
Step 3: 12 mod 6 = 0 (since 12 = 2 × 6 + 0) → the second number hit zero
Result: the last nonzero remainder was 6, so GCD(48, 18) = 6

Other Ways to Find the GCD

Listing factors: Write out every divisor of each number and pick the largest one they share. Reliable for small numbers, but painfully slow once numbers get into the hundreds or thousands.

Prime factorization: Break both numbers down into prime factors, then multiply together the primes they have in common, using the lowest power that appears in either factorization.

Euclidean algorithm: Repeated division with remainders, as shown above. This is what calculators and computers actually use, since it stays fast even for enormous numbers.

Reference Table

Where the GCD Actually Gets Used

Simplifying Fractions: Reducing a fraction to lowest terms means dividing the numerator and denominator by their GCD — it's the single most common practical use of this calculation.

Cryptography: Public-key systems like RSA rely heavily on numbers being coprime (having a GCD of 1), and the Euclidean algorithm is used directly inside key-generation steps to verify that relationship and compute modular inverses.

Scheduling & Timing Problems: If two repeating events need to be spaced or synchronized (like two gears turning at different rates, or two lights blinking at different intervals), the GCD and its close relative, the LCM, determine how the patterns align over time.

Tiling & Layout Design: When dividing a rectangular space into the largest possible identical square tiles with no leftover space, the tile size is exactly the GCD of the rectangle's width and height — the same tiling picture shown in the calculator above.

Music Theory: Polyrhythms, where two different rhythmic groupings play simultaneously (like 3 against 4), rely on the GCD and LCM to determine how many beats pass before both patterns realign.

Computer Science: Beyond cryptography, the GCD shows up in algorithms for simplifying ratios, reducing aspect ratios for screens and images, and in various number-theoretic subroutines used across software.

Tips for Working With GCDs

✓ You don't need factor lists for big numbers: The Euclidean algorithm finds the GCD of even huge numbers in a handful of steps, while factoring them first would be far slower.

✓ GCD(a, 1) is always 1: Since 1 divides every integer, no number can share a larger common factor with 1.

✓ GCD and LCM are linked: For any two positive integers, GCD(a, b) × LCM(a, b) = a × b — handy for finding one when you already know the other.

✓ Coprime doesn't mean prime: 8 and 15 are coprime (GCD = 1) even though neither number is itself prime — coprime just means they share no common factors at all.

✓ Order doesn't matter: GCD(a, b) always equals GCD(b, a) — the algorithm sorts itself out automatically after the first step regardless of which number you enter first.

✓ Works for more than two numbers: To find the GCD of three or more numbers, find the GCD of the first two, then find the GCD of that result with the next number, and so on.

One of the Oldest Algorithms Still in Daily Use

Named After Euclid, But Possibly Older: The algorithm is described in Euclid's "Elements," written around 300 BCE, making it one of the earliest algorithms ever recorded in detail. Some historians believe the method may have been known even earlier, possibly originating with the mathematician Eudoxus.

A Rare Case of "Solved and Done": Unlike most areas of mathematics that get revised and reframed over centuries, the Euclidean algorithm has needed essentially no correction since it was first written down — it remains provably optimal for what it does.

Donald Knuth Called It "the Granddaddy": In his influential book "The Art of Computer Programming," Knuth referred to the Euclidean algorithm as the oldest nontrivial algorithm to have survived to the present day, and used it to illustrate core ideas in the analysis of algorithm efficiency.

Still Foundational in Modern Computing: Extended versions of the algorithm are baked directly into cryptographic libraries used today, meaning a 2,300-year-old technique is quietly running every time you load a secure website.

Frequently Asked Questions