GCD Calculator

Enter two or more whole numbers to find their greatest common divisor.

Updated

Enter to calculate Esc to clear

GCD Calculator

Our GCD Calculator finds the greatest common divisor of any list of whole numbers, also known as the greatest common factor (GCF) or highest common factor (HCF). Type or paste the numbers and the GCD appears straight away, with the prime factors of each number, the steps of the Euclidean algorithm and the LCM shown underneath. It is exact for very large numbers too, which makes it handy for simplifying fractions and ratios, cutting things into equal pieces and number theory homework.

Quick answer

The greatest common divisor (GCD) is the largest positive whole number that divides every number in the list exactly. For example, the GCD of 24 and 36 is 12, and the GCD of 48 and 18 is 6. Enter any whole numbers above and the calculator shows the GCD instantly.

  • Euclidean algorithm: GCD(a, b) = GCD(b, a mod b), repeated until the remainder is 0
  • Prime factors: multiply the primes shared by every number, each at its lowest power
  • With the LCM: GCD(a, b) × LCM(a, b) = a × b
  • GCD of 1: the numbers are coprime and share no factor

What Is the GCD?

A divisor (or factor) of a number divides into it with no remainder. A common divisor of several numbers divides into all of them, and the greatest common divisor is the largest one. Every common divisor is a divisor of the GCD, so once you know the GCD you know them all.

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

Common divisors: 1, 2, 3, 4, 6, 12
GCD(24, 36) = 12

The same number goes by several names: greatest common factor (GCF), highest common factor (HCF) and greatest common measure. It is never larger than the smallest number in the list, and it is always at least 1.

How to Find the GCD

1. List the divisors. Write out the divisors of each number and pick the largest one they share, as above. This is quick for small numbers but slow for big ones.

2. Use prime factors. Break each number into primes, then keep only the primes found in every number, each at its lowest power:

24 = 2³ × 3
36 = 2² × 3²
48 = 2⁴ × 3

Shared, lowest powers: 2², 3
GCD = 2² × 3 = 4 × 3 = 12

3. Use the Euclidean algorithm. Divide the larger number by the smaller and keep the remainder. Repeat with the smaller number and the remainder until the remainder is 0. The last divisor is the GCD. This is the method the calculator uses, because it stays fast even for 30-digit numbers.

GCD(1071, 462)
1071 = 2 × 462 + 147
462 = 3 × 147 + 21
147 = 7 × 21 + 0

GCD(1071, 462) = 21

Worked Examples

Two numbers. Find the GCD of 48 and 18 with the Euclidean algorithm:

48 = 2 × 18 + 12
18 = 1 × 12 + 6
12 = 2 × 6 + 0

GCD(48, 18) = 6

Equal pieces. Three ribbons are 60 cm, 90 cm and 150 cm long. To cut them all into equal pieces that are as long as possible, with nothing left over, make each piece GCD(60, 90, 150) = 30 cm. That gives 2 + 3 + 5 = 10 pieces.

Simplifying a fraction. GCD(84, 126) = 42, so 84/126 = 2/3 in one step.

NumbersGCDLCM
24, 361272
48, 186144
8, 9172
17, 511751
84, 12642252
24, 36, 4812144
60, 90, 15030900

GCD and LCM

The least common multiple (LCM) is the smallest number that all the numbers divide into. The GCD uses the lowest power of each shared prime, and the LCM uses the highest power of every prime. For two numbers they are linked by a simple rule:

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

24 = 2³ × 3, 36 = 2² × 3²
GCD = 2² × 3 = 12, LCM = 2³ × 3² = 72
12 × 72 = 864 = 24 × 36

So once you have the GCD, the LCM of two numbers is their product divided by the GCD. The rule only works for two numbers: for 2, 4 and 8 the GCD is 2 and the LCM is 8, so GCD × LCM = 16, while the product is 64.

The GCD and Fractions

A fraction is in its lowest terms when the numerator and the denominator have a GCD of 1. Dividing both by their GCD gets there in one step:

84/126
GCD(84, 126) = 42
= (84 ÷ 42)/(126 ÷ 42) = 2/3

Dividing by a smaller common factor, such as 2 or 6, also works, but you then have to keep going until no common factor is left.

GCD in Excel and Code

ToolGCD of 24, 36 and 48
Excel / Google Sheets=GCD(24, 36, 48)
Excel, a range=GCD(A1:A10)
Python 3.9+math.gcd(24, 36, 48)
JavaScriptb ? gcd(b, a % b) : a

Excel’s GCD returns #NUM! for negative numbers and drops the decimal part of non-whole numbers. Python before 3.9 takes only two numbers at a time. JavaScript has no built-in GCD, so you write the short recursive function shown above.

Common Mistakes

  • Mixing up GCD and LCM. The GCD of 24 and 36 is 12; the LCM is 72.
  • Taking the highest powers. The highest powers give the LCM. The GCD needs the lowest, such as 2² (not 2⁴) for 24, 36 and 48.
  • Keeping a prime that is not shared. A prime must divide every number to count; the 3² in 36 adds only one 3 to GCD(24, 36).
  • Giving 0 as the answer. In the Euclidean algorithm the GCD is the last divisor, not the final remainder of 0.
  • Thinking coprime means prime. 8 and 9 have a GCD of 1, but neither is a prime number.

