Greatest Common Factor Calculator

You can use our greatest common factor calculator to find the greatest common factor (GCF) of a given set of numbers. Finding the GCF is critical for reducing fractions or finding the least common multiple of two numbers. However, it can be tedious to find the GCF of large numbers, say 10144 and 12408, through manual calculations. And that's where this calculator shines - instantly, you can use our greatest common factor finder to find the GCF between any two numbers!

In the following article, you shall learn answers to some fundamental questions, like what is the greatest common factor and how to calculate it.

The greatest common factor of a given set of positive numbers is the largest positive integer that divides them without leaving a remainder.

For example, consider the numbers 45 and 189. The greatest positive integer that can divide them both is 9. Hence, we say that the greatest common factor of 45 and 189 is 9.

We denote the GCF of two numbers, A and B, as GCF(A, B).

There are several methods to find the greatest common factor of two numbers:

• List all factors;
• Prime factorization method;
• Euclidean algorithm;
• Binary algorithm; and
• Using some properties of GCF.

Let's briefly get acquainted with each method.

Listing all factors

This method involves two basic steps. Let's explore them with the help of our previous example:

1. List all possible factors for each number:
   • $45: 1, 3, 5, 9, 15, 45$.
   • $189: 1, 3, 7, 9, 21, 27, 63, 189$.
2. List all common factors for these numbers in ascending order: $1, 3, 9$.
3. The largest number in this list is the greatest common factor: $9$.

This method is the most straightforward approach to the problem. But as you may have observed, it can be tedious to perform manually for large numbers.

Prime factorization method

In this method, we perform the prime factorization of the numbers, i.e., we write them as products of their prime factors and then multiply common prime factors together. Let's apply this method to the same example:

1. Prime factorize the numbers:
   • $45 = 3 \times 3 \times 5$; and
   • $189 = 3 \times 3 \times 3 \times 7$.
2. Gather the common prime factors: $3 \times 3$.
3. Multiply the common prime factors to find the GCF: $3 \times 3 = 9$.

Euclidean algorithm

The Euclidean algorithm method relies on the principle that the GCF of two numbers is also the GCF of these two numbers and their difference:

$\rm{GCF}(A,B) = GCF(A, B, A-B)$

A faster version of this algorithm utilizes the modulo operation rather than subtraction. Let's look at our example, GCF(45, 189):

1. Take the smaller number as the divisor and perform the modulo operation:

   $189 \mod 45 = 9$

2. Take the previous divisor and the modulo remainder in a new list:

   $45, 9$

3. Take the smaller number in this list as the divisor and perform the modulo operation:

   $45 \mod 9 =0$

4. Since the remainder is $0$, we can stop. The last modulo divisor, $9$, is the GCF of 45 and 189.

Binary algorithm for GCF

This algorithm follows these simple rules:

1. If A and B are even, $\rm{GCF}(A,B) = GCF(A/2, B/2)$.
2. If only A is even, $\rm{GCF}(A,B) = GCF(A/2, B)$.
3. If A and B are odd and A>B, $\rm{GCF}(A, B) = GCF((A-B)/2, B)$.
4. $\rm{GCF}(0, A) = A$.

The binary algorithm dictates that we repeat steps 1-3 until we reach A = B or the condition in step 4. Let's look at our two numbers, 45 and 189:

1. Both numbers are odd:
   $\rm{GCF}(45, 189) = GCF((189-45)/2, 45) = GCF(72,45)$
2. Only one number is even: $\rm{GCF(72, 45) = GCF(72/2, 45)= GCF(36, 45)}$
3. Only one number is even: $\rm{GCF(36, 45) = GCF(36/2, 45) = GCF(18, 45)}$
4. Only one number is even: $\rm{GCF(18, 45) = GCF(18/2, 45) = GCF(9, 45)}$
5. Both numbers are odd: $\rm{GCF(9, 45) = GCF((45-9)/2, 9) = GCF(18,9)}$
6. Only one number is even: $\rm{GCF(18, 9) = GCF(18/2, 9) = GCF(9, 9)}$
7. Since both numbers are the same, we can stop here:
   $\rm{GCF(45, 189) = 9}$

Our greatest common factor calculator is easy to use:

1. Simply enter the list of (up to fifteen) numbers in any order. The tool will calculate the greatest common factor of these numbers.
2. Want to check step-by-step solutions? Choose the method from the drop-down list, and our greatest common factor finder will make it happen in a snap!

Are you planning to renovate your house? If you intend to cover any surface with square tiles, you will probably need to compute a GCF!

Suppose that you want to tile the floor of your bathroom. For aesthetic reasons, you want to avoid breaking the tiles. If the floor has length $A$ and width $B$, how big can you take the side length $C$ of your tiles? For the tiles to fill in the floor completely, their side length needs to be a factor of both the length and width. In other words, the largest possible $C$ is $\rm{GCF}(A,B)$.

So, before you start the renovation, make sure to learn how to calculate the greatest common factor!

Check out other tools from Omni that perform similar calculations:

• GCF calculator;
• GCD calculator;
• Greatest common divisor calculator; and
• Greatest common denominator calculator.

The greatest common factor of 8 and 12 is 4. To arrive at this answer, you need to follow these steps:

1. List all factors for both numbers:
   • 8: 1, 2, 4, 8.
   • 12: 1, 2, 3, 4, 6, 12.
2. Gather the common factors between the two numbers: 1, 2, 4.
3. 4 is the largest in this list, hence the greatest common factor of 8 and 12.
4. Verify the calculation and solution steps with our greatest common factor calculator.

The greatest common factor of any two co-prime numbers is 1. This is because, by definition, co-prime numbers have only 1 as the common factor between them.