# Greatest Common Factor (GCF, HCF, GCD) Calculator

## Greatest Common Divisor (GCD/GCF)

## What is GCD, HCF or GCF?

The GCD (greatest common divisor) also known as GCF (greatest common factor) or HCF (highest common factor) is the largest positive integer that divides a given set of numbers. Alternatively, given a set of divisors for any set of more than one integer, the GCD or HCF is the max element from such a set.

The GCD has essential application in mathematics such as simplification of polynomials.

For any given pairs of integers, a GCD always exists. How do we know this? Consider 2 positive integers a,b. Since 1 divides a and 1 divides b, so we have a common factor between a and b. If another integer sa d is a common divisor, then d<=a and d<= b , i.e. d <= min (a,b), thus the set of common factors is finite and therefore GCD(a,b) exists.

Now that we know that the GCD always exists and it is unique, the next agenda is to learn how to calculate it.

## GCD calculation methods

There several techniques that can be used to find the GCD. The choice for the calculation method depends on your assignment’s requirements. Our online calculator for finding the GCF shows you all the steps and explanation for each method.

### Finding GCF by listing divisors method

This is the most straight forward method for finding the GCD/ GCF. As the name suggests, you start off by listing all the divisors of each number and then selecting the highest among the common divisors.

For example

Find the GCD of

Divisors of

Divisors of

Common divisors are

Highest common divisor =

**Example 2:**

Find the GCD of

Divisors of

Divisors of

Common divisors are

Highest common divisor =

Although the divisor method is quite simple to apply, it can be tedious especially when dealing with large numbers as shown by the examples above. More so, you can encounter errors while listing the divisors. To avoid such short comings, I recommend that you use our online GCF calculator; the calculator can list all the divisors without making errors.

### Find the GCF by prime factorization / canonical decomposition method

This method is related to the previous method but instead of listing all the factors/ divisors we only list the ones that are prime. You can also try out our prime factorization calculator to find prime factors for any number. Next we find a set of all common prime factors. The GCF is then calculated by finding the product of these common prime factors.

Example 1

Find the GCF of 24 and 36 using prime factorization

Solution:

Prime factors of 24 are:

Prime factors of 36 are:

Common prime factors =

GCF = product

**Example 2**

Find the GCF of

Solution:

Prime factors of

Prime factors of

Common prime factors =

GCF = product

From the above examples, the prime factorization method is quite applicable even for large numbers. However, listing all the prime factors for a given number can be affected by common errors. To avoid errors when listing the prime factors for a given number, you can use our prime factoring calculator

.### Finding GCF by Euclidian’s algorithm method

The Euclidian algorithm method although not the easiest is the most applicable technique for finding the GCD. This method can be applied even for large and complex numbers. However, the method only works for 2 numbers.

To find the GCD of any two numbers/ integers say a and b using the Euclidian algorithm,

We set up a division loop i.e. assuming that

Example

Find the GCF of

Solution

Example 2:

A school store plans to make and sell packages that contain pencils, erasers and notepads. If the store has 600 pencils, 450 erasers and 300 notepads, what is the largest number of packages that can be made if no items are left over? How many pencils, erasers and notepads are in each package?

Solution: The first question can be found by finding the GCF(600,450,300). This can be achieved through the prime factorization method for finding GCD.

600 =2^2\times 3\times 5^2, 450 = 2 \times 3^2 \times 5^2 and 300 = 2^2 \times3 \times 5^2

By taking the lowest powers of the common factors, we find that the GCF(600,450,300) = 2 \times 3 \times 5^2 = 150 packages. In this case each of the packages will have 600 \divide 150 =4 pencils, 450 \divide 150 = 3 erasers and 300 \divide 150 = 2 notepads

Our GCF calculator shows you all the steps for the Euclidian’s algorithm method.

### How to use the highest common divisor (HCD) calculator

Our online GCD calculator is free and easy to use. To find the HCF or GCF of any given set of numbers, simply insert the numbers in the text field provided and click on the calculate/ find button to calculate. Note that the numbers must be separated with comas, or space. Once you hit the calculate button, the result will be displayed in the solution field below.

### The LCM (Least common Multiple)

See our LCM calculator here: (lcm calculator with steps)

The LCM or the least common multiple is a closely related concept of GCD. Finding the LCM is quite similar to finding the GCD. Prime factorization of each numbers is used to find the LCM. You can find the LCM of any set of numbers using our LCM calculator. The calculator is free to use and shows you all the steps.

### When is the GCF equal to 1 : Coprime Numbers?

A prime number is any number which has

For any coprime numbers A and B, the

## Properties of GCF

GCF has some interesting properties that come in handy in solving mathematical problems. In this section, we will list some of the common properties /characteristic of GCD.

- Ration and GCD: Given any two numbers
x andy , ify>x and the ratioy:x is an integer, then theGCF(x,y) = x and thelcm =y - For any given number a,
GCF(a,0) = a (a property that is commonly applied in Euclidian algorithm) - GCF of 1 and any other number is
1 i.e.GCF(a,1) =1 - If any two numbers a and b are coprime, i.e. and b have no any common factor, then
GCF(a,b)=1 - For any
3 numbersa, b ,c , ifb × c/a is an integer, and thatGCF(a,b) =d , thena × c/d is also an integer - For any given integer
k , theGCF(k × a, k × b) = k × GCF(a,b) (commonly used in binary algorithm) - For any integers
a,b |a × b|=lcm(a,b) × GCF(a,b)

## Some more interesting Facts about GCD/ GCF

Another important aspect of gcd is its uniqueness, i.e. Can a set of positive integers have more than one GCD?

To prove that the GCD of any set of integers is unique: suppose that### Applications of GCF

Now that you have got an online tool to calculate GCF efficiently and accurately, you may be wondering; what are the usage of GCF apart from the beauty of it all?

Here are some of the well known applications of GCD- Simplifying polynomials
- number theory, particularly in modular arithmetic
- Simplifying of fractions
- Used in extended Euclidian algorithm to compute modular inverse

### GCD Practice Problems and Solutions

- find the gcf of 37 and 51 using prime factorization
- find the gcf of 24 and 36 using prime factorization
- find the gcf of 45 and 60 using prime factorization
- find the gcf of 32 , 56 and 96 using prime factorization
- find the gcf of 36 and 81 using prime factorization
- find the gcf of 27 and 63 using prime factorization
- find the gcf of 189 and 200 using prime factorization
- find the gcf of 112 and 144 using prime factorization
- find the gcf of 30 and 36 using prime factorization
- find the gcf of 15 and 20 using prime factorization
- find the gcf of 25 and 50 using prime factorization