Key Terms

Divisor
A number that divides into another with no remainder: 6 is a divisor of 24.
Common divisor
A number that divides into every number in the list.
GCD
Greatest common divisor (also GCF or HCF): the largest common divisor.
LCM
Least common multiple: the smallest number every number divides into.
Coprime
Numbers with a GCD of 1, such as 8 and 9.
Prime factors
A number written as a product of primes, such as 36 = 2² × 3².
Euclid
The Euclidean algorithm: find the GCD by repeated division with remainders.

How to Use the GCD Calculator

  1. Enter your numbers. Type two or more whole numbers in the “Numbers” box, separated by spaces or commas, for example 24 36 48. You can enter up to 200 numbers, and you can paste a column straight from a spreadsheet.
  2. Read the GCD. The greatest common divisor appears as you type, with the working underneath (for example GCD(24, 36, 48) = 12). The table below it shows the prime factors of each number, with the shared factors in bold, and the LCM. For two numbers you also see every step of the Euclidean algorithm.
  3. Copy the result. Press Copy to copy the GCD. Press Clear or Esc to start again.

Example: enter 48 18 and the GCD is 6, with the working GCD(48, 18) = 6, the three Euclidean steps, an LCM of 144 and the note that 48/18 simplifies to 8/3.

Who Can Use This Calculator?

Students and TeachersSimplifying fractions and ratios, factor and number theory homework
Cooks and CraftersScaling recipes and cutting material into equal pieces
ProgrammersReducing ratios, aspect ratios and checking coprime keys
Builders and DesignersLargest square tiles or grid size that fits an area exactly

Frequently Asked Questions (FAQs)

What is the greatest common divisor (GCD)?

The GCD of two or more whole numbers is the largest positive number that divides into every one of them exactly. The GCD of 24 and 36 is 12: the divisors of 24 are 1, 2, 3, 4, 6, 8, 12 and 24, the divisors of 36 are 1, 2, 3, 4, 6, 9, 12, 18 and 36, and 12 is the largest number in both lists.

How do you find the GCD of two numbers?

Use the Euclidean algorithm: divide the larger number by the smaller, then replace the pair with the smaller number and the remainder, and repeat until the remainder is 0. The last divisor is the GCD. For 48 and 18: 48 = 2 × 18 + 12, 18 = 1 × 12 + 6, 12 = 2 × 6 + 0, so GCD(48, 18) = 6.

How do you find the GCD of three or more numbers?

Write each number as a product of primes and multiply the primes that appear in every number, each at its lowest power. For 24, 36 and 48: 24 = 23 × 3, 36 = 22 × 32 and 48 = 24 × 3, so the GCD is 22 × 3 = 12. You can also work in pairs: GCD(a, b, c) = GCD(GCD(a, b), c).

Is the GCD the same as the GCF and the HCF?

Yes. Greatest common divisor (GCD), greatest common factor (GCF), highest common factor (HCF) and greatest common measure all mean the same number. GCD is common in the US and in programming, HCF in the UK and India, and GCF in many US school books.

What is the difference between GCD and LCM?

The GCD is the largest number that divides into all the numbers, so it is at most the smallest number. The least common multiple (LCM) is the smallest number that all the numbers divide into, so it is at least the largest number. For 24 and 36 the GCD is 12 and the LCM is 72. For two numbers, GCD × LCM = the product of the numbers (12 × 72 = 864 = 24 × 36).

What does a GCD of 1 mean?

The numbers share no prime factor, so they are called coprime (or relatively prime). 8 and 9 are coprime even though neither is prime. A fraction whose top and bottom are coprime, such as 8/9, is already in its lowest terms.

How is the GCD used to simplify fractions?

Divide the numerator and the denominator by their GCD. The GCD of 84 and 126 is 42, so 84/126 = (84 ÷ 42)/(126 ÷ 42) = 2/3 in one step. The same works for ratios: 24 : 36 simplifies to 2 : 3.

What is the GCD of 0, negative numbers or decimals?

Every number divides 0, so 0 does not change the GCD: GCD(0, 7) = 7. GCD(0, 0) is 0 by convention, as in Excel and Python. Minus signs are ignored, because the GCD is always positive: GCD(−12, 18) = 6. The GCD is defined for whole numbers only. For decimals such as 0.6 and 0.9, multiply by 10 to get 6 and 9, find the GCD (3) and divide by 10 again: 0.3.

Can the GCD be larger than the smallest number?

No. The GCD has to divide into the smallest non-zero number, so it can be at most that number. It equals the smallest number exactly when that number divides all the others: GCD(17, 51) = 17.

Is the GCD Calculator free?

Yes. It is completely free, needs no sign-up, and can be used as many times as you like.

Try our GCD Calculator to find the greatest common divisor of any whole numbers instantly.