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 can illustrate 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 prime factorize the numbers, i.e., we only list the prime factors of the numbers. Applying this method to the same example:

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

Euclidean algorithm

Euclidean algorithm method relies on the principle that the GCF of two given numbers must also be the GCF of the two numbers and the difference between those numbers:

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

A faster version of this algorithm utilizes the modulo operation rather than subtraction. Looking 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 A = B or the condition in step 4 occurs. 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!

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.