CalcUnit Logo
Math

Mastering Fractions: How to Find the Greatest Common Divisor (GCD)

Learn the mathematical strategies used to simplify massive fractions. We explain the Prime Factorization method and the 2,000-year-old Euclidean Algorithm.

CEBy CalcUnit Math ExpertsPublished 8 min read
Mastering Fractions: How to Find the Greatest Common Divisor (GCD)

Instantly simplify massive numbers using our GCD Calculator, or read on to learn the historical algorithms used to solve complex fraction problems.

If a math test asks you to simplify the fraction 48/180, you know you need to divide the top and the bottom by the same number. You might start by dividing by 2 to get 24/90, and then divide by 2 again to get 12/45, and then divide by 3 to get 4/15.

This guess-and-check method works, but it is incredibly slow. The mathematically elegant way to simplify a fraction in a single step is to find the Greatest Common Divisor (GCD)—the largest single number that divides perfectly into both 48 and 180.

There are two primary methods to find the GCD: Prime Factorization, and the Euclidean Algorithm.

Method 0: Listing All Factors (For Small Numbers)

Before the two classic methods, there is a humble third one that is fastest of all when the numbers are small: just list every factor of each number and find the largest match.

Find the GCD of 24 and 36.

  • Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24
  • Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36

The shared factors are 1, 2, 3, 4, 6, and 12. The greatest of them is 12.

Listing works beautifully up to about 50. Beyond that, the lists grow long and one missed factor ruins the answer — which is why the real methods exist.

Run your own numbers

Enter your own numbers and see the result instantly — free, no signup.

Open the Calculator →

Method 1: Prime Factorization

This method breaks both numbers down into their fundamental building blocks: prime numbers (numbers that can only be divided by 1 and themselves, like 2, 3, 5, 7).

Let's find the GCD of 48 and 180.

Step 1: Find the prime factors of the first number.

  • 48 = 2 × 24
  • 24 = 2 × 12
  • 12 = 2 × 6
  • 6 = 2 × 3 Prime factors of 48: 2, 2, 2, 2, 3

Step 2: Find the prime factors of the second number.

  • 180 = 2 × 90
  • 90 = 2 × 45
  • 45 = 3 × 15
  • 15 = 3 × 5 Prime factors of 180: 2, 2, 3, 3, 5

Step 3: Multiply the shared factors. Look at the two lists. What numbers do they both share? They both share two 2s and one 3. Multiply the shared numbers together: 2 × 2 × 3 = 12.

The Greatest Common Divisor is 12. (Divide the top and bottom of 48/180 by 12, and you instantly get the simplified fraction 4/15).

Method 2: The Euclidean Algorithm

Prime factorization works great for small numbers, but what if you need to find the GCD of massive numbers, like 1071 and 462? Finding prime factors would take hours.

Over 2,300 years ago, the Greek mathematician Euclid invented a brilliant, lightning-fast algorithm based on division and remainders.

The Rule: The GCD of two numbers also divides their remainder.

Let's find the GCD of 1071 and 462.

  1. Divide the larger number by the smaller number. 1071 ÷ 462 = 2 with a remainder of 147.
  2. Shift the numbers. Take the old smaller number (462) and divide it by the remainder (147). 462 ÷ 147 = 3 with a remainder of 21.
  3. Shift the numbers again. Take the old smaller number (147) and divide it by the new remainder (21). 147 ÷ 21 = 7 with a remainder of 0.

When the remainder hits exactly zero, the algorithm stops. The final divisor you used (21) is your Greatest Common Divisor!

Why the Euclidean Algorithm Works

The logic is one clean idea: any number that divides both a and b must also divide their difference — and therefore must divide the remainder when a is divided by b.

So the GCD of 1071 and 462 equals the GCD of 462 and 147. Nothing is lost at each step, yet the numbers shrink dramatically.

Because the remainder is always smaller than the divisor, the pairs collapse toward zero fast. Even enormous inputs finish in a surprisingly small number of steps, which is why computers still use Euclid's method today.

Finding the GCD of Three or More Numbers

Real problems rarely stop at two numbers. The fix is simple: apply the method in a chain, two numbers at a time.

Find the GCD of 24, 36, and 60.

  1. First pair: GCD(24, 36) = 12
  2. Chain the result: GCD(12, 60) = 12

The GCD of all three numbers is 12. The order does not matter — start with whichever pair looks easiest, then fold in the next number.

