# Greatest Common Factor Calculator

## Calculator Use

Calculate GCF, GCD, HCF and GCD of a set of numbers separated by commas. This calculator will find the greatest common factor (GCF) which is also referred to as the greatest common denominator (GCD) or highest common factor (HCF) but is most formally referred to as the **Greatest Common Divisor (GCD)**. ^{[1,2]}

## What is the Greatest Common Factor?

The greatest common factor (GCF or GCD or HCF or GCD) of a set of two or more integers is the greatest positive integer that divides evenly into all numbers in the set, without a remainder. For example, for the set of values 18, 30 and 42 the GCF = 6.

## How to Find the Greatest Common Factor (GCF)

There are several ways to find the greatest common factor of numbers and the most efficient method you use depends on how many numbers you have, how large they are and what you will do with the result.

### Factoring

To find the GCF by factoring, we list out all of the factors of each number or get them with a factor calculator. The whole number factors are numbers that divide evenly into the number to be factored. We then list the common factors of each and choose the largest one.

## Example: Find the GCF of 18 and 27

The factors of 18 are

1, 2,3, 6,9, 18.The factors of 27 are

1,3,9, 27.The common factors of 18 and 27 are 1, 3 and 9.

The greatest common factor of 18 and 27 is 9.

## Example: Find the GCF of 20, 50 and 120

The factors of 20 are 1, 2, 4, 5, 10, 20.

The factors of 50 are 1, 2, 5, 10, 25, 50.

The factors of 120 are 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120.

The common factors of 20, 50 and 120 are 1, 2, 5 and 10. (Include only the factors common to all three numbers.)

The greatest common factor of 20, 50 and 120 is 10.

### Prime Factorization

To find the GCF by prime factorization, we list out all of the prime factors of each number or get them with a prime factor calculator. We then list the prime factors that are common to each of our original numbers. Include the highest number of occurrences of each prime factor that is common to each original number. Multiply these together to get the GCF.

You will see that as our numbers to factor get larger, this prime factorization method may be easier than straight factoring.

## Example: Find the GCF (18, 27)

The prime factorization of 18 is 2 x 3 x 3 = 18.

The prime factorization of 27 is 3 x 3 x 3 = 27.

The occurrences of common prime factors of 18 and 27 are 3 and 3.

So, the greatest common factor of 18 and 27 is 3 x 3 = 9.

## Example: Find the GCF (20, 50, 120)

The prime factorization of 20 is 2 x 2 x 5 = 20.

The prime factorization of 50 is 2 x 5 x 5 = 50.

The prime factorization of 120 is 2 x 2 x 2 x 3 x 5 = 120.

The occurrences of common prime factors of 20, 50 and 120 are 2 and 5.

So, the greatest common factor of 20, 50 and 120 is 2 x 5 = 10.

### Euclid's Algorithm

What do you do if you want to find the GCF of more than 2 very large numbers such as 182664, 154875 and 137688? If you have a calculator for factoring or a calculator for prime factorization or even this GCF calculator it would be easy but if you needed to solve the problem by hand it could become arduous.

Euclid's algorithm gives us a process for finding the GCF of 2 numbers. From the larger number, subtract the smaller number as many times as you can until you have a number that is smaller than the small number (or without getting a negative answer). Now, using the original small number and the result, a smaller number, repeat the process. Repeat this until the last result is zero, and the GCF is the next-to-last small number result. Also see our Euclid's Algorithm Calculator.

## Example: Find the GCF (18, 27)

27 - 18 = 9

18 - 9 - 9 = 0

So, the greatest common factor of 18 and 27 is 9, the smallest result we had before we reached 0.

## Example: Find the GCF (20, 50, 120)

Note that the GCF (x,y,z) = GCF (GCF (x,y),z). In other words, the GCF of 3 or more numbers can be found by finding the GCF of 2 numbers and using the result along with the next number to find the GCF and so on.

Let's get the GCF (120,50) first

120 - 50 - 50 = 120 - (50 * 2) = 20

50 - 20 - 20 = 50 - (20 * 2) = 10

20 - 10 - 10 = 20 - (10 * 2) = 0

So, the greatest common factor of 120 and 50 is 10.

Now let's find the GCF of our third value, 20, and our result, 10. GCF (20,10)

20 - 10 - 10 = 20 - (10 * 2) = 0

So, the greatest common factor of 20 and 10 is 10.

Therefore, the greatest common factor of 120, 50 and 20 is 10.

## Example: Find the GCF (182664, 154875, 137688) or GCF (GCF(182664, 154875), 137688)

First we find the GCF (182664, 154875)

182664 - (154875 * 1) = 27789

154875 - (27789 * 5) = 15930

27789 - (15930 * 1) = 11859

15930 - (11859 * 1) = 4071

11859 - (4071 * 2) = 3717

4071 - (3717 * 1) = 354

3717 - (354 * 10) = 177

354 - (177 * 2) = 0

So, the the greatest common factor of 182664 and 154875 is 177.

Now we find the GCF (177, 137688)

137688 - (177 * 777) = 159

177 - (159 * 1) = 18

159 - (18 * 8) = 15

18 - (15 * 1) = 3

15 - (3 * 5) = 0

So, the greatest common factor of 177 and 137688 is 3.

Therefore, the greatest common factor of 182664, 154875 and 137688 is 3.

### References

[1] Zwillinger, D. (Ed.). CRC Standard Mathematical Tables and Formulae, 31st Edition. New York, NY: CRC Press, 2003 p. 101.

[2] Weisstein, Eric W. "Greatest Common Divisor." From *MathWorld*--A Wolfram Web Resource.

Help With Fractions: Finding the Greatest Common Factor.

The Math Forum: LCD, LCM.

Wikipedia: Euclidean Algorithm.

**Cite this content, page or calculator as:**

Furey, Edward "Greatest Common Factor Calculator"; from *http://www.calculatorsoup.com* - Online Calculator Resource.