Greatest Common Factor Calculator

What is the Greatest Common Factor (GCF)?

The greatest common factor of a set of whole numbers is the largest number that divides every one of them without leaving a remainder. Textbooks also call it the greatest common divisor (GCD) or highest common factor (HCF); all three names describe the same value. For two numbers a and b it is written GCF(a, b).

Take 48 and 72. Their shared divisors are 1, 2, 3, 4, 6, 8, 12, and 24, so the biggest one — and therefore the GCF — is 24. Every pair of whole numbers has at least one common factor, since 1 divides everything. When 1 is the only shared factor, the numbers are called coprime.

One shortcut is worth remembering: if the smaller number divides the larger one exactly, the smaller number is the GCF. That is why GCF(9, 63) is 9 without any factoring at all.

Prime Factorization Method

To use this method, break each number down into primes, then look for primes that appear in every list. Where a prime shows up more than once, use the lowest power it reaches in any of the numbers. Multiplying those shared primes gives the GCF.

Worked example: GCF(24, 36, 60)

24 = 2 × 2 × 2 × 3
36 = 2 × 2 × 3 × 3
60 = 2 × 2 × 3 × 5
Every list contains 2 × 2 × 3, so GCF(24, 36, 60) = 12.

The method is easy to follow and shows exactly why the answer is what it is, but it becomes slow once the numbers are large. Factoring a number with two big prime factors, for instance, can take far longer than the division method described below.

Euclidean Algorithm

The Euclidean algorithm reaches the same answer with repeated division instead of factoring. It rests on one fact: any common divisor of two numbers also divides the remainder left when the larger is divided by the smaller. That means the problem can be shrunk without changing its answer.

In practice:

1. Divide the larger number by the smaller one and note the remainder.
2. Replace the larger number with the smaller one, and the smaller one with the remainder.
3. Repeat until the remainder is zero.
4. The last non-zero remainder — the divisor in that final step — is the GCF.

Worked example: GCF(1071, 462)

1071 ÷ 462 = 2 remainder 147
462 ÷ 147 = 3 remainder 21
147 ÷ 21 = 7 remainder 0
The last divisor is 21, so GCF(1071, 462) = 21.

For three or more numbers, apply the algorithm pairwise: find the GCF of the first two, then the GCF of that result and the third number, and continue. For example, GCF(84, 126) = 42, and GCF(42, 210) = 42, so GCF(84, 126, 210) = 42.

The division version above is much faster than the older subtraction variant, which repeatedly takes one number away from the other until the two match. Both are correct, but subtraction can need thousands of steps where division needs a handful.

How to Use the GCF Calculator

Using the GCF calculator is straightforward. Simply enter your numbers separated by commas in the input field above, then click the Calculate button. The calculator will instantly compute the greatest common factor and display step-by-step prime factorizations for each number.

For example, if you enter "12, 18, 24", the calculator will show the prime factorization of each number: 12 = 2 × 2 × 3, 18 = 2 × 3 × 3, and 24 = 2 × 2 × 2 × 3. It will then identify the common prime factors (2 and 3) and multiply them to give the GCF of 6. You can also use our prime factorization calculator to break down individual numbers.

The calculator accepts any number of positive integers. You can separate them with commas, spaces, or both. The clear button resets the input to the default example values. The print button lets you save or print the results along with the step-by-step breakdown for your records or homework.

This GCF calculator is particularly useful for students learning about factors and divisibility, teachers preparing examples for their classes, and professionals who need to compute GCFs quickly without manual calculation.

GCF vs LCM - Key Differences and Relationship

The greatest common factor (GCF) and the least common multiple (LCM) are two fundamental concepts in number theory that are closely related. While the GCF finds the largest number that divides all given numbers, the LCM finds the smallest number that is a multiple of all given numbers. Use our LCM calculator to compute the least common multiple.

For example, consider the numbers 6 and 10. The GCF of 6 and 10 is 2 (the largest number that divides both evenly). The LCM of 6 and 10 is 30 (the smallest number that both 6 and 10 divide evenly). Notice that 6 × 10 = 60, and GCF(6,10) × LCM(6,10) = 2 × 30 = 60. This demonstrates the fundamental relationship: for any two numbers a and b, GCF(a,b) × LCM(a,b) = a × b.

