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 27 and 18

Divisors of 27 are 3,9,27

Divisors of 18 are 2, 3, 6,9,18

Common divisors are 3, 9

Highest common divisor = 9

Example 2:

Find the GCD of 96 and 32

Divisors of 96 are 2,3,4,8,16,32,48,96

Divisors of 32 are 2,4,8,16,32

Common divisors are 2,4,8,16,32

Highest common divisor = 32

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: 24 = 2 ×2 × 2 × 3

Prime factors of 36 are: 36 = 2 × 2 × 3 × 3

Common prime factors = (2, 2, 3)

GCF = product (2,2,3) = 2 × 2 × 3 = 12;

Example 2

Find the GCF of 81 and 72 using prime factorization

Solution:

Prime factors of 81 are: 81 = 3 × 3 × 3 × 3

Prime factors of 72 are: 72 = 2 × 2 × 2 × 3 × 3

Common prime factors = (3,3)

GCF = product (3,3) = 3 × 3=9;

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 b is the largest of the two numbers, begin by dividing b with a. While the remainder is not equal to zero, repeat the division, assign b=a and a = remainder. The loop will terminate when the remainder is equivalent to zero. The GCF is then given by the value of a from the last iteration.

Example

Find the GCF of 1022 and 320 using the Euclidian algorithm

Solution

1022/320 = 3 Remainder 62

320/62 =5 remainder 10

62/10 = 6 remainder 2

20/2 = 5 remainder 0

GCF = 2

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 1 and itself as the only divisors. On the other hand, two numbers are said to be coprime if and only if the only common factor/ divisor between them is 1. More precisely, such numbers are considered as having no common factors between them.

For any coprime numbers A and B, the GCF (A,B) =1. However this does not imply that either of the numbers is a prime number. For such numbers the set of shared factors is empty. Examples of coprime pairs include 5and 9, 35 and 24, 55 and 671 etc. Finding the probability that any two randomly selected numbers are co-prime is an interesting arising idea. It has been established that the probability of any two random numbers is prime is about 61%. You can try this using out GCF calculator. If the GCF results equal to 1, then the two numbers are co-prime. Repeat this experiment with several pairs, tabulating your result at each interval. You may be surprised to find the result equal to 61%.

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 and y, if y>x and the ratio y:x is an integer, then the GCF(x,y) = x and the lcm =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 numbers a, b ,c , if b × c/a is an integer, and that GCF(a,b) =d, then a × c/d is also an integer
• For any given integer k, the GCF(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 d1, d2 are two GCD for a,b.

Then d1|d2 and d2|d1, thus d1= \pm d2 and since d1>0 and d2>0, we have d1=d2. For any two integers a, b, there exists integers m, n such that the gcd of a,b can be expressed as a linear combination of the integers. i.e. ma+nb=gcd(a,b)

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