GCD Calculator — Greatest Common Divisor

How to Find the Greatest Common Divisor

The greatest common divisor (GCD) of a set of numbers is the largest number that divides evenly into all numbers in the set. The greatest common divisor is sometimes referred to as the greatest common factor (GCF), highest common factor (HCF), greatest common denominator, or highest common divisor.

A factor (or divisor) of a number x is any whole number that can be multiplied by another whole number to produce x. For example, 3 and 5 are both factors of 15, because 3 × 5 = 15.

There are three standard methods to find the GCD: using prime factorization, listing all factors, or Euclid's algorithm. Our calculator above uses all three and shows the complete step-by-step solution. Read on to learn each method with a worked example.

Method One: Find GCD Using Prime Factorization

The prime factorization method works by decomposing each number into its prime factors — the building blocks that are themselves only divisible by 1 and themselves. Once you have the prime factors for every number in the set, you identify the primes that are common to all numbers and multiply them together to get the GCD.

A prime number is a number greater than 1 that has no divisors other than 1 and itself. The first several primes are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29…

Example: Find the GCD of 90 and 165 using prime factorization.

Step 1 — Find the prime factors of 90:

• 90 ÷ 2 = 45 → 2 is a prime factor
• 45 ÷ 3 = 15 → 3 is a prime factor
• 15 ÷ 3 = 5 → 3 is a prime factor (again)
• 5 ÷ 5 = 1 → 5 is a prime factor

Prime factors of 90 = 2 × 3 × 3 × 5 (or 2 × 3² × 5)

Step 2 — Find the prime factors of 165:

• 165 ÷ 3 = 55 → 3 is a prime factor
• 55 ÷ 5 = 11 → 5 is a prime factor
• 11 ÷ 11 = 1 → 11 is a prime factor

Prime factors of 165 = 3 × 5 × 11

Step 3 — Find the common prime factors:

Both 90 and 165 share the prime factors 3 and 5.

Step 4 — Multiply the common prime factors:

GCD = 3 × 5 = 15

Method Two: Find GCD by Listing All Factors

This method involves finding every factor of each number, identifying which factors are common to all numbers, and then selecting the largest one. It is straightforward and easy to understand, though it becomes impractical for very large numbers.

Example: Find the GCD of 90 and 165 by listing all factors.

Step 1 — List all factors of 90:

Check every integer from 1 up to 90 that divides 90 evenly:

Factors of 90 = {1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90}

Step 2 — List all factors of 165:

Factors of 165 = {1, 3, 5, 11, 15, 33, 55, 165}

Step 3 — Find the common factors:

Numbers that appear in both factor lists:

Common factors = {1, 3, 5, 15}

Step 4 — Select the greatest common factor:

The largest number in the set of common factors is 15.

Method Three: Find GCD Using Euclid's Algorithm

Euclid's algorithm is the most efficient method for finding the GCD of two numbers. Invented by the Greek mathematician Euclid around 300 BCE, it is one of the oldest algorithms still in everyday use. The method works by repeatedly dividing and taking remainders until the remainder reaches zero.

The algorithm:

1. Divide the larger number by the smaller number. Note the remainder.
2. If the remainder is 0, the divisor in this step is the GCD. Stop here.
3. If the remainder is not 0, replace the larger number with the previous divisor, and the smaller number with the remainder. Go back to step 1.

Example: Find the GCD of 90 and 165 using Euclid's algorithm.

• Step 1: 165 ÷ 90 = 1 remainder 75
• Step 2: 90 ÷ 75 = 1 remainder 15
• Step 3: 75 ÷ 15 = 5 remainder 0

The remainder is 0, so the divisor in this final step — 15 — is the GCD.

The Relationship Between GCD and LCM

The GCD and LCM (Least Common Multiple) are deeply connected by a simple formula:

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

This means once you know the GCD, you can instantly calculate the LCM:

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

For example: GCD(90, 165) = 15, so LCM(90, 165) = (90 × 165) / 15 = 14,850 / 15 = 990.

The LCM is essential when you need to add or subtract fractions with different denominators — the LCD (Least Common Denominator) is simply the LCM of the denominators.

Frequently Asked Questions

What is the difference between GCD, GCF, and HCF?

They are all different names for the same concept — the largest number that divides two or more numbers without a remainder. GCD (Greatest Common Divisor) is the term most commonly used in university-level mathematics and computer science. GCF (Greatest Common Factor) is the preferred term in American K-12 education. HCF (Highest Common Factor) is widely used in British, Indian, and Australian math education. All three terms are interchangeable.

How do I find the GCD of more than two numbers?

Apply the GCD function iteratively. First find the GCD of the first two numbers, then find the GCD of that result with the third number, and continue until all numbers have been processed. For example:

GCD(12, 18, 24) = GCD(GCD(12, 18), 24) = GCD(6, 24) = 6

Our calculator above handles any number of inputs — just enter them separated by commas.

What is the greatest common divisor used for?

The GCD has many practical applications:

• Simplifying fractions: Divide both numerator and denominator by their GCD. For example, 48/36 → divide both by GCD(48,36) = 12 → simplified to 4/3. Use our Fraction Calculator to simplify fractions automatically.
• Finding the LCM: LCM(a,b) = (a × b) / GCD(a,b). The LCM Calculator uses this relationship.
• Tiling problems: The largest square tile that fits perfectly into a rectangular room of dimensions a × b (with no cutting) has a side length equal to GCD(a, b).
• Gear ratios: In mechanical engineering, the GCD determines the simplest gear ratio between two gears.
• Cryptography: RSA encryption — the foundation of internet security — relies heavily on GCD computations and Euclid's extended algorithm.

Can the GCD ever be 1?

Yes. When the GCD of two numbers is 1, the numbers are called coprime (or relatively prime). This means they share no common factors other than 1. Examples: GCD(8, 15) = 1, GCD(7, 13) = 1, GCD(25, 36) = 1. Two consecutive integers are always coprime.

Is there a GCD function on scientific calculators?

Many scientific calculators have a built-in GCD or "gcd" function. On the TI-84, use math → NUM → gcd(. On Casio calculators, the function is often under the MATH menu. Online tools like our GCD Calculator above provide step-by-step solutions that physical calculators typically do not show.