GCD Calculator

What is the greatest common factor?

A factor of a number divides it exactly. The greatest common factor of two or more numbers is the largest factor they all have. Take 12 and 18. The factors of 12 are 1, 2, 3, 4, 6, 12. The factors of 18 are 1, 2, 3, 6, 9, 18. Both lists contain 1, 2, 3, 6, and the largest of those is 6, so GCF(12, 18) = 6.

The same number goes by three names. US schools call it the greatest common factor (GCF). The UK, India and Australia say highest common factor (HCF). Higher math and programming languages say greatest common divisor (GCD), as in Python’s math.gcd.

How to find the GCF: four methods

Each method below gives the same answer. The calculator shows all four for your numbers, so you can follow the one your teacher asked for. They are listed here in the same order as the calculator’s method buttons.

List the factors

Write every factor of each number, in pairs from the outside in: for 18, that is 1 × 18, 2 × 9 and 3 × 6. Then circle the factors on every list and take the largest. This is the first method most students learn, and it works well up to about 100. For bigger numbers the lists get long and it is easy to miss one.

List the factors of 12 and 18

Prime factorization

Split each number into primes. Keep only the primes that appear in every number, each at its lowest power, and multiply them. For 48 and 36:

Both numbers have 2 and 3. The lower power of 2 is 2² (from 36) and the lower power of 3 is 3¹ (from 48), so the GCF is 4 × 3 = 12. Taking the higher powers instead, 2⁴ × 3² = 144, gives the least common multiple. The calculator’s prime table puts the two side by side.

Show the prime table for 48 and 36

The ladder method

The ladder (also called the cake or upside-down division method) is prime factorization done on all the numbers at once. Write the numbers in a row. Divide every one of them by a prime that goes into all of them, and write the results underneath. Repeat until no prime goes into every number in the bottom row. The GCF is the product of the primes down the left side.

3 and 5 share no prime, so the ladder stops. GCF(36, 60) = 2 × 2 × 3 = 12. For two numbers, the same ladder also gives the LCM: multiply the left side and the bottom row, 2 × 2 × 3 × 3 × 5 = 180.

Show the ladder for 36 and 60

Euclid’s algorithm

Euclid described this method around 300 BC, in Book VII of the Elements. It needs no factors at all. Divide the larger number by the smaller and keep the remainder. Then divide the old divisor by that remainder, and repeat. When the remainder reaches 0, the last divisor is the GCD. For 1071 and 462:

The remainder is 0 after 3 divisions, so GCD(1071, 462) = 21. It works because any number that divides both a and b also divides the remainder a − q × b, so the pair (b, remainder) has the same GCD as (a, b) but smaller numbers.

Show Euclid’s steps for 1071 and 462

Gabriel Lamé proved in 1844 that the number of divisions is never more than five times the number of digits in the smaller number, so even 40-digit numbers take at most 200 steps. The slowest pairs are consecutive Fibonacci numbers: 89 and 55 take 9 divisions, because every quotient is 1.

Euclid’s algorithm as a picture

Draw a 48 by 18 rectangle and cut off the largest square you can, 18 by 18. Two fit, leaving a 12 by 18 strip. Cut a 12 by 12 square from that, leaving 12 by 6. Two 6 by 6 squares fill it exactly. The side of the last square, 6, is the GCD, and the number of squares at each cut is a quotient in Euclid’s divisions. The calculator draws this rectangle for any two numbers.

Draw the rectangle for 48 and 18

Which method should you use?

GCF of three or more numbers

Work in pairs. Find the GCF of the first two numbers, then the GCF of that answer and the next number, and so on. For 24, 36 and 60, GCF(24, 36) = 12 and GCF(12, 60) = 12. The order does not change the result. With prime factors, a prime counts only if it appears in every number.

Three numbers can have a GCF of 1 even when some pairs share a factor. 6, 10 and 15 have GCF 1, yet 6 and 10 share 2, 6 and 15 share 3, and 10 and 15 share 5. The calculator points this out in its Coprime result.

Check 6, 10 and 15 in the calculator

GCF of common number pairs

These are the pairs that come up most in homework. Each pair opens in the calculator with its steps.

GCF and LCM

The least common multiple (LCM) is the smallest number that all your numbers divide into. For two numbers, the GCF and the LCM are tied by one formula:

So once you have the GCF, the LCM is a × b ÷ GCF. The formula fails for three or more numbers: for 2, 4 and 8 the GCF is 2 and the LCM is 8, and 2 × 8 is not 2 × 4 × 8. Our LCM calculator explains the LCM on its own.

Simplifying fractions and ratios

Dividing the top and bottom of a fraction by their GCF puts it in lowest terms in one step. 48/36 has GCF 12, so 48/36 = 4/3. Ratios work the same way. A 1920 × 1080 screen has GCF 120, and 1920 ÷ 120 = 16 and 1080 ÷ 120 = 9, which is why it is called 16:9. The calculator’s “Divided by the GCD” result gives this lowest-terms ratio for any set of numbers.

Reduce 1920 × 1080 to 16:9

GCF word problems

A word problem needs the GCF when you split things into the largest possible equal groups, with nothing left over. If it asks when two things will line up again, it needs the LCM instead.

Gift bags

You have 24 pencils and 36 erasers and want identical gift bags with nothing left over. What is the largest number of bags? The number of bags must divide both 24 and 36, so it is GCF(24, 36) = 12. Each bag gets 24 ÷ 12 = 2 pencils and 36 ÷ 12 = 3 erasers.

Check the gift bags in the calculator

Square tiles

A floor is 360 cm by 270 cm. What is the largest square tile that covers it with no cutting? The tile’s side must divide both lengths, so it is GCF(360, 270) = 90 cm. That takes 4 × 3 = 12 tiles.

Draw the 360 by 270 floor

Teams

A class of 18 boys and 24 girls splits into teams, each with the same mix of boys and girls. The most teams possible is GCF(18, 24) = 6, each with 3 boys and 4 girls.

Coprime numbers

Numbers whose GCF is 1 are called coprime, or relatively prime. They do not have to be prime themselves: 8 and 15 are coprime, and so are 35 and 64. Two numbers next to each other, such as 20 and 21, are always coprime. A prime is coprime with every number it does not divide. Two even numbers are never coprime, because both have the factor 2.

Check 35 and 64 in the calculator

The extended Euclidean algorithm and Bézout’s identity

Bézout’s identity says that for any whole numbers a and b there are whole numbers x and y with a·x + b·y = GCD(a, b). The extended Euclidean algorithm finds them. It runs Euclid’s divisions and keeps two extra columns, s and t, so that each remainder r = s·a + t·b. Each new row is the row two up minus the quotient times the row above. For 240 and 46 the last row before the remainder 0 gives:

Show the extended table for 240 and 46

When the GCD is 1, the identity gives a modular inverse: a number that undoes multiplication modulo b. For 17 and 3120, the inverse of 17 is 2753, because 17 × 2753 = 46,801, which is 15 × 3120 + 1. RSA encryption finds its private key this way, and programs use the same step to divide in modular arithmetic. If you work with remainders, our modulo calculator shows each one on a number line.

Find the inverse of 17 mod 3120

Zero and negative numbers

Every number divides 0, so GCD(a, 0) = a for any a that is not 0. GCD(0, 0) has no greatest divisor; some programming languages return 0 for it by convention, and the calculator asks for at least one number that is not 0. Signs do not matter either. The GCD is always positive, so GCD(−12, 18) = GCD(12, 18) = 6.