This chaining trick works for any count of numbers and for all three methods, not just Euclid's.

GCD in the Real World: The Tiling Problem

GCD is not just a fractions tool. It answers a classic practical question: what is the largest square tile that fits a rectangle with no cutting?

Suppose a floor measures 168 inches by 120 inches. The tile size must divide both dimensions exactly.

Factor them: 168 = 2³ × 3 × 7 and 120 = 2³ × 3 × 5. The shared factors give GCD = 2³ × 3 = 24.

So 24-inch square tiles fit perfectly: 168 ÷ 24 = 7 tiles along one side and 120 ÷ 24 = 5 along the other, for 7 × 5 = 35 tiles and zero waste cuts.

The same logic sizes photo prints, cuts fabric into equal strips, and splits a class into the largest possible equal groups. In fact, any problem asking for the "largest equal size" — the biggest square, the longest equal pieces, the largest fair group — is secretly asking for a GCD.

GCD and LCM: Two Sides of One Coin

The GCD has a partner: the Least Common Multiple (LCM), the smallest number that both numbers divide into. For any two positive numbers, they obey one elegant rule:

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

Check it with 12 and 18. Their GCD is 6 and their LCM is 36, and indeed 6 × 36 = 216 = 12 × 18.

This means if you can find one, you get the other by division: LCM = (a × b) ÷ GCD. Our LCM Calculator uses exactly this relationship.

The LCM earns its keep when adding fractions: 1/12 + 1/18 needs the common denominator 36, giving 3/36 + 2/36 = 5/36.

Which Method Should You Choose?

Each method has a home ground. Matching the tool to the numbers saves real effort.

  • Listing factors: best for small numbers you can factor at a glance, and for teaching what a common divisor actually is. It fails quietly when a factor is easy to overlook.
  • Prime factorization: best when the numbers factor easily, or when you also need the LCM or other factor information. It becomes painful for large numbers with big prime factors.
  • Euclidean algorithm: best for everything else — especially large, awkward numbers. It never requires factoring anything, only division with remainders.

A reliable habit: first check whether the smaller number divides the larger one. If it does, you are done in seconds, and no method was needed at all.

Special Cases Worth Knowing

  • One number divides the other. GCD(12, 36) is simply 12 — the smaller number itself. Always test this first; it ends the problem instantly.
  • Coprime numbers. If two numbers share no factors beyond 1, like 8 and 15, their GCD is 1 and they are called coprime or relatively prime. A fraction like 8/15 is already in lowest terms.
  • Zero. GCD(a, 0) equals a, since every number divides 0. This is the rule that formally ends the Euclidean algorithm.
  • Negative numbers. GCD ignores signs. GCD(−24, 36) is 12, computed from the absolute values.

FAQ

What is the difference between GCD and GCF? There is no mathematical difference! Greatest Common Divisor (GCD) and Greatest Common Factor (GCF) mean the exact same thing. Some textbooks use "Factor" and others use "Divisor," but the calculation is identical.

What is the GCD of two different prime numbers? It is always 1. A prime has no factors besides 1 and itself, and two different primes share nothing else. The only exception is the same prime twice: GCD(7, 7) is 7.

How is GCD different from just "simplifying until it looks done"? Guess-and-check simplification can stop too early — 24/90 looks plausible until you notice both still divide by 6. Dividing by the GCD once guarantees the fraction is fully reduced, with nothing left to find.

Where else does GCD show up? Beyond fractions and tiling, GCD sits inside gear-ratio design, music rhythm patterns, and the RSA cryptography concept of coprime numbers. It is one of the oldest algorithms still in daily use.


Don't waste time doing repetitive prime factorization by hand. Let the CalcUnit GCD Calculator run the Euclidean algorithm for you instantly.

NameMastering Fractions: How to Find the Greatest Common Divisor (GCD)
DescriptionLearn the mathematical strategies used to simplify massive fractions. We explain the Prime Factorization method and the 2,000-year-old Euclidean Algorithm.
PublishedJune 12, 2026 · CalcUnit Math Experts
Filed undermath · gcd calculator

Keep Reading

Decoding Antiquity: How to Read Roman Numerals
Math

Decoding Antiquity: How to Read Roman Numerals

Struggling to read the copyright date on a movie or the number of a Super Bowl? Learn the seven symbols and the subtractive rules of Roman Numerals.

Jun 12, 2026CalcUnit History Experts