This relationship means you can calculate the LCM by dividing the product of the numbers by their GCF. So LCM(6,10) = (6 × 10) / GCF(6,10) = 60 / 2 = 30. This is often the most efficient way to compute the LCM, especially for larger numbers.

Understanding both GCF and LCM is essential for working with fractions. The GCF helps you simplify fractions to their lowest terms, while the LCM helps you find a common denominator when adding or subtracting fractions with different denominators.

Real-World Applications of GCF

The greatest common factor has numerous practical applications in everyday life. In cooking and baking, you use GCF to scale recipes. If a recipe calls for 8 cups of flour and 12 cups of sugar, the GCF of 8 and 12 is 4, so you know the recipe can be scaled in increments of 4 servings. When working with recipes, you can also use our fraction calculator to handle ingredient measurements.

In construction and woodworking, GCF helps with measuring and cutting materials evenly. If you have boards of lengths 24 feet and 36 feet and want to cut them into equal pieces of the maximum possible length, you would cut them into pieces of GCF(24, 36) = 12 feet each.

In education, GCF is used when grouping students. If you have 24 boys and 36 girls and want to form mixed groups with the same number of boys and girls in each group, the GCF of 24 and 36 is 12, so you can form 12 groups with 2 boys and 3 girls each.

In computer science, the Euclidean algorithm for computing GCF is used in cryptography, particularly in the RSA encryption algorithm. It is also used in digital signal processing and for reducing fractions in computer algebra systems.

Common Mistakes When Finding GCF

One of the most common mistakes when finding the GCF is confusing it with the LCM. Remember that the GCF is the largest number that divides evenly into all given numbers, while the LCM is the smallest number that all given numbers divide into evenly. A helpful way to remember: GCF produces a result smaller than or equal to the inputs, while LCM produces a result larger than or equal to the inputs. If you need the LCM instead, use our LCM calculator.

Another frequent error is forgetting to include all common factors. When using prime factorization, make sure you only multiply the factors that appear in ALL numbers, not just some of them. If a prime factor appears in two out of three numbers but not the third, it is not a common factor and should not be included in the GCF.

Students also commonly forget that 1 is always a factor of every number. Two numbers that share no common prime factors will have a GCF of 1. These numbers are called coprime or relatively prime. For example, GCF(14, 15) = 1 because 14 = 2 × 7 and 15 = 3 × 5 share no common prime factors.

When using the Euclidean algorithm, a common mistake is stopping too early. The algorithm must continue until the remainder is exactly zero. The GCF is the last non-zero remainder, not the final remainder of zero. Pay careful attention to the subtraction or division steps.

Tips and Tricks for GCF Calculations

When finding the GCF of two numbers, start by checking if the smaller number divides the larger one evenly. If it does, then the smaller number is the GCF. For example, GCF(12, 24) = 12 because 12 divides 24 evenly. This simple check can save time on many problems.

The Euclidean algorithm using division is generally faster than the subtraction version, especially for large numbers. Instead of repeatedly subtracting, use the modulo operation: GCF(a, b) = GCF(b, a % b). This eliminates multiple subtraction steps in one operation.

For small numbers (under 100), memorizing multiplication tables and recognizing factors quickly can speed up GCF calculations significantly. Numbers that end in 0, 2, 4, 6, or 8 have 2 as a factor. Numbers ending in 0 or 5 have 5 as a factor. A number is divisible by 3 if the sum of its digits is divisible by 3.

You can verify your GCF by checking that it divides evenly into each of the original numbers. Also check that if you divide each original number by the GCF, the resulting numbers are coprime (their GCF is 1). This two-step verification ensures you have found the correct greatest common factor. For more advanced calculations involving powers, try our exponent calculator.

Prime Numbers and Composite Numbers

Prime numbers are the building blocks of all positive integers. A prime number is a positive integer greater than 1 that has exactly two factors: 1 and itself. The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, and 31. Note that 2 is the only even prime number.

Composite numbers are positive integers greater than 1 that are not prime. They have more than two factors. For example, 4 (factors: 1, 2, 4), 6 (factors: 1, 2, 3, 6), and 15 (factors: 1, 3, 5, 15) are composite numbers. The number 1 is neither prime nor composite.

