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 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!

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.

---

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