Created by Mateusz Mucha and Wojciech Sas, PhD candidate Show
Reviewed by Jack Bowater Last updated: Dec 01, 2021 The GCF calculator evaluates the Greatest Common Factor between two to six 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! What is GCF?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. How to Find the Greatest Common FactorThere are various methods which 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:
The good news is that you can estimate the GCD with simple math operations, without roots or logarithms! For most cases they are just subtraction, multiplication, or division. GCF finder - list of factorsThe primary method used to estimate the Greatest Common Divisor is to find all of the factors of the
given numbers. Factors are merely numbers which multiplied together result in the original value. In general, they can be both positive and negative, e.g.
Lets try something more challenging. We want to find the answer for a question: "What is the Greatest Common Factor of
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 to use our GCF calculator, just to make sure that the result is correct. Prime factorizationAnother commonly used procedure which 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
We can see
that for this simple example the result is consistent with the previous method. Let's find if it works equally well for the more complicated case. What is the GCF of
Euclidean algorithmThe idea which is the basis of the Euclidean algorithm says that if the number
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 more difficult case with
Similarly to the previous example, the GCD of 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 which solves the issue because we are interested only in the remainder smaller than both numbers. Let's repeat the Euclidean algorithm for our examples using modulo instead of ordinary subtraction:
The Greatest Common Denominator is 8. What about the other one?
GCD of Binary Greatest Common Divisor algorithmIf 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:
As usual, let's practice the algorithm with our sets of numbers. We start with
Actually, we could've stopped at the third step since GCD of 1 and any number is 1.
Coprime numbersWe 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, 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 Greatest Common Denominator of more than two numbersNow 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 which states that:
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. Least Common MultipleAnother concept closely related to GCD is the Least Common Multiple. To find the Least Common Multiple, we use much of 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. Greatest Common Factor can be estimated with the use of LCM. The following expression is valid:
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. Properties of GCDWe have already presented few properties of Greatest Common Denominator. In this section, we list the most important ones:
Mateusz Mucha and Wojciech Sas, PhD candidate Data (You may enter up to 15 integer numbers) Absolute valueAdditionAssociative property… 58 more What are the GCF factors of 8?Factors of 8: 1, 2, 4, 8.
What are two GCF of 8?GCF of 2 and 8 by Listing Common Factors
There are 2 common factors of 2 and 8, that are 1 and 2. Therefore, the greatest common factor of 2 and 8 is 2.
What are all the factors of 8?Factors of 8: 1, 2, 4, 8. Factors of 9: 1, 3, 9. Factors of 10: 1, 2, 5, 10.
How do you find greatest common factor?The greatest common factor is the greatest factor that divides both numbers. To find the greatest common factor, first list the prime factors of each number. 18 and 24 share one 2 and one 3 in common. We multiply them to get the GCF, so 2 * 3 = 6 is the GCF of 18 and 24.
|