What is GCD?

The GCD of two or more integers refers to a positive number that can divide all the numbers without a remainder.

GCD synonyms

HCF – Highest Common factor

GCF– Greatest Common Factor

HCD – Highest Common divisor

How to Find GCD

You can find the GCD using 3 methods which are factoring, LCM and Long Division. Let’s look at each method.

Factoring method

You can simply find the GCD of numbers by listing their factors and then determining the largest number that divides all of them. This is an exhaustive process especially with numbers with many factors. You can find the factors using the factors calculator then compare them.

Example: Find the GCD of 6, 8 and 12

Step 1: List the factors of all the three integers

Factors of 6: 1, 2, 3 and 6

Factors of 8: 1, 2, 4 and 8

Factors of 12: 1, 2, 3, 4 and 12

Step 2: Identify the greatest number which can divide all the numbers

In this case, 2 is the largest factor that can divide all the three numbers

Therefore 2 is the GCD

Using the LCM method

Step 1: Multiply a by b

Step 2: Find the LCM of a and b

Step 3: Divide the answer in step 1 by the answer in step 2

Example 1: Find the GCD of 12 and 36 using The LCM method

12 multiplied 36 is 432

The LCM of 12 and 36 is 36

So GCD (12, 36) = 432 ¸ 36

Therefore GCD (12, 36) is 12

Example 2: Find the GCD of 18 and 24 using the LCM method

The product of 18 and 24 is 432

The LCM of 18 and 24 is 72

So GCD (18, 24) = 432 ¸ 72

Therefore GCD (18, 24) = 6

Using Long Division

You can find the GCD of two numbers without factoring them using Long Division

In Euclidean algorithm you can calculate the GCD of two numbers (a, b) by following these steps

If a = 0 then we can represent the GCD as (0, b) = b

If b = 0 then we can represent the GCD as (0, a) = a

If both are not equal to 0 then we will represent “a” in the quotient remainder form such that (a = b × q + r). q Stands for Quotient and R stands for remainder.

Example: Find the GCD of 14 and 35 using Euclidean algorithm

Divide the large number by the smaller number

Since the remainder is not less than zero, divide the divisor in step one by the remainder in step 2 (14)

Repeat the process until the remainder is zero

Therefore the GCD of 14 and 35 is the corresponding divisor which is 7