The Fundamental Theorem of Arithmetic states that every positive integer can be expressed uniquely as a product of prime numbers (ignoring order). This is why prime factorization is so important for finding the GCF. When you break numbers down into their prime factors, you can easily identify the common factors. Try our prime factorization calculator to see the prime factors of any number.

Understanding the difference between prime and composite numbers is essential for GCF calculations because the GCF of two prime numbers is always 1 (unless they are the same number, in which case the GCF is the number itself). For example, GCF(7, 11) = 1, while GCF(7, 7) = 7.

GCF of Three or More Numbers

Finding the GCF of three or more numbers follows the same principles as finding it for two numbers, with the additional requirement that the common factor must divide every single number in the set. This makes the GCF of multiple numbers typically smaller than the GCF of any subset.

The most reliable method is to use prime factorization for all numbers and identify only the prime factors that appear in every factorization. For example, to find GCF(48, 72, 120): 48 = 2⁴ × 3, 72 = 2³ × 3², 120 = 2³ × 3 × 5. The common factors are 2³ and 3, so GCF = 2³ × 3 = 8 × 3 = 24.

Another approach is the pairwise method: find the GCF of the first two numbers, then find the GCF of that result with the third number, and so on. For our example: GCF(48, 72) = 24, then GCF(24, 120) = 24. So GCF(48, 72, 120) = 24. This method can be more efficient when using the Euclidean algorithm.

A common real-world application involves finding the largest group size that can evenly divide multiple quantities. If you have 48 apples, 72 oranges, and 120 bananas, the GCF of 24 tells you that you can create 24 identical fruit baskets, each containing 2 apples, 3 oranges, and 5 bananas.

Practice Problems with GCF

Practice is essential for mastering GCF calculations. Here are some problems to try. Use the GCF calculator above to check your answers and see the step-by-step prime factorization. You can also use our factor calculator to find all factors of any number.

Problem 1: Find GCF(36, 48). (Answer: 12, since 36 = 2² × 3² and 48 = 2⁴ × 3; common factors are 2² × 3 = 12)

Problem 2: Find GCF(84, 126). (Answer: 42, since 84 = 2² × 3 × 7 and 126 = 2 × 3² × 7; common factors are 2 × 3 × 7 = 42)

Problem 3: Find GCF(100, 75). (Answer: 25, since 100 = 2² × 5² and 75 = 3 × 5²; common factor is 5² = 25)

Problem 4: Find GCF(17, 19). (Answer: 1, since both are prime numbers and different, they are coprime)

Problem 5: Find GCF(64, 128, 256). (Answer: 64, since each number is a power of 2: 64 = 2⁶, 128 = 2⁷, 256 = 2⁸)

Problem 6: Find GCF(45, 60, 75). (Answer: 15, since 45 = 3² × 5, 60 = 2² × 3 × 5, 75 = 3 × 5²; common factors are 3 × 5 = 15)

Problem 7: Find GCF(144, 96). Use the Euclidean algorithm. (Answer: 48, since 144 ÷ 96 = 1 remainder 48, then 96 ÷ 48 = 2 remainder 0, so GCF = 48)

Try entering these numbers into the GCF calculator to verify your answers and see the complete prime factorization for each set of numbers.

History of the Greatest Common Factor

The concept of the greatest common factor has been studied since ancient times. The Euclidean algorithm, named after the Greek mathematician Euclid (circa 300 BCE), is one of the oldest algorithms still in use today. Euclid described the algorithm in his seminal work Elements, specifically in Book VII, which covers number theory.

The Euclidean algorithm was revolutionary because it provided a systematic method for finding the GCF without requiring prime factorization. This was particularly important because the ancient Greeks did not have our modern notation for prime factorization and relied on geometric methods for many mathematical operations.

Over the centuries, mathematicians refined and extended the concept. In the 17th century, Pierre de Fermat and Marin Mersenne studied properties of prime numbers and factorization. In the 18th century, Leonhard Euler and Carl Friedrich Gauss made significant contributions to number theory, including the Fundamental Theorem of Arithmetic, which formalized the role of prime factorization.

Today, the Euclidean algorithm is a fundamental tool in computer science and cryptography. The RSA encryption algorithm, which secures much of the internet, relies on the difficulty of factoring large numbers while using the Euclidean algorithm for key generation. This ancient mathematical concept continues to play a vital role in modern technology.