GCF Calculator – Greatest Common Factor

The GCF calculator evaluates the Greatest Common Factor between two up to fifteen different numbers. Read on to find the answer to the question: "What is the Greatest Common Factor of given numbers?", learn about several GCF finder methods, including prime factorization or the Euclidean algorithm, decide which is your favorite, and check out by yourself that our GCF calculator can save you time when dealing with big numbers!

The greatest common factor definition is the largest integer factor that is present between a set of numbers. It is also known as the Greatest Common Divisor, Greatest Common Denominator (GCD), Highest Common Factor (HCF), or Highest Common Divisor (HCD). This is important in certain applications of mathematics such as simplifying polynomials where often it's essential to pull out common factors. Next, we need to know how to find the GCF.

There are various methods that help you to find GCF. Some of them are child's play, while others are more complex. It's worth knowing all of them so you can decide which you prefer:

• Using the list of factors;
• Prime factorization of numbers;
• Euclidean algorithm;
• Binary algorithm (Stein's algorithm); and
• Using multiple properties of GCF (including Least Common Multiple, LCM).

The good news is that you can estimate the GCD with simple math operations without roots or logarithms! In most cases, they are just subtraction, multiplication, or division.

The primary method used to estimate the greatest common divisor is to find all of the factors of the given numbers. Factors are merely numbers that are multiplied together to result in the original value. In general, they can be both positive and negative, e.g., 2 × 3 is the same as (-2) × (-3), both equal 6. From a practical point of view, we consider only positive ones. Moreover, only integers are concerned. Otherwise, you could find an infinite combination of distinct fractions being factors, which is pointless in our case. Knowing that, let's estimate the greatest common denominator of numbers 72 and 40.

1. Factors of 72 are: 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72.
2. Factors of 40 are: 1, 2, 4, 5, 8, 10, 20, 40.
3. List all the common factors: 1, 2, 4, 8.
4. The Greatest Common Divisor is 8, the highest value from above.

Let's try something more challenging. We want to find the answer to a question: "What is the greatest common factor of 33,264 and 35,640?" All we need to do is repeat the previous steps:

1. Factors of 33,264 are: 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 16, 18, 21, 22, 24, 27, 28, 33, 36, 42, 44, 48, 54, 56, 63, 66, 72, 77, 84, 88, 99, 108, 112, 126, 132, 144, 154, 168, 176, 189, 198, 216, 231, 252, 264, 297, 308, 336, 378, 396, 432, 462, 504, 528, 594, 616, 693, 756, 792, 924, 1008, 1188, 1232, 1386, 1512, 1584, 1848, 2079, 2376, 2772, 3024, 3696, 4158, 4752, 5544, 8316, 11,088, 16,632, 33,264.

2. Factors of 35,640 are: 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 18, 20, 22, 24, 27, 30, 33, 36, 40, 44, 45, 54, 55, 60, 66, 72, 81, 88, 90, 99, 108, 110, 120, 132, 135, 162, 165, 180, 198, 216, 220, 264, 270, 297, 324, 330, 360, 396, 405, 440, 495, 540, 594, 648, 660, 792, 810, 891, 990, 1080, 1188, 1320, 1485, 1620, 1782, 1980, 2376, 2970, 3240, 3564, 3960, 4455, 5940, 7128, 8910, 11,880, 17,820, 35,640.

3. List of all common divisors: 1, 2, 3, 4, 6, 8, 9, 11, 12, 18, 22, 24, 27, 33, 36, 44, 54, 66, 72, 88, 99, 108, 132, 198, 216, 264, 297, 396, 594, 792, 1188, 2376.

4. The final result is: 2376.

As you can see, the higher the number of factors, the more time consuming the procedure gets, and it's easy to make a mistake. It's worth knowing how this method works, but instead, we recommend using our GCF calculator just to make sure that the result is correct.

Another commonly used procedure that can be treated as a greatest common divisor calculator utilizes the prime factorization. This method is somewhat related to the one previously mentioned. Instead of listing all of the possible factors, we find only the ones which are prime numbers. As a result, the product of all shared prime numbers is the answer to our problem, and what's more important, there is always one unique way to factorize any number to prime ones. So now, let's find the greatest common denominator of 72 and 40 using prime factorization:

1. Prime factors of 72 are: 2, 2, 2, 3, 3.

2. Prime factors of 40 are: 2, 2, 2, 5.

3. In other words, we can write: 72 = 2 × 2 × 2 × 3 × 3 and 40 = 2 × 2 × 2 × 5.

4. The part which is shared in both cases is 2 × 2 × 2 = 8, and that's the greatest common factor.

We can see that for this simple example, the result is consistent with the previous method. Let's find out if it works equally well for the more complicated case. What is the GCF of 33,264and 35,640?

1. Prime factors of 33,264 are: 2, 2, 2, 2, 3, 3, 3, 7, 11.

2. Prime factors of 35,640 are: 2, 2, 2, 3, 3, 3, 3, 5, 11.

3. We can use exponent notation to write products as: 33,264 = 2⁴ × 3³ × 7 × 11, 35,640 = 2³ × 3⁴ × 5 × 11.

4. The common product of two numbers is 2³ × 3³ × 11. We can also write it in a more compact and sophisticated way, with factorials taken into account: (3!)³ × 11. Check out if our GCD calculator gives you the same result, which is 2376.

The idea, which is the basis of the Euclidean algorithm, says that if the number k is the greatest common factor of numbers A and B, then k is also GCF for the difference of these numbers A - B. Following this procedure, we will finally reach 0. As a result, the greatest common divisor is the last nonzero number. Let's take a look at our examples one more time – numbers 40 and 72. Each time we make a subtraction, we compare two numbers, ordering them from the highest to the smallest value:

• GCF of 72 and 40: a difference 72 - 40 equals 32,
• GCF of 40 and 32: 40 - 32 = 8,
• GCF of 32 and 8: 32 - 8 = 24,
• GCF of 24 and 8: 24 - 8 = 16,
• GCF of 16 and 8: 16 - 8 = 8,
• GCF of 8 and 8: 8 - 8 = 0 STOP!

In our last step, we obtain 0 from subtraction. This means that we find our greatest common divisor and its value in the penultimate line of the subtractions: 8.

What about a more difficult case with 33,264 and 35,640? Let's try to solve it using the Euclidean algorithm:

• GCF of 35,640 and 33,264: 35,640 - 33,264 = 2376,
• GCF of 33,264 and 2376: 33,264 - 2376 = 30,888,
• GCF of 30,888 and 2376: 30,888 - 2376 = 28,512,
• GCF of 28,512 and 2376: 28,512 - 2376 = 26,136,
• GCF of 26,136 and 2376: 26,136 - 2376 = 23,760,
• GCF of 23,760 and 2376: 23,760 - 2376 = 21,384,
• GCF of 21,384 and 2376: 21,384 - 2376 = 19,008,
• GCF of 19,008 and 2376: 19,008 - 2376 = 16,632,
• GCF of 16,632 and 2376: 16,632 - 2376 = 14,256,
• GCF of 14,256 and 2376: 14,256 - 2376 = 11,880,
• GCF of 11,880 and 2376: 11,880 - 2376 = 9504,
• GCF of 9504 and 2376: 9504 - 2376 = 7128,
• GCF of 7128 and 2376: 7128 - 2376 = 4752,
• GCF of 4752 and 2376: 4752 - 2376 = 2376,
• GCF of 2376 and 2376: 2376 - 2376 = 0 STOP!

Similarly to the previous example, the GCD of 33,264 and 35,640 is the last nonzero difference in the procedure, which is 2376.

As you can see, the basic version of this GCF finder is very efficient and straightforward but has one significant drawback. The bigger the difference between the given numbers, the more steps are needed to reach the final step. The modulo is an effective mathematical operation that solves the issue because we are interested only in a remainder smaller than both numbers. Let's repeat the Euclidean algorithm for our examples using modulo instead of ordinary subtraction:

• GCF of 72 and 40: 72 mod 40 = 32,
• GCF of 40 and 32: 40 mod 32 = 8,
• GCF of 32 and 8: 32 mod 8 = 0 STOP!

The greatest common denominator is 8. What about the other one?

• GCF of 35,640 and 33,264: 35,640 mod 33,264 = 2376,
• GCF of 33,264 and 2376: 33,264 mod 2376 = 0 STOP!

GCD of 35,640 and 33,264 is 2376, and it's found in just two steps instead of 15. Not bad, is it?

If you like arithmetic operations simpler than those used in the Euclidean algorithm (e.g. modulo), the Binary algorithm (or Stein's algorithm) is definitely for you! All you have to use is comparison, subtraction, and division by 2. While estimating the greatest common factor of two numbers, keep in mind these identities:

1. gcd(A, 0) = A, we are using the fact that each number divides zero and an observation from the last step in the Euclidean algorithm – one of the numbers drop to zero, and our result was the previous one.

2. If both A and B are even, it means that gcd(A, B) = 2 × gcd(A/2, B/2) due to the fact that 2 is a common factor.

3. If only one of the numbers is even, let's say A, then gcd(A, B) = gcd(A/2, B). This time 2 is not a common divisor, so we can continue with the reduction until both numbers are odd.

4. If both A and B are odd and A > B, then gcd(A, B) = gcd((A-B)/2, B). This time we combine two features into one step. The first one is derived from the Euclidean algorithm, working out the greatest common divisor of the difference of both numbers and the smaller one. Secondly, the division by 2 is possible since the difference of two odd numbers is even, and according to step 3 we can reduce the even one.

5. Steps 2-4 are repeated until reaching step 1 or if A = B. The outcome will be 2ⁿ × A, where n is the number of factors 2 found in a second step.

As usual, let's practice the algorithm with our sets of numbers. We start with 40 and 72:

• They are both even so gcf(72, 40) = 2 × gcf(36, 20) = 2² × gcf(18, 10) = 2³ × gcf(9, 5) = …;

• The remaining numbers are odd so … = 2³ × gcf((9-5)/2, 5) = 2³ × gcf(2, 5);

• 2 is even so we can reduce it: … = 2³ × gcf(1, 5);

• 1 and 5 are odd so: … = 2³ × gcf((5-1)/2, 1) = 2³ × gcf(2, 1); and

• Remove 2 from an even number: … = 2³ × gcf(1, 1) = 2³ = 8.

Actually, we could've stopped at the third step since GCD of 1 and any number is 1.
Okay, and how to find the greatest common factor of 33,264 and 35,640 using the binary method?

• Two even numbers: gcf(35,640, 33,264) = 2 × gcf(17,820, 16,632) = 2² × gcf(8910, 8316) = 2³ × gcf(4455, 4158) = ….

• One even one odd: … = 2³ × gcf(4455, 2079).

• Two odd: … = 2³ × gcf((4455-2079)/2, 2079) = 2³ × gcf(1188, 2079).

• One even one odd: … = 2³ × gcf(594, 2079) = 2³ × gcf(297, 2079).

• Two odd: … = 2³ × gcf((2079-297)/2, 297) = 2³ × gcf(891, 297).

• Two odd: … = 2³ × gcf((891-297)/2, 297) = 2³ × gcf(297, 297) = 2³ × 297 = 2376.

We know that prime numbers are those that have only 2 positive integer factors: 1 and itself. So the question is, what are coprime numbers? We can define them as numbers which have no common factors. More precisely, 1 is their only common factor, but since we omit 1 in prime factorization, it's okay to say that they have no common divisors. In other words, we can write that numbers A and B are coprime if gcf(A,B) = 1. It doesn't really mean that either of them is a prime number, just the list of shared factors is empty. The examples of coprime numbers are: 5 and 7, 35 and 48, 23,156 and 44,613.

A fun fact: it's possible to calculate the probability that two randomly chosen numbers are coprime. Although it's quite complicated, the overall result is about 61%. Are you surprised? Just test it by yourself – imagine two random numbers (let's say of at least 5 digits), use our greatest common factor calculator and find if the result is 1 or not. Repeat the game multiple times and estimate what's the percentage of coprime numbers you found.

Now that we are aware of numerous methods of finding the greatest common divisor of two numbers, you might ask: "how to find the greatest common factor of three or more numbers?". It turns out not to be as difficult as it might seem at first glance. Well, listing all of the factors for each number is definitely a straightforward method because we can just find the greatest one. However, you can quickly realize that it gets more and more time-consuming as the number of figures increases.

Prime factorization method has a similar drawback, but since we can group all of the primes in, for instance, ascending order, we can introduce a way to work out a result a little faster than previously.

On the other hand, if you prefer using binary or Euclidean algorithms to estimate what is the GCF of multiple numbers, you can also use a theorem that states that:

gcf(a, b, c) = gcf(gcf(a, b), c) = gcf(gcf(a, c), b) = gcf(gcf(b, c), a).

It means that we can calculate the GCD of any two numbers and then start the algorithm again using the outcome and the third number and continue as long as there are any figures left. It doesn't matter which two we choose first.

Another concept closely related to GCD is the least common multiple. To find the least common multiple, we use much of the same process we used to find the GCF. Once we get the numbers down to the prime factorization, we look for the smallest power of each factor, as opposed to the largest power. Then we multiply the highest powers, and the result is the least common multiple or LCM. This can be done by hand or with the use of the LCM calculator.

The greatest common factor can be estimated with the use of LCM. The following expression is valid:

gcf(a, b) = |a × b| / lcm(a, b).

It may be handy to find the least common multiple first due to the complexity and duration. Naturally, it can be calculated either way, so it's worth knowing both how to find GCD and LCM.

We have already presented a few properties of the greatest common denominator. In this section, we list the most important ones:

• If the ratio of two numbers a and b (a > b) is an integer then gcf(a, b) = b.

• gcf(a, 0) = a, used in Euclidean algorithm.

• gcf(a, 1) = 1.

• If a and b don't have common factors (they are coprime), then gcf(a, b) = 1.

• All common factors of a and b are also divisors of gcf(a,b).

• If b × c / a is an integer and gcf(a, b) = d, then a × c / d is also an integer.

• For any integer k: gcf(k×a, k×b) = k × gcf(a, b), used in binary algorithm.

• For any positive integer k: gcf(a/k, b/k) = gcf(a, b) / k.

• gcf(a, b) × lcm(a, b) = |a×b|.

• gcf(a, lcm(b, c)) = lcm(gcf(a, b), gcf(a, c)).

• lcm(a, gcf(b, c)) = gcf(lcm(a, b), lcm(a, c)).

No, the GCF of 14 and 42 is not 2. The GCF of 14 and 42 is 14, and to find it, decompose both numbers into their factors:

• The factors of 14 are 1, 2, 7, and 14.
• The factors of 42 are 1, 2, 3, 6, 7, 14, 21, and 42.

As you can see, the greatest common number in both lists is 14, which is the GCF.

The GCF of 8 and 12 is 4. To get to this answer:

1. Write down all of the factors for all of the numbers:

   • The factors of 8 are 1, 2, 4, and 8.
   • The factors of 12 are 1, 2, 3, 4, 6, and 12.

2. List all common factors: 1, 2, 4.

3. The greatest common factor is the largest of them, which is 4.

The GCF of 24 and 36 is 12. We can arrive at this answer by using the euclidean method:

1. Sort the numbers into ascending order:

   24, 36.

2. Work out the modulo operation, taking the greatest number as the dividend and the smallest as the divisor:

   36 mod 24 = 12.

3. Gather the divisor and the remainder and sort them in ascending order:

   12, 24.

4. Again, work out the modulo operation the same way:

   24 mod 12 = 0.

5. Only one number is left (the divisor, 12), so, 12 is the greatest common factor.

The GCF of 30 and 54 is 6. We can use prime factorization to obtain the answer:

1. Write down all of the numbers as a product of their prime factors:

   • 30 = 2 × 3 × 5
   • 54 = 2 × 3 × 3 × 3

2. List all the common prime factors: 2, 3

3. Find the product of all common prime factors: 2 × 3 = 6

4. The greatest common factor is the result of the previous step. For 30 and 54 